I have a list of where the elements are of type struct and I would like to
sort the list based upon the contents of one of the slots in the structure.
I have searched, in vain, for the syntax, can anyone advise?
* "Jeff Undercoffer" <············@home.com>
| I have a list of where the elements are of type struct and I would like to
| sort the list based upon the contents of one of the slots in the structure.
|
| I have searched, in vain, for the syntax, can anyone advise?
What have you tried so far? And what is the name of the slot accessor?
///
"Jeff Undercoffer" <············@home.com> writes:
> I have a list of where the elements are of type struct and I would like to
> sort the list based upon the contents of one of the slots in the structure.
>
> I have searched, in vain, for the syntax, can anyone advise?
Check the CLHS entry for SORT,
<http://www.xanalys.com/software_tools/reference/HyperSpec/Body/fun_sortcm_stable-sort.html>,
and read about the PREDICATE and KEY arguments. IMHO this is the first
place to look at, so you probably didn't search very long...
"Jeff Undercoffer" <············@home.com> writes:
> I have a list of where the elements are of type struct and I would like to
> sort the list based upon the contents of one of the slots in the structure.
(sort list #'predicate :key #'slot-accessor)
See <http://www.xanalys.com/software_tools/reference/HyperSpec/Body/fun_sortcm_stable-sort.html>.
--
Pekka P. Pirinen
The Risks of Electronic Communication
<http://www.best.com/~thvv/emailbad.html>
> (sort list #'predicate :key #'slot-accessor)
While we're on the subject, is there a standard idiom in Lisp for sorting
using primary and secondary (and tertiary, etc) keys? Say I have:
(defstruct person
last-name
first-name)
and want to sort by last-name, but within last-name by first-name.
In article <············@suaar1ac.prod.compuserve.com>,
Roy Mash <········@ci.sf.ca.us> wrote:
>> (sort list #'predicate :key #'slot-accessor)
>
>While we're on the subject, is there a standard idiom in Lisp for sorting
>using primary and secondary (and tertiary, etc) keys? Say I have:
> (defstruct person
> last-name
> first-name)
>and want to sort by last-name, but within last-name by first-name.
Nothing very concise. You can't use :KEY in this case, you just have to
write a comparison predicate that checks both keys:
(defun person-< (p1 p2)
(if (string= (person-last-name p1) (person-last-name p2))
(string< (person-first-name p1) (person-first-name p2))
(string< (person-last-name p1) (person-last-name p2))))
What would be nice would be a version of SORT that accepted an arbitrary
number of keys and predicates:
(multi-key-sort sequence #'key1 #'predicate1 #'key2 #'predicate2 ...)
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin <······@genuity.net> writes:
>
> In article <············@suaar1ac.prod.compuserve.com>,
> Roy Mash <········@ci.sf.ca.us> wrote:
> >> (sort list #'predicate :key #'slot-accessor)
> >
> >While we're on the subject, is there a standard idiom in Lisp for sorting
> >using primary and secondary (and tertiary, etc) keys? Say I have:
> > (defstruct person
> > last-name
> > first-name)
> >and want to sort by last-name, but within last-name by first-name.
>
> Nothing very concise. You can't use :KEY in this case, you just have to
> write a comparison predicate that checks both keys:
>
> (defun person-< (p1 p2)
> (if (string= (person-last-name p1) (person-last-name p2))
> (string< (person-first-name p1) (person-first-name p2))
> (string< (person-last-name p1) (person-last-name p2))))
>
> What would be nice would be a version of SORT that accepted an arbitrary
> number of keys and predicates:
>
> (multi-key-sort sequence #'key1 #'predicate1 #'key2 #'predicate2 ...)
This was talked about recently so I should probably just point to Deja
News for my point of view. Personally, I just do
(stable-sort (sort thing #'string-lessp :key #'person-first-name)
#'string-lessp :key #'person-last-name)
though it's less efficient. It really depends on whether you're
compute-bound for this operation as to how much you have to trade off
coding for aesthetics. What Barry suggests is *probably* a bit faster
since it does only one sort instead of two. Then again, the
algorithmic complexity isn't necessarily that different, since we may
be talking a constant factor of two (where each step is less expensive
for doing fewer compares) UNLESS the effect of the first sort is to
de-optimize the second sort, and I'm not sure you can know the answer
to that portably... could go either way.
Sorts are weird things to optimize and I don't do it a lot. As I
recall, if you really carea bout speed you have to worry about other
strange things like whether knowing it is mostly sorted or mostly not
sorted does something bad to the time expected...
Mostly I just leave this to metering and see if it matters before
stressing a lot. I've found a few places where it does matter enormously,
and many others where it doesn't matter at all.