* New function for subr.el: sort-on
@ 2017-11-24 17:36 John Wiegley
2017-11-25 1:09 ` Basil L. Contovounesios
0 siblings, 1 reply; 2+ messages in thread
From: John Wiegley @ 2017-11-24 17:36 UTC (permalink / raw)
To: emacs-devel
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
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: New function for subr.el: sort-on
2017-11-24 17:36 New function for subr.el: sort-on John Wiegley
@ 2017-11-25 1:09 ` Basil L. Contovounesios
0 siblings, 0 replies; 2+ messages in thread
From: Basil L. Contovounesios @ 2017-11-25 1:09 UTC (permalink / raw)
To: John Wiegley; +Cc: emacs-devel
John Wiegley <johnw@gnu.org> writes:
> (defsubst sort-on (seq predicate accessor)
Perhaps the name `sort-by' would be more consistent with the
`seq-sort-by' function defined in lisp/emacs-lisp/seq.el?
> (mapcar #'cdr (sort (mapcar #'(lambda (x) (cons (funcall accessor x) x)) seq)
^^
Out of curiosity, is there a preference/convention
for/against `function'-quoting lambdas in the Emacs source
tree? The only reason I avoid it is because it breaks the
fontification of `lambda' as a macro. :)
> (setq seq (sort* seq #'(lambda (x y) (funcall predicate (car x) (car y)))))
^^^^^
Is this not the same as using plain `sort' here?
--
Basil
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2017-11-25 1:09 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-11-24 17:36 New function for subr.el: sort-on John Wiegley
2017-11-25 1:09 ` Basil L. Contovounesios
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).