Asp Forum - Faster way to iterate list from end

james

11/16/2015 7:27:00 AM

Any faster way to iterate list from end?

(defun print-from-end (lst)
(loop for i from (1- (length lst)) downto 0
do (nth i lst)))

CL-USER> (time (print-from-end (make-list 100000 :initial-element 'a)))

Evaluation took:
6.970 seconds of real time
6.983467 seconds of total run time (6.966075 user, 0.017392 system)
100.19% CPU
15,297,832,484 processor cycles
1,660,768 bytes consed

24 Answers

Richard Fateman

11/16/2015 7:42:00 AM

On 11/15/2015 11:26 PM, james wrote:
> Any faster way to iterate list from end?
>
> (defun print-from-end (lst)
> (loop for i from (1- (length lst)) downto 0
> do (nth i lst)))
>
> CL-USER> (time (print-from-end (make-list 100000 :initial-element 'a)))
>
> Evaluation took:
> 6.970 seconds of real time
> 6.983467 seconds of total run time (6.966075 user, 0.017392 system)
> 100.19% CPU
> 15,297,832,484 processor cycles
> 1,660,768 bytes consed
>
>

There are a few things wrong with your program, prominently
the fact that "print-from-end" does not print anything.

Assuming that you actually inserted an output statement somewhere,
you might find it roughly equivalent but hugely faster to
just do

(time (reverse (make-list ....)))

William James

11/16/2015 11:16:00 AM

james wrote:

> Any faster way to iterate list from end?
>
> (defun print-from-end (lst)
> (loop for i from (1- (length lst)) downto 0
> do (nth i lst)))
>
> CL-USER> (time (print-from-end (make-list 100000 :initial-element 'a)))
>
> Evaluation took:
> 6.970 seconds of real time
> 6.983467 seconds of total run time (6.966075 user, 0.017392 system)
> 100.19% CPU
> 15,297,832,484 processor cycles
> 1,660,768 bytes consed
>

MatzLisp (Ruby):

(Time.now - (Array.new(100_000, :a).reverse_each{|x| x}; Time.now)).abs
===>0.03125

That's on an old, slow winXP laptop.

words = %w(eeny meeny miney mo)
words.reverse_each{|w| p w}
"mo"
"miney"
"meeny"
"eeny"

--
Elie [Wiesel] thus could have remained at Birkenau to await the Russians.
Although his father had permission to stay with him as a hospital patient or
orderly, father and son talked it over and decided to move out with the
Germans. --- Robert Faurisson

Pascal J. Bourguignon

11/16/2015 11:54:00 AM

james <dinglei2008@gmail.com> writes:

> Any faster way to iterate list from end?

http://metamodular.com/reverse...

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

taruss

11/16/2015 5:58:00 PM

On Sunday, November 15, 2015 at 11:26:50 PM UTC-8, james wrote:
> Any faster way to iterate list from end?
>
> (defun print-from-end (lst)
> (loop for i from (1- (length lst)) downto 0
> do (nth i lst)))

The problem here is that lists are sequential access data structures, so your
call to NTH will have to traverse "i" cells on each call. This, of course,
gives you an O(N^2) traversal. For all but very small lists it would most
likely be faster to do:

(defun print-from-end (list)
(loop for item in (reverse list)
do (print item)))

<rant>
NTH is an abomination and seduces new lisp programmers into thinking that
indexed access to lists is perhaps a constant-time operation when it really
isn't.
</rant>

Pascal J. Bourguignon

11/16/2015 7:09:00 PM

taruss@google.com writes:

> On Sunday, November 15, 2015 at 11:26:50 PM UTC-8, james wrote:
>> Any faster way to iterate list from end?
>>
>> (defun print-from-end (lst)
>> (loop for i from (1- (length lst)) downto 0
>> do (nth i lst)))
>
> The problem here is that lists are sequential access data structures, so your
> call to NTH will have to traverse "i" cells on each call. This, of course,
> gives you an O(N^2) traversal. For all but very small lists it would most
> likely be faster to do:
>
> (defun print-from-end (list)
> (loop for item in (reverse list)
> do (print item)))

On the other hand, having access to each cells, allows you to build an
indirect list mapping to the original list in any way you want:

cl-user> (defun meta-list (list)
"
Returns a list whose CARs are the CONS cells of the LIST.
LIST must be a proper list.
"
(loop :for meta :on list :collect meta))
meta-list
cl-user> (meta-list (list 1 2 3 4))
((1 . #1=(2 . #2=(3 . #3=(4)))) #1# #2# #3#)
cl-user> (nreverse (meta-list (list 1 2 3 4)))
(#1=(4) #2=(3 . #1#) #3=(2 . #2#) (1 . #3#))
cl-user> (mapcar (function car) (nreverse (meta-list (list 1 2 3 4))))
(4 3 2 1)

So if you need to process the list from both ends, you can keep
(nreverse (meta-list (list 1 2 3 4))) around.

As for print-from-end, you might prefer to use count-if, which would
assumedly use the best algorithm (eg. Robert Strandh's for long lists),
selected by the implementation.

(defun print-from-end (list)
(count-if (lambda (element)
(print element)
nil)
list :from-end t))

(Notice that only count-if enforce the processing in the reverse order;
:FROM-END T for the other functions just require the last occurence).

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Kaz Kylheku

11/16/2015 7:59:00 PM

On 2015-11-16, james <dinglei2008@gmail.com> wrote:
> Any faster way to iterate list from end?
>
> (defun print-from-end (lst)

The naming convention LST is not required in Common Lisp. A local variable
named LIST doesn't shadow the LIST function.

> (loop for i from (1- (length lst)) downto 0
> do (nth i lst)))

Yes; construct a reversed copy of the list with the reverse
function, and traverse it forward:

(loop for elem in (reverse list) do ...)

If this list is encapsulated in some object, it may be possible to
keep two lists in parallel, so that both orders are available.

Or you can cache the reversal so that if the reverse order is needed multiple
times, without any updates of the original list in between, it can be reused.

> CL-USER> (time (print-from-end (make-list 100000 :initial-element 'a)))

Timing this is almost pointless. A very basic background in CS, that
every programmer should have, will tell you that what you're doing is slow
*asymptotically*: the running time is O(n*n), meaning that it rises with the
square of the input size. Whenever you double the input size, the time
increases four-fold (except for small input sizes, where the effects of
exceeding the thresholds of various levels of caching make the difference
appear even *worse*).

Kaz Kylheku

11/16/2015 8:09:00 PM

On 2015-11-16, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> cl-user> (defun meta-list (list)
> "
> Returns a list whose CARs are the CONS cells of the LIST.
> LIST must be a proper list.
> "
> (loop :for meta :on list :collect meta))
[ ... ]
> So if you need to process the list from both ends, you can keep
> (nreverse (meta-list (list 1 2 3 4))) around.

In this regard alone, I fail to see the advantage of this meta list, compared
to just keeping (reverse list) which gives you the original CAR-s in reverse
order.

(I understand that having the conses of the original list in reverse
order has the advantage that you can make the items available in
some other order, like reverse, while retaining fast access to the original
succesor of each item, since you have the original cons.)

A succinct way to construct the metalist is simply this:

(maplist #'identity list)

You're only baiting Mr. WJ with such overwrought loopiness.

Pascal J. Bourguignon

11/16/2015 8:31:00 PM

Kaz Kylheku <kaz@kylheku.com> writes:

> On 2015-11-16, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
>> cl-user> (defun meta-list (list)
>> "
>> Returns a list whose CARs are the CONS cells of the LIST.
>> LIST must be a proper list.
>> "
>> (loop :for meta :on list :collect meta))
> [ ... ]
>> So if you need to process the list from both ends, you can keep
>> (nreverse (meta-list (list 1 2 3 4))) around.
>
> In this regard alone, I fail to see the advantage of this meta list, compared
> to just keeping (reverse list) which gives you the original CAR-s in reverse
> order.

Thru the meta list you can modify the original list.

> (I understand that having the conses of the original list in reverse
> order has the advantage that you can make the items available in
> some other order, like reverse, while retaining fast access to the original
> succesor of each item, since you have the original cons.)
>
> A succinct way to construct the metalist is simply this:
>
> (maplist #'identity list)
>
> You're only baiting Mr. WJ with such overwrought loopiness.

Indeed. LOOP is such a swiss knife, there's a tendency to overuse it.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

smh

11/17/2015 12:42:00 AM

Strange how Lisp programmers forget about recursion. Creating a reverse copy of a list conses. Something like the following runs cons free (except for any consing done by printing itself).

(defun tnirp (list)
(pprint-logical-block (*standard-output* list :prefix "(" :suffix ")")
(labels ((tnirp1 (list)
(when list
(tnirp1 (cdr list))
(when (cdr list)
(write-char #\space)
(pprint-newline :linear))
(write (car list)))))
(tnirp1 list)))
list)

This assumes, of course, that the list isn't so long that it blows the stack.

Kaz Kylheku

11/17/2015 12:51:00 AM

On 2015-11-17, smh <shaflich@gmail.com> wrote:
> Strange how Lisp programmers forget about recursion. Creating a reverse copy
> of a list conses. Something like the following runs cons free (except for
> any consing done by printing itself).
[ ... ]
> This assumes, of course, that the list isn't so long that it blows the stack.

Which is why Lisp programmers forgot about recursion.

The lists are long here; upthread, a > 6s timing was reported for a list with
100000 entries.

That could be large enough to blow the stack.

comp.lang.lisp

Faster way to iterate list from end

james

Richard Fateman

William James

Pascal J. Bourguignon

taruss

Pascal J. Bourguignon

Kaz Kylheku

Kaz Kylheku

Pascal J. Bourguignon

smh

Kaz Kylheku

x Login to ForumsZone