Re: cl.el sort* efficiency

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

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

"Juanma Barranquero" <lekktu@gmail.com> writes:
>
> You're implementing a Schwartzian Transform
> (http://en.wikipedia.org/wiki/Schwartzian_transform) inside sort*,
> which is kinda odd.

The concept would pre-date 1994, wouldn't it?  (Not that this is the
place for questions of academic priority :-)

> IMHO is the responsibility of the user of sort* to know whether
> comparisons are going to be expensive and preprocess the data to help
> in the comparison.

A key func as data accessor seemed to me a reasonably natural way to
express that, but maybe that's just me.

> You're doing an optimization at the wrong level:
> perhaps I'm using it with so light a comparison function that your
> method makes it more expensive...

I see the common lisp spec specifically doesn't say how much or little
the key is used.  Dunno what you get from implementations in practice.
Is there a CL expert in the house?


In any case Richard advises not doing anything to emacs at this time,
but I would propose a sentence for the manual, just to describe what's
current.

2006-12-24  Kevin Ryde  <user42@zip.com.au>

	* cl.texi (Sorting Sequences): In sort*, add a little cautionary note
	about the key procedure being used heavily.


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

Index: cl.texi
===================================================================
RCS file: /sources/emacs/emacs/man/cl.texi,v
retrieving revision 1.30
diff -u -c -r1.30 cl.texi
cvs diff: conflicting specifications of output style
*** cl.texi	22 Dec 2006 23:27:28 -0000	1.30
--- cl.texi	24 Dec 2006 00:43:47 -0000
***************
*** 4092,4098 ****
  @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.
  
  The @code{sort*} function is destructive; it sorts lists by actually
  rearranging the @code{cdr} pointers in suitable fashion.
--- 4092,4100 ----
  @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.

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

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