Re: cl.el sort* efficiency

[Kevin Ryde]

Miles Bader <address@hidden> writes:
>
> Certainly the alternative of allocating storage to keep
> around all retrieved key values is pretty heavyweight and in many cases
> not an optimization at all,

I see your point, I guess there's two equally good features (an
accessor or a preprocessor), it's just a matter of which one is
offered.

Stefan Monnier <address@hidden> writes:
>
> Actually, I do believe that when I was a CL user I expected that the sort
> function would call the :key function only O(n) times rather than O(n log n)
> times.

At least I'm not the only one who thought in that direction :)

"Juanma Barranquero" <address@hidden> writes:
>
> Of course. I didn't meant that the idea was invented by Randal
> Schwartz, or recently; but it's very popular under that name.

No, confusion only on my part.  Not that the wiki article is
fantastically clear on concept versus the idiom (it's all there, but
rather laboured).


Without wanting to labour this sort* either :), I'd like to propose a
further tweak to the documentation.  In fact I think it's enough to
leave the code alone and just make it a little clearer what one gets.

2006-12-26  Kevin Ryde  <address@hidden>

        * cl.texi (Sorting Sequences): In sort*, don't say "preprocess" as
        that suggests O(N) :key use.  Show structs as an example, since
        downcase is more expensive than intended for the :key func.  Another
        tweak to the wording of :key only an accessor.

For ease of reading:

 -- Function: sort* seq predicate &key :key
     This function sorts SEQ into increasing order as determined by
     using PREDICATE to compare pairs of elements.  PREDICATE should
     return true (non-`nil') if and only if its first argument is less
     than (not equal to) its second argument.  For example, `<' and
     `string-lessp' are suitable predicate functions for sorting
     numbers and strings, respectively; `>' would sort numbers into
     decreasing rather than increasing order.

     This function differs from Emacs' built-in `sort' in that it can
     operate on any type of sequence, not just lists.  Also, it accepts
     a `:key' argument which is used to access part of an element for
     the PREDICATE function.  For example, to sort structures by a
     particular field (*note Structures::)

          (defstruct person name age sex)

          (setq data (sort* data 'string-lessp :key 'person-name))

     Or `car' would be useful for sorting association lists.  The
     `:key' function is designed only as a data accessor though, it's
     used on every predicate call.

     The `sort*' function is destructive; it sorts lists by actually
     rearranging the `cdr' pointers in suitable fashion.

cl.texi.sort-2.diff
Description: Text Data