Re: cl-dolist, dolist, cl-return,

[John Mastro <john.b.mastro@gmail.com>]

Emanuel Berg <embe8573@student.uu.se> wrote:
>> My point was that the re-evaluation part would be
>> just a side-problem: even if your expression is
>> a mere variable (so re-evaluating it is very cheap),
>> the need to use `nth' at each step would force an
>> O(N^2) complexity to this loop.
>
> You mean `nth' is linear, and `dotimes' is linear, so
> the whole thing is linear**2 = quadratic?
>
> But I'm not using nth - probably you misread "neq".
> (Ha! - maybe a reason not to do it just presented
> itself...)
>
> Here is the code, which is linear, O(n), unless
> there is a hidden nth somewhere...

Stefan means that if, given `(dolist (x (list 1 2 3)) ...)', you
evaluated `(list 1 2 3)' on every iteration you would end up doing
something the moral equivalent of

    (setq elt (nth 0 (list 1 2 3))) ;; first iteration
    (setq elt (nth 1 (list 1 2 3))) ;; second iteration

and so on, rather than

    (let ((the-list (list 1 2 3)))
      (setq elt (pop the-list))  ;; first iteration
      (setq elt (pop the-list))) ;; second iteration

The latter case (which is how things really work) is obviously much
more efficient, because the former case needlessly re-walks
the list.

-- 
john