Re: cl.el sort* efficiency

[Kevin Ryde <user42@zip.com.au>]

[-- Attachment #1: Type: text/plain, Size: 2712 bytes --]

Miles Bader <miles@gnu.org> 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 <monnier@iro.umontreal.ca> 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" <lekktu@gmail.com> 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  <user42@zip.com.au>

	* 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.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: cl.texi.sort-2.diff --]
[-- Type: text/x-diff, Size: 1706 bytes --]

*** cl.texi.~1.31.~	2006-12-26 11:20:21.000000000 +1100
--- cl.texi	2006-12-26 11:24:08.000000000 +1100
***************
*** 4082,4100 ****
  
  This function differs from Emacs' built-in @code{sort} in that it
  can operate on any type of sequence, not just lists.  Also, it
! accepts a @code{:key} argument which is used to preprocess data
! fed to the @var{predicate} function.  For example,
  
  @example
! (setq data (sort* data 'string-lessp :key 'downcase))
  @end example
  
  @noindent
! sorts @var{data}, a sequence of strings, into increasing alphabetical
! order without regard to case.  A @code{:key} function of @code{car}
! would be useful for sorting association lists.  It should only be a
! simple accessor though, it's used heavily in the current
! implementation.
  
  The @code{sort*} function is destructive; it sorts lists by actually
  rearranging the @code{cdr} pointers in suitable fashion.
--- 4082,4101 ----
  
  This function differs from Emacs' built-in @code{sort} in that it
  can operate on any type of sequence, not just lists.  Also, it
! accepts a @code{:key} argument which is used to access part of an
! element for the @var{predicate} function.  For example, to sort
! structures by a particular field (@pxref{Structures})
  
  @example
! (defstruct person name age sex)
! 
! (setq data (sort* data 'string-lessp :key 'person-name))
  @end example
  
  @noindent
! Or @code{car} would be useful for sorting association lists.  The
! @code{:key} function is designed only as a data accessor though, it's
! used on every predicate call.
  
  The @code{sort*} function is destructive; it sorts lists by actually
  rearranging the @code{cdr} pointers in suitable fashion.

[-- Attachment #3: Type: text/plain, Size: 142 bytes --]

_______________________________________________
Emacs-devel mailing list
Emacs-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/emacs-devel