[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: 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

   (catch '--cl-block-nil--
           '(1 2 3))
          (x nil)
          (foo nil))
           (consp --cl-var--)
         (setq x
               (car --cl-var--))
         (setq foo
               (nconc foo
                      (list x)))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ WTF?
         (setq --cl-var--
               (cdr --cl-var--)))

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?

Attachment: signature.asc
Description: OpenPGP digital signature

reply via email to

[Prev in Thread] Current Thread [Next in Thread]