From: Robert Klemme <shortcutter@...>
Date: 2012-01-19T18:22:10+09:00
Subject: Re: Elegant expression of sorting

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.

> 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

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)
}

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
  ]
}

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

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/