all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* cl.el sort* efficiency
@ 2006-12-22 19:19 Kevin Ryde
  2006-12-23  0:29 ` Juanma Barranquero
  0 siblings, 1 reply; 8+ messages in thread
From: Kevin Ryde @ 2006-12-22 19:19 UTC (permalink / raw)


I noticed that cl sort* function calls the given :key function within
every comparison, which is not good if key extraction is a big slow
calculation.  I struck such a case myself recently, and in fact the
example in the manual showing

	(sort* lst 'string-lessp :key 'downcase)

is almost another.  If possible I don't think you'd want to throw off
two new downcased strings in every compare.

The code below is an idea to build key results in an alist and sort
that.  It's not tested properly yet, and really isn't a thing of
beauty.  There's some trouble taken to rearrange the original cons
cells because that's discussed at length in the manual for plain
"sort", so maybe someone's relying on that.  Ideas for something
better or worse would be welcome.


(defun sort* (cl-seq cl-pred &rest cl-keys)
  "Sort the argument SEQ according to PREDICATE.
This is a destructive function; it reuses the storage of SEQ if possible.
\nKeywords supported:  :key
\n(fn SEQ PREDICATE [KEYWORD VALUE]...)"
  (if (nlistp cl-seq)
      (replace cl-seq (apply 'sort* (append cl-seq nil) cl-pred cl-keys))
    (cl-parsing-keywords (:key) ()
      (if (memq cl-key '(nil identity))
	  (sort cl-seq cl-pred)

        ;; turn cl-seq into an alist of (KEY-RESULT . ORIGINAL-CONS-CELL)
        (let (cl-x)
          (while cl-seq
            (setq cl-x (acons (funcall cl-key (car cl-seq)) cl-seq cl-x))
            (setq cl-seq (cdr cl-seq)))
          (setq cl-seq (nreverse cl-x)))
        ;; sort that alist by KEY-RESULT
        (setq cl-seq (sort cl-seq (if (eq cl-pred '<)
                                      'car-less-than-car
                                    (lambda (cl-x cl-y)
                                      (funcall cl-pred
                                               (car cl-x) (car cl-y))))))
        ;; mung cdrs of original cons cells to put them in new order
        (let (cell prev)
          (while cl-seq
            (setq cell (cdar cl-seq))
            (setcdr cell prev)
            (setq prev cell)
            (setq cl-seq (cdr cl-seq)))
          (nreverse prev))))))

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

end of thread, other threads:[~2006-12-26  0:26 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2006-12-22 19:19 cl.el sort* efficiency Kevin Ryde
2006-12-23  0:29 ` Juanma Barranquero
2006-12-24  0:56   ` Kevin Ryde
2006-12-24  2:08     ` Miles Bader
2006-12-25 23:10       ` Stefan Monnier
2006-12-26  0:26       ` Kevin Ryde
2006-12-24 17:09     ` Richard Stallman
2006-12-25  1:09     ` Juanma Barranquero

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.