From: Garthy D <garthy_lmkltybr@...>
Date: 2012-01-19T19:49:04+09:00
Subject: Re: Elegant expression of sorting


Hi Robert,

On 19/01/12 19:52, Robert Klemme wrote:
> On Thu, Jan 19, 2012 at 10:09 AM, Garthy D
> <garthy_lmkltybr@entropicsoftware.com>  wrote:
>> On 19/01/12 16:35, Yong Li wrote:
>>>
>>> On Thu, Jan 19, 2012 at 8:58 AM, Garthy D
>>> <garthy_lmkltybr@entropicsoftware.com>    wrote:
>>>>
>>>> Hi all,
>>>>
>>>> I've found that for the current project I am working on that I am
>>>> frequently
>>>> doing sorts based on multiple keys. The comparisons on each key tend to
>>>> vary, ie. sometimes I want descending rather than ascending, and other
>>>> times
>>>> the comparison itself is complex.
>>>>
>>>> I usually do something like this:
>>>>
>>>> foo.sort! {|a,b|
>>>>   # Ascending, primary.
>>>>   rv = a.key0<=>    b.key0
>>>>   # Descending, secondary.
>>>>   rv = b.key1<=>    a.key1 if rv == 0
>>>>   # A tricky and expensive comparison, tertiary.
>>>>   rv = a.magic(b) if rv == 0
>>>>   rv
>>>> }
>>>>
>>>> Does anyone have any suggestions as to a more elegant way to express
>>>> this?
>>>> I'm after something that is logically equivalent, but easier to write and
>>>> clearer to read.
>
>>> A general way to perform a multi-key sort is:
>>> # assuming sort() is a stable sort algorithm, e.g. merge sort
>>>    foo.sort! {|a,b|
>>>       # starting from the least important key
>>>       a.magic(b)
>>>    }
>>>    foo.sort! {|a,b|
>>>       # sort again using the second-least important key
>>>       b.key1<=>    a.key1
>>>    }
>>>    # repeat until you are done with the most important key
>>>
>>> I guess you can generalize this using an array of Lambdas.
>>> One potential disadvantage of this for your particular case is that,
>>> a.magic(b) is always performed even if a.key0 != b.key0. As you have
>>> stated, this is quite expensive, and can make the above general scheme
>>> much more expensive than your way.
>
> This is totally inefficient because it goes through the original data
> set (which might be large) multiple times.  The complexity of #magic
> only adds to this.

Very true.

>> Cool- thanks for that. I won't be able to use it directly as the last key
>> sort for most of the things I am doing is typically expensive, but I'm still
>> quite interested in different possible approaches. Thankyou. :)
>
> Please don't, there are much better approaches (see botp's for
> example).  Here are more

Yes, it's not directly suitable for what I'm doing but the different 
approach was interesting- there are cases where I might be able to have 
the input come in already sorted against one of the keys without cost. 
It got me thinking, anyway.

> foo.sort! {|a,b|
>   # Ascending, primary.
>   (a.key0<=>  b.key0).nonzer0? ||
>   # Descending, secondary.
>   (b.key1<=>  a.key1).nonzero? ||
>   # A tricky and expensive comparison, tertiary.
>   a.magic(b)
> }

Very, very neat; and nice find on "nonzero?". :) My first thought was 
that "nonzero?" surely returns a boolean and this would break it- but it 
looks like "nonzero?" with numeric return was designed for this *exact* 
problem. :)

I was wondering if there was a nice way to drop the "rv" from my 
solution- this looks like the best way.

> foo.sort_by {|a|
>    [
>    # Ascending, primary.
>    a.key0,
>    # Descending, secondary, only if numeric.
>    -a.key1,
>     # A tricky and expensive comparison, tertiary.
>    a.create_magic_key
>    ]
> }

I'd stumbled on sort_by initially, I suspect I'll use it when I can 
precompute the comparisons easily (this is sometimes the case, sometimes 
not).

> All these approaches can also be stored in a lambda and used from there
>
> YourClass::SORT_FOO = lambda {|a| [a.key0, -a.key1, a.create_magic_key]}
> YourClass::SORT_BAR = lambda {|a,b| (a.key0<=>  b.key0).nonzero? || ... }
>
> enum.sort_by&YourClass::SORT_FOO
> enum.sort&YourClass::SORT_BAR

Excellent stuff. :)

I'm not at all familiar with the "enum.sort_by&YourClass::SORT_FOO" 
syntax at this point, so I might need to read up on that. I can at least 
partly guess from the context though.

Thankyou for your very detailed input on this one, excellent stuff! :)

Garth