Re: lists.texi

[David Kastrup <dak@gnu.org>]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> Richard Stallman wrote:
>
>    If you want to do a little work, I am sure you could write a single
>    loop that produces the right elements in the right order.  Then you
>    could rotate it properly with a single call to setcdr followed by
>    nconc'ing the pieces in the opposite order.
>
> Unless I am completely misunderstanding things, I believe I was a
> little bit too quick to admit that my original function:
>
> (defun ring-elements (ring)
>   "Return a list of the elements of RING in order, newest first."
>   (let (lst)
>     (dotimes (var (ring-length ring))
>       (push (ring-ref ring var) lst))
>     (nreverse lst)))
>
> was quadratic.  It essentially does ring-length times an aref in
> _vector_, which unlike checking the element at an average position
> in a _list_, would not appear to be linear in the size of the
> vector.

Well, I was one of the O(n^2) criers, and I did not know that ring-ref
works via aref.  Looking at ring-ref, however, it would appear that
the O(1) constant is pretty hefty.

> Anyway, I now propose the following which avoids the nreverse and
> esentially "inlines" the `ring-ref' call, but in a way that avoids a
> lot more overhead than a simple inlining.  So I believe that it
> should be an improvement by a pretty good constant factor, which
> would not be of too much help if it really is quadratic, but why is
> it?
>
> (defun ring-elements (ring)
>   "Return a list of the elements of RING, in order, newest first."
>   (let ((start (car ring))
>   (size (ring-size ring))
>   (vect (cddr ring))
>   lst)
>     (dotimes (var (cadr ring) lst)
>       (push (aref vect (mod (+ start var) size)) lst))))

As long as you checked that the elements come out in the right order,
this would appear like a pretty good solution.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum