From: "John Wiegley" <johnw@gnu.org>
To: emacs-devel@gnu.org
Subject: New function for subr.el: sort-on
Date: Fri, 24 Nov 2017 09:36:43 -0800 [thread overview]
Message-ID: <m2h8tjpoic.fsf@newartisans.com> (raw)
This can be more memory efficient than using `sort' with a predicate, since it
computes each value used by the predicate only once. If the predicate only
needs to access sub-elements, and not do any computation, there may be no
advantage.
--8<---------------cut here---------------start------------->8---
(defsubst sort-on (seq predicate accessor)
"Sort SEQ using PREDICATE applied to values returned by ACCESSOR.
This implements the so-called Schwartzian transform, which has
the performance advantage of applying ACCESSOR at most once per
element in the list, as opposed to using `sort' with a PREDICATE
that applies the ACCESSOR.
Note: this function is only a win over `sort' if ACCESSOR is
compute-intensive; otherwise, it uses more intermediate cons
cells than regular `sort', and so represents a memory for CPU
tradeoff."
(mapcar #'cdr (sort (mapcar #'(lambda (x) (cons (funcall accessor x) x)) seq)
#'(lambda (x y) (funcall predicate (car x) (car y))))))
(defun sort-on* (seq predicate accessor)
"Sort SEQ using PREDICATE applied to values returned by ACCESSOR.
This is a destructive version of `sort-on', which attempts to
reuse storage as much as possible."
(let ((seq2 seq))
(while seq2
(setcar seq2 (cons (funcall accessor (car seq2)) (car seq2)))
(setq seq2 (cdr seq2))))
(setq seq (sort* seq #'(lambda (x y) (funcall predicate (car x) (car y)))))
(let ((seq2 seq))
(while seq2
(setcar seq2 (cdar seq2))
(setq seq2 (cdr seq2)))
seq))
--8<---------------cut here---------------end--------------->8---
--
John Wiegley GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com 60E1 46C4 BD1A 7AC1 4BA2
next reply other threads:[~2017-11-24 17:36 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-11-24 17:36 John Wiegley [this message]
2017-11-25 1:09 ` New function for subr.el: sort-on Basil L. Contovounesios
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=m2h8tjpoic.fsf@newartisans.com \
--to=johnw@gnu.org \
--cc=emacs-devel@gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).