[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] use tail pointer for LOOP
From: |
David Kastrup |
Subject: |
Re: [PATCH] use tail pointer for LOOP |
Date: |
Wed, 16 Jun 2010 20:10:48 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) |
address@hidden writes:
> On Sat, May 29, 2010 at 08:49:13PM -0400, Daniel Colascione wrote:
>> On 5/29/10 8:45 PM, Ken Raeburn wrote:
>
> [...]
>
>> > 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 [...]
>
> This has intrigued me for quite a while.
>
> Since I really should be doing tax declarations, I couldn't hold back for
> longer -- here is my (very unscientific) approach, to help you all
> procrastinate a bit too:
>
> | (defun copy1 (lst)
> | "Build up a copy of lst by consing up in reverse order, then
> | reversing"
> | (let ((res))
> | (while lst
> | (setq res (cons (car lst) res)
> | lst (cdr lst)))
> | (nreverse res)))
> |
> | (defun copy2 (lst)
> | "Build up a copy of lst by consing up in order, keeping a tail
> | pointer"
> | (when lst
> | (let ((res) (tail))
> | (setq res (cons (car lst) nil)
> | tail res
> | lst (cdr lst))
> | (while lst
> | (setcdr tail (cons (car lst) nil))
> | (setq tail (cdr tail)
> | lst (cdr lst)))
> | res)))
> |
> | (defun runtwo (n)
> | (let ((lst))
> | (while (> n 0)
> | (setq lst (cons n lst)
> | n (1- n)))
> | (garbage-collect)
> | (cons (benchmark-run (copy1 lst))
> | (benchmark-run (copy2 lst)))))
> |
> | (runtwo 1000000)
>
> (Maybe the tail pointer version could be done more elegantly: I'd be
> delighted to be taught more :)
>
> Turns out that the nreverse version is a tad faster (on my hardware, one
> of those Atom based netbooks, in case it matters) -- about 2.1 versus
> 2.7 seconds for a list of size 10^6. Garbage collections are comparable.
Did you byte-compile?
--
David Kastrup
- Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP), tomas, 2010/06/16
- Re: [PATCH] use tail pointer for LOOP,
David Kastrup <=
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Stefan Monnier, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, David Kastrup, 2010/06/18
- Re: [PATCH] use tail pointer for LOOP, Stefan Monnier, 2010/06/18