Re: [Chicken-users] length performance

[Zbigniew]

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!

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.

On 1/4/06, John Cowan <address@hidden> wrote:
> In order to keep counts as you suggest, it would be necessary to keep
> a count with *each* pair, thus increasing the storage cost by 50%.

> Mario Domenech Goulart scripsit:
>
> > I've noticed that the performance of the length function is a bit low
> > for medium/large lists.  As far as I understand (from runtime.c
> > C_i_length), Chicken counts the elements from the given list everytime
> > length is invoked.  Is it like that?