[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
O(N^2) behavior in LOOP
From: |
Daniel Colascione |
Subject: |
O(N^2) behavior in LOOP |
Date: |
Sat, 29 May 2010 17:56:09 -0400 |
User-agent: |
Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; en-US; rv:1.9.1.9) Gecko/20100317 Thunderbird/3.0.4 |
Erm, what's going on here?
(loop for x in '(1 2 3)
collect x into foo)
Expands into
(cl-block-wrapper
(catch '--cl-block-nil--
(let*
((--cl-var--
'(1 2 3))
(x nil)
(foo nil))
(while
(consp --cl-var--)
(setq x
(car --cl-var--))
(setq foo
(nconc foo
(list x)))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ WTF?
(setq --cl-var--
(cdr --cl-var--)))
nil)))
What is going on with the indicated line? That's O(N^2) because nconc
has to traverse the entire 'foo' list each time a value is appended.
Without the 'into' clause, loop uses push and nreverse, which, while
still suboptimal, is at least linear.
Before I go fix the loop macro, is there a _reason_ for the nconc silliness?
signature.asc
Description: OpenPGP digital signature
- O(N^2) behavior in LOOP,
Daniel Colascione <=