chicken-users
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Chicken-users] length performance


From: Mario Domenech Goulart
Subject: Re: [Chicken-users] length performance
Date: Thu, 05 Jan 2006 16:40:14 +0000
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux)

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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]