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.
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))))
_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/emacs-devel
