Any interest in a function like this to add to subr.el?

Any interest in a function like this to add to subr.el?

[John Wiegley]

(defun sort-on (seq predicate accessor)
  "Sort SEQ use 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))))))

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Any interest in a function like this to add to subr.el?

[Dmitry Gutov]

On 18.10.2016 20:53, John Wiegley wrote:
> (defun sort-on (seq predicate accessor)
>   "Sort SEQ use 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))))))

Isn't this basically cl-sort, though?

Re: Any interest in a function like this to add to subr.el?

[John Wiegley]

>>>>> "DG" == Dmitry Gutov <dgutov@yandex.ru> writes:

GD> Isn't this basically cl-sort, though?

No.  cl-sort is (1) destructive and (2) does not guarantee calling the
accessor only once per element.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Any interest in a function like this to add to subr.el?

[Dmitry Gutov]

On 18.10.2016 23:34, John Wiegley wrote:
>>>>>> "DG" == Dmitry Gutov <dgutov@yandex.ru> writes:
>
> GD> Isn't this basically cl-sort, though?
>
> No.  cl-sort is (1) destructive and (2) does not guarantee calling the
> accessor only once per element.

You're right.

Then I agree that we want a function like that. We'd want a destructive 
version of it as well, though.

Re: Any interest in a function like this to add to subr.el?

[John Wiegley]

>>>>> "DG" == Dmitry Gutov <dgutov@yandex.ru> writes:

GD> Then I agree that we want a function like that. We'd want a destructive
GD> version of it as well, though.

Yes, good idea!  How about something like this:

(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))

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Any interest in a function like this to add to subr.el?

[Ken Raeburn]

> On Oct 18, 2016, at 17:25, John Wiegley <jwiegley@gmail.com> wrote:
> 
>>>>>> "DG" == Dmitry Gutov <dgutov@yandex.ru> writes:
> 
> GD> Then I agree that we want a function like that. We'd want a destructive
> GD> version of it as well, though.
> 
> Yes, good idea!  How about something like this:
> 
> (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))))

Is there a shorthand function for this bit?  I.e., mutate every element of the list according to some supplied function, but reusing the same list storage.  If so, the body of sort-on* becomes about as short as your original sort-on.

Logically it’d be a variant of mapcar but “mapcar*” is something else…

>  (setq seq (sort* seq #'(lambda (x y) (funcall predicate (car x) (car y)))))

Is there any benefit to sort* instead of sort here?  As far as I can see, sort* just calls sort after (1) checking whether the list we just iterated over is a list, and (2) checking whether we supplied a “:key” keyword, which we didn’t.

Some other observations:

“sort” and “sort*” will work on vectors, too, returning the now-sorted vector; your sort-on, using mapcar, will make it into a list, and sort-on* will fail trying to apply car and cdr to vectors.  Were these intended to work on lists only?

As far as your doc strings go, you say sort-on will apply the accessor “at most once per element in the list”, but it’s going to be exactly once per element, isn’t it?

The “cdr” pass before returning could walk the intermediate sorted list in the sort-on case too, making it more space-efficient.  Since the inner “mapcar” call has allocated us some unshared storage, we can just alter it in place and return it to the caller.

Ken

Re: Any interest in a function like this to add to subr.el?

[John Wiegley]

>>>>> Ken Raeburn <raeburn@raeburn.org> writes:

> Is there a shorthand function for this bit? I.e., mutate every element of
> the list according to some supplied function, but reusing the same list
> storage. If so, the body of sort-on* becomes about as short as your original
> sort-on.

I'd like that too.

> Is there any benefit to sort* instead of sort here? As far as I can see,
> sort* just calls sort after (1) checking whether the list we just iterated
> over is a list, and (2) checking whether we supplied a “:key” keyword, which
> we didn’t.

You're right, I should just use sort.

> “sort” and “sort*” will work on vectors, too, returning the now-sorted
> vector; your sort-on, using mapcar, will make it into a list, and sort-on*
> will fail trying to apply car and cdr to vectors. Were these intended to
> work on lists only?

It should be generalized to work for vectors as well.

> As far as your doc strings go, you say sort-on will apply the accessor “at
> most once per element in the list”, but it’s going to be exactly once per
> element, isn’t it?

Correct.

> The “cdr” pass before returning could walk the intermediate sorted list in
> the sort-on case too, making it more space-efficient. Since the inner
> “mapcar” call has allocated us some unshared storage, we can just alter it
> in place and return it to the caller.

Great observation, I'll do that!

Thanks for the valuable feedback,
-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Any interest in a function like this to add to subr.el?

[Stefan Monnier]

>   (setq seq (sort* seq #'(lambda (x y) (funcall predicate (car x) (car y)))))
               ^^^^^
You mean `cl-sort`!


        Stefan

Re: Any interest in a function like this to add to subr.el?

[Stefan Monnier]

> We'd want a destructive version of it as well, though.

Why?


        Stefan

Re: Any interest in a function like this to add to subr.el?

[Dmitry Gutov]

On 19.10.2016 17:48, Stefan Monnier wrote:
>> We'd want a destructive version of it as well, though.
>
> Why?

I was thinking for performance.

But yeah, we should probably benchmark the two versions on multiple 
inputs, and only keep the destructive version if it's indeed noticeably 
faster on some (like big lists where the predicate costs on the order of 
the magnitude of allocating a new cons).

Re: Any interest in a function like this to add to subr.el?

[Stefan Monnier]

>>> We'd want a destructive version of it as well, though.
>> Why?
> I was thinking for performance.

I'd find it really surprising if N uses of `cons` would be
sufficiently more expensive than N uses of `setcar` not to be
drowned by the O(N*log N) funcalls and other processing.
But it wouldn't be the first time I was wrong, of course.


        Stefan

Re: Any interest in a function like this to add to subr.el?

[Andy Moreton]

On Tue 18 Oct 2016, John Wiegley wrote:

> (defun sort-on (seq predicate accessor)
>   "Sort SEQ use 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))))))

Doesn't a specialised routine like this belong in subr-x.el ? At least
initially, until it is demonstrated that there is widespread need for it
in emacs core.

    AndyM

Re: Any interest in a function like this to add to subr.el?

[Stefan Monnier]

> Doesn't a specialised routine like this belong in subr-x.el ?

I think it belongs in seq.el instead.


        Stefan