[cl-utilities-devel] Re: making EXTREMUM return multiple values -- and request for a function EXTREMA.

[Peter Scott]

On 11/15/05, Tobias C. Rittweiler <tcr at freebits.de> wrote:
> I'd like to suggest making EXTREMUM return all /equivalent/ extrema as
> multiple values, such that for instance:
>
>   CL-USER> (extremum '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr)
>   (D . 1)
>   (B . 1)

That makes a lot of sense from a semantics perspective, and you've
given me a lot to think about. However, I believe that this would be a
better way to do it:

* The EXTREMUM function would behave the way it does now. This is
efficient and its correctness is immediately obvious from the source
code. Using EXTREMUM indicates that you want only one answer, and you
aren't particularly concerned about duplicates. This should be
explicitly spelled out in the documentation (which I should probably
get around to finishing sometime soon...).

* The EXTREMA function will return a list of all equivalent extrema
(by your definition of equality). This name and return type emphasizes
that it is returning all the extrema, and nothing that is not an
extremum.

* The N-MOST-EXTREME function will behave like your EXTREMA function:
it will return the n most extreme values in a sequence.

> My more restrictive (featurewise) version based on parts of your code
> but that I hacked together to fit my particular needs (no :start, :end
> keywords, only works for lists), looks like this:
>
>   ;;; Inspired by www.cliki.net/EXTREMUM), but this function returns
>   ;;; all extrema of sequence (if being equal) as multiple values.
>   (defun extremum (sequence predicate &key (key #'identity))
>     (let* ((smallest-elements (list (first sequence)))
>            (smallest-key (funcall key (first smallest-elements))))
>       (map nil
>            #'(lambda (x)
>                (let ((x-key (funcall key x)))
>                  (cond ((funcall predicate x-key smallest-key)
>                         (setq smallest-elements (list x))
>                         (setq smallest-key x-key))
>                        ;; both elements are considered equal if the predicate
>                        ;; returns false for (PRED A B) and (PRED B A)
>                        ((not (funcall predicate smallest-key x-key))
>                         (push x smallest-elements)))))
>            (rest sequence))
>       (apply #'values smallest-elements)))

Here's my slightly less hackish code, based on yours:

 (defun extremum (sequence predicate &key (key #'identity) (start 0) end)
   (setf sequence (subseq sequence start end))
   (let* ((smallest-elements (list (elt sequence 0)))
          (smallest-key (funcall key (elt smallest-elements 0))))
     (map nil
          #'(lambda (x)
              (let ((x-key (funcall key x)))
                (cond ((funcall predicate x-key smallest-key)
                       (setq smallest-elements (list x))
                       (setq smallest-key x-key))
                      ;; both elements are considered equal if the predicate
                      ;; returns false for (PRED A B) and (PRED B A)
                      ((not (funcall predicate smallest-key x-key))
                       (push x smallest-elements)))))
          (subseq sequence 1))
     (apply #'values smallest-elements)))

This works with all proper sequences and accepts :start and :end
arguments. It's also a little slower than yours, and it doesn't
perform bounds checking (although that would be easy; I have a macro
which handles all that for cl-utilities).

These work as you would expect:
(extremum '(3 2 1 1 2 1) #'<)
(extremum #(3 2 1 1 2 1) #'<)
(extremum #(3 2 1 1 2 1) #'< :end 4)
(extremum #(3 2 1 1 2 1) #'< :start 3 :end 4)
(extremum '(3 2 1 1 2 1) #'< :end 4)

The complexity of that code bothers me, though. I worry about complex
code; it gives me feelings of looming bugs that are about to bite
me---or worse, bite someone else. Perhaps I can find a cleaner way to
write it if I put some more thought into it.

> Similiarly, I'd like to suggest a new function EXTREMA which returns the
> N "topmost" extrema:
>
>   CL-USER> (extrema 1 '(3 1 2 1) #'>)
>   (3)
>   CL-USER> (extrema 2 '(3 1 2 1) #'>)
>   (3 2)
>   CL-USER> (extrema 2 '(3 1 2 1) #'<)
>   (1 1)
>
>   CL-USER> (extrema 1 '((A . 3) (B . 1) (C . 2) (D . 1)) #'> :key #'cdr)
>   ((A . 3))
>   CL-USER> (extrema 2 '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr)
>   ((D . 1) (B . 1))

Pretty good idea.

> My version -- which can almost certainly be written many times
> simpler -- is:
> [snip]

As I was understanding this, I came up with a mental model: it simply
returned the first n elements of the sequence sorted with a certain
key and predicate. This immediately suggested a many times simpler
version:

(defun extrema (n sequence predicate &key (key #'identity))
  (subseq (sort (copy-seq sequence) predicate :key key)
          0 n))

One thing you might want to consider is the stability of your extrema
function, in the sense that quecksort is "unstable".

(my-extrema 2 '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr) =>
((B . 1) (D . 1))
(your-extrema 2 '((A . 3) (B . 1) (C . 2) (D . 1)) #'< :key #'cdr) =>
((D . 1) (B . 1))

My extrema function is stable in this case (by accident, since I
didn't ask for a stable sort) and yours is unstable. This can
sometimes be bad. I'll have to make -STABLE and regular versions.

My extrema function conses about twice as much as yours, but it's a
little faster on ACL 6.2 trial.

> Well, you'll hopefully get inspired. :-)

I have been. And once I get my big load of homework and exams worked
off, I'll inspire myself to actually make some changes to
cl-utilities. You've been a big help, thanks.

-Peter