Hello,
I have an array which elements are LIST as below.
#((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)) ; let's call it ARRAY
I would like to sort the array by second element of each list.
(stable-sort array #'> :key #'cadr))
So, now I can sort the array as
#((2 7 1) (3 7 4) (1 3 5) (5 3 8) (9 1 3))
However, I have two seven and three respectively in the second element,
so I want to sort it by the first element.
Desired result should be
#((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
Is there any way to sort partially as above?
I can't find any example from CL references.
Thanks alot.
Sungwoo
"Sungwoo Lim" <·······@cad.strath.ac.uk> wrote in message
·······························@cad.strath.ac.uk...
> Hello,
>
> I have an array which elements are LIST as below.
>
> #((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)) ; let's call it ARRAY
>
> I would like to sort the array by second element of each list.
>
> (stable-sort array #'> :key #'cadr))
>
> So, now I can sort the array as
>
> #((2 7 1) (3 7 4) (1 3 5) (5 3 8) (9 1 3))
>
> However, I have two seven and three respectively in the second element,
> so I want to sort it by the first element.
> Desired result should be
>
> #((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
>
> Is there any way to sort partially as above?
> I can't find any example from CL references.
> Thanks alot.
>
> Sungwoo
>
You just need to write your own test function. If you'll be using that same
criterion elsewhere, give it a name and use that instead of #'> if it's of
local interest only use a lambda:
CL-USER 22 > (setf array #((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)) )
#((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3))
CL-USER 23 > (stable-sort array #'(lambda (list1 list2)
(or (> (cadr
list1) (cadr list2))
(and (=
(cadr list1) (cadr list2))
(>
(car list1) (car list2))))))
#((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
I think you just want
(defun funky-sort (seq)
(stable-sort seq #'(lambda (a b)
(let ((primary-a (cadr a))
(primary-b (cadr b)))
(if (= primary-a primary-b)
(> (car a) (car b))
(> primary-a primary-b))))))
Tim
On Wed, 1 Aug 2001, Sungwoo Lim wrote:
> Hello,
>
> I have an array which elements are LIST as below.
>
> #((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)) ; let's call it ARRAY
>
> I would like to sort the array by second element of each list.
>
> (stable-sort array #'> :key #'cadr))
>
> So, now I can sort the array as
>
> #((2 7 1) (3 7 4) (1 3 5) (5 3 8) (9 1 3))
>
> However, I have two seven and three respectively in the second element,
> so I want to sort it by the first element.
> Desired result should be
>
> #((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
>
> Is there any way to sort partially as above?
> I can't find any example from CL references.
> Thanks alot.
>
> Sungwoo
>
>
In article <··························@cad.strath.ac.uk>, Sungwoo Lim wrote:
>#((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
>
>Is there any way to sort partially as above?
You can sort on the first list element, followed by sorting on
the second:
(stable-sort array #'> :key #'first)
(stable-sort array #'> :key #'second)
In the second sort, whenever two lists match in their second element,
their existing order will be preserved. That property is what ``stable''
means in ``stable sort''.
Another solution is to not rely on the sort stability, but rather do it
in one pass. To do that, define an ordering relation which disambiguates
lists that have a common second element. This means writing an
alternate comparison function instead of using #'>
Example:
(defun greaterp (left-list right-list)
(if (eql (second left-list) (second right-list))
(> (first left-list) (first right-list))
(> (second left-list) (second right-list))))
(defvar *array* #((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)))
(stable-sort *array* #'greaterp)
Sungwoo Lim <·······@cad.strath.ac.uk> writes:
> Hello,
>
> I have an array which elements are LIST as below.
>
> #((1 3 5) (5 3 8) (2 7 1) (3 7 4) (9 1 3)) ; let's call it ARRAY
>
> I would like to sort the array by second element of each list.
>
> (stable-sort array #'> :key #'cadr))
>
> So, now I can sort the array as
>
> #((2 7 1) (3 7 4) (1 3 5) (5 3 8) (9 1 3))
>
> However, I have two seven and three respectively in the second element,
> so I want to sort it by the first element.
> Desired result should be
>
> #((3 7 4) (2 7 1) (5 3 8) (1 3 5) (9 1 3))
>
> Is there any way to sort partially as above?
> I can't find any example from CL references.
> Thanks alot.
>
(stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
That is, first sort by the secondary key.
Then, do a stable-sort which preserves that ordering in the equal cases
but perturbs things in the case of a dominating primary key.
>>>>> On Wed, 1 Aug 2001 18:36:22 GMT, Kent M Pitman <······@world.std.com> wrote:
> (stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
I am not sure what kind of performance hit this statement involves.
Same goes for the if-laden functions. I always do something like
this (not only in Lisp!) that involves only 1 pass to form a key:
(defun my-sort (el) (+ (car el) (* 10 (cadr el)))
(sort ARRAY #'> :key #'my-sort)
This trick works unconditionally on chars and ints, and if you're
trying to do this with floats of unknown magnitude - you're doing
something wrong.
--ET.
In article <······················@dfw-read.news.verio.net>, MeanGene wrote:
>>>>>> On Wed, 1 Aug 2001 18:36:22 GMT, Kent M Pitman <······@world.std.com> wrote:
>
>> (stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
>
>I am not sure what kind of performance hit this statement involves.
>Same goes for the if-laden functions. I always do something like
>this (not only in Lisp!) that involves only 1 pass to form a key:
>
>(defun my-sort (el) (+ (car el) (* 10 (cadr el)))
>(sort ARRAY #'> :key #'my-sort)
>
>This trick works unconditionally on chars and ints, and if you're
>trying to do this with floats of unknown magnitude - you're doing
>something wrong.
What if you get this input:
#( '(1 10) '(100 1) )
According to your formula, the ranks assigned to these lists would be:
101 110
This is wrong, because a list whose second element ranks greater than the
second element of another list must be considered greater, no matter what
the magnitude is of the first element. So '(1 10) must have a greater
rank than '(100 1).
It's not enough to say that the second element has ten times the weight
of the first. That kind of arithmetic coding works when the numbers
are known to have a confined range. E.g. if the lists contain only the
values 0 through 9, then you can treat them codes for decimal integers,
using that interpretation to assign a rank which can be used to
sort them.
···@ashi.footprints.net (Kaz Kylheku) writes:
> In article <······················@dfw-read.news.verio.net>, MeanGene wrote:
>
> >(defun my-sort (el) (+ (car el) (* 10 (cadr el)))
> >(sort ARRAY #'> :key #'my-sort)
> >
> >This trick works unconditionally on chars and ints, and if you're
> >trying to do this with floats of unknown magnitude - you're doing
> >something wrong.
>
> What if you get this input:
>
> #( '(1 10) '(100 1) )
>
> According to your formula, the ranks assigned to these lists would be:
>
> 101 110
>
> This is wrong, because a list whose second element ranks greater than the
> second element of another list must be considered greater, no matter what
> the magnitude is of the first element. So '(1 10) must have a greater
> rank than '(100 1).
But you missed where he added the caveat that you need to know the
magnitude of the numbers involved. Where he wrote "10" in the
original, it should say magnitude-of-greatest-key. So in your example
that would be 100:
#((1 10) (100 1))
^ ^
+-1001 +-200
=> #((1 10) (100 1))
which is correct.
I'm not so sure about this assertion, though:
> > and if you're trying to do this with floats of unknown magnitude -
> > you're doing something wrong.
In article <···············@conquest.OCF.Berkeley.EDU>,
Thomas F. Burdick <···@conquest.OCF.Berkeley.EDU> wrote:
>···@ashi.footprints.net (Kaz Kylheku) writes:
>
>> In article <······················@dfw-read.news.verio.net>, MeanGene wrote:
>>
>> >(defun my-sort (el) (+ (car el) (* 10 (cadr el)))
>> >(sort ARRAY #'> :key #'my-sort)
>> >
>> >This trick works unconditionally on chars and ints, and if you're
>> >trying to do this with floats of unknown magnitude - you're doing
>> >something wrong.
>>
>> What if you get this input:
>>
>> #( '(1 10) '(100 1) )
>>
>> According to your formula, the ranks assigned to these lists would be:
>>
>> 101 110
>>
>> This is wrong, because a list whose second element ranks greater than the
>> second element of another list must be considered greater, no matter what
>> the magnitude is of the first element. So '(1 10) must have a greater
>> rank than '(100 1).
>
>But you missed where he added the caveat that you need to know the
>magnitude of the numbers involved.
Where did he say that? The only caveat he mentioned was with floats.
I suspect that this method doesn't provide any performance improvement over
the :TEST function that contains an IF. Instead of doing a condition test
for each comparison, it performs two multiplications before each comparison
(unless the implementation of SORT caches the keys instead of calling the
key function repeatedly). The version with the conditional only needs to
look at the secondary keys in cases where two elements have the same
primary key.
--
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.
Well, first of all - it's was implicit in my posting that in real life
you'd have to use something like MAX_INT instead of 10 in this toy example.
Anyway, here's my completely unscientific attempt at timing these methods
(from a compiled file, of course):
(time (loop for n from 1 to 1000000 do (tim-sort *array*))
Evaluation took:
2.97 seconds of real time
2.63 seconds of user run time
0.16 seconds of system run time
[Run times include 0.5 seconds GC run time]
0 page faults and
32042856 bytes consed
(time (loop for n from 1 to 1000000 do (wolfhard-sort *array*))
Evaluation took:
3.02 seconds of real time
2.68 seconds of user run time
0.14 seconds of system run time
[Run times include 0.49 seconds GC run time]
0 page faults and
32035496 bytes consed
(time (loop for n from 1 to 1000000 do (ken-sort *array*))
Evaluation took:
13.43 seconds of real time
10.57 seconds of user run time
0.95 seconds of system run time
[Run times include 2.94 seconds GC run time]
0 page faults and
192242064 bytes consed.
(time (loop for n from 1 to 1000000 do (gene-sort *array*))
Evaluation took:
6.69 seconds of real time
5.62 seconds of user run time
0.37 seconds of system run time
[Run times include 1.45 seconds GC run time]
0 page faults and
96120760 bytes consed
"Eduardo Mu�oz" <···@jet.es> writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > (stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
>
> Really elegant, I *must* say.
But doesn't perform as well (unless the compiler is *really* smart).
···@itasoftware.com writes:
> "Eduardo Mu�oz" <···@jet.es> writes:
>
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > (stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
> >
> > Really elegant, I *must* say.
>
> But doesn't perform as well (unless the compiler is *really* smart).
Yes, certainly, you can always do things in a more ugly way if they
become performance bottlenecks. But I don't think that should be your
first impulse in many cases that are not in high-stress inner loops.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>···@itasoftware.com writes:
>
>> "Eduardo Mu�oz" <···@jet.es> writes:
>>
>> > Kent M Pitman <······@world.std.com> writes:
>> >
>> > > (stable-sort (sort array #'> :key #'car) #'> :key #'cadr)
>> >
>> > Really elegant, I *must* say.
>>
>> But doesn't perform as well (unless the compiler is *really* smart).
>
>Yes, certainly, you can always do things in a more ugly way if they
>become performance bottlenecks. But I don't think that should be your
>first impulse in many cases that are not in high-stress inner loops.
Actually, I'm not so sure that the performance would be that bad. I'm not
sure what the performance difference between stable and non-stable sorts
are (I presume stable sorts are generally slower, since most popular
sorting functions are non-stable, but I don't know how much slower).
Ignoring the difference in performance, the above mechanism simply doubles
the time. If you complicate the comparison and/or key function enough that
they takes more than twice as long as the corresponding functions in the
above expression, a single sort using these comparison/key functions will
be just as slow.
There's a non-negligible chance that a compiler may recognize calls to SORT
that use common comparison functions like #'>, and generate code that
performs the tests inline rather than doing full funcalls. So nesting some
sorts that can be optimized could be better than doing a single sort that
makes use of a user-defined function.
--
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.
In article <··························@cad.strath.ac.uk>, Sungwoo Lim
<·······@cad.strath.ac.uk> wrote:
Thanks for the all advices from all of you.
These are really helpful. =0)
Sungwoo