[Top][All Lists]
[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