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> =A0wrote:
>>>
>>> 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|
>>> =A0# Ascending, primary.
>>> =A0rv =3D a.key0<=3D> =A0b.key0
>>> =A0# Descending, secondary.
>>> =A0rv =3D b.key1<=3D> =A0a.key1 if rv =3D=3D 0
>>> =A0# A tricky and expensive comparison, tertiary.
>>> =A0rv =3D a.magic(b) if rv =3D=3D 0
>>> =A0rv
>>> }
>>>
>>> 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 a=
nd
>>> clearer to read.

>> A general way to perform a multi-key sort is:
>> # assuming sort() is a stable sort algorithm, e.g. merge sort
>> =A0 foo.sort! {|a,b|
>> =A0 =A0 =A0# starting from the least important key
>> =A0 =A0 =A0a.magic(b)
>> =A0 }
>> =A0 foo.sort! {|a,b|
>> =A0 =A0 =A0# sort again using the second-least important key
>> =A0 =A0 =A0b.key1<=3D> =A0a.key1
>> =A0 }
>> =A0 # 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 !=3D 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 st=
ill
> 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 <=3D> b.key0).nonzer0? ||
 # Descending, secondary.
 (b.key1 <=3D> 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 =3D lambda {|a| [a.key0, -a.key1, a.create_magic_key]}
YourClass::SORT_BAR =3D lambda {|a,b| (a.key0 <=3D> b.key0).nonzero? || ...=
 }

enum.sort_by &YourClass::SORT_FOO
enum.sort &YourClass::SORT_BAR

Kind regards

robert

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