all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* O(N^2) behavior in LOOP
@ 2010-05-29 21:56 Daniel Colascione
  2010-05-29 22:06 ` Daniel Colascione
  0 siblings, 1 reply; 21+ messages in thread
From: Daniel Colascione @ 2010-05-29 21:56 UTC (permalink / raw)
  To: Emacs development discussions

[-- Attachment #1: Type: text/plain, Size: 892 bytes --]

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?


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

^ permalink raw reply	[flat|nested] 21+ messages in thread

end of thread, other threads:[~2010-06-18 13:40 UTC | newest]

Thread overview: 21+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-05-29 21:56 O(N^2) behavior in LOOP Daniel Colascione
2010-05-29 22:06 ` Daniel Colascione
2010-05-29 22:14   ` Lennart Borgman
2010-05-29 22:35   ` Geoff Gole
2010-05-29 23:58     ` [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP) Daniel Colascione
2010-05-30  0:45       ` Ken Raeburn
2010-05-30  0:49         ` Daniel Colascione
2010-06-16 17:44           ` tomas
2010-06-16 18:10             ` [PATCH] use tail pointer for LOOP David Kastrup
2010-06-17  5:10               ` tomas
2010-06-17  7:18                 ` Thien-Thi Nguyen
2010-06-17  9:22                   ` tomas
2010-06-17 10:03                     ` Thien-Thi Nguyen
2010-06-17 14:05                       ` tomas
2010-06-17 15:16                         ` Thien-Thi Nguyen
2010-06-17 10:12                     ` Thien-Thi Nguyen
2010-06-17 20:48                 ` Stefan Monnier
2010-06-18  7:07                   ` David Kastrup
2010-06-18 13:40                     ` Stefan Monnier
2010-05-30 17:05       ` Štěpán Němec
2010-05-30 17:09         ` Daniel Colascione

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.