Luc Teirlinck <[EMAIL PROTECTED]> 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 _______________________________________________ Emacs-devel mailing list Emacs-devel@gnu.org http://lists.gnu.org/mailman/listinfo/emacs-devel
