[Top][All Lists]

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

Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP)

From: Daniel Colascione
Subject: Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP)
Date: Sat, 29 May 2010 20:49:13 -0400
User-agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv: Gecko/20100317 Thunderbird/3.0.4

On 5/29/10 8:45 PM, Ken Raeburn wrote:
> On May 29, 2010, at 19:58, Daniel Colascione wrote:
>> We do this only for the anonymous-variable case, but it's still an
>> improvement.
> If it's only in the anonymous case, where (if I understand
> correctly)
> the value isn't accessible until the loop construct returns a value, why
> not keep it simple and build the list in reverse, doing an nreverse call
> at the end? It doesn't need to be "in order" in the intermediate states.
> Is it any faster to build the list in order? (Simply avoiding nreverse
> obviously makes things a little faster, but are you doing more work each
> time around the loop to maintain and use the tail pointer?)

It's only a little bit more work to use the tail pointer, and it saves
having to traverse the entire list on return, which could be a lot of
work for a large list. For small lists, it might be a tossup, but then
the difference doesn't matter much in that case anyway.

Also, other LOOP implementations use tail pointers.

Attachment: signature.asc
Description: OpenPGP digital signature

reply via email to

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