[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: cl-dolist, dolist, cl-return,
From: |
John Mastro |
Subject: |
Re: cl-dolist, dolist, cl-return, |
Date: |
Wed, 8 Jul 2015 18:49:34 -0700 |
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
- cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/07
- Re: cl-dolist, dolist, cl-return,, John Mastro, 2015/07/07
- Re: cl-dolist, dolist, cl-return,, Stefan Monnier, 2015/07/07
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/08
- Re: cl-dolist, dolist, cl-return,, Stefan Monnier, 2015/07/08
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/08
- Re: cl-dolist, dolist, cl-return,,
John Mastro <=
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/09
- Message not available
- Re: cl-dolist, dolist, cl-return,, Barry Margolin, 2015/07/10
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/11
- Re: cl-dolist, dolist, cl-return,, Stefan Monnier, 2015/07/10
Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/08
- Re: cl-dolist, dolist, cl-return,, Pascal J. Bourguignon, 2015/07/07
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/08
- RE: cl-dolist, dolist, cl-return,, Drew Adams, 2015/07/08
- Re: cl-dolist, dolist, cl-return,, Emanuel Berg, 2015/07/08
- Message not available
- Re: cl-dolist, dolist, cl-return,, Pascal J. Bourguignon, 2015/07/08