Hello,
On Thu, 5 Jan 2006 03:07:16 -0600 Zbigniew <address@hidden>
wrote:
Additionally, it would become infeasible to splice a pair into or out
of the list [an O(1) operation], given only a pointer into the middle
of the list, because you cannot update the counts of earlier list
elements. This would be "possible" with a doubly-linked list---but
insert and remove would now require an average of O(n) operations, to
update every count!
I understand. Thanks for you comments, Zbigniew, Kon and John. I was
just wondering if there could be some implementation trick to make
length faster.
The structure you are looking for is a vector (Python and Perl
"lists"
are actually vectors), not a linked list (Scheme list). As Kon
pointed out, length is fairly uncommon in Scheme, and heavy use may
indicate you're programming against the Scheme paradigm. Might I
suggest reading the beginning of SICP to develop the proper
habits, if
you have not already.
Actually it's not a question of habit (at least I hope so :-)). It
just
happened that I was comparing the performance of some basic Chicken
functions against Python and the performance of length was a bit lower
than what I was expecting.
Best wishes,
Mario
_______________________________________________
Chicken-users mailing list
address@hidden
http://lists.nongnu.org/mailman/listinfo/chicken-users