From: Steve Howell <showell30@...>
Date: 2010-10-14T23:06:38+09:00
Subject: Re: sort_by: multiple fields with reverse sort

On Oct 13, 10:50 pm, Jeremy Bopp <jer...@bopp.net> wrote:
> On 10/13/2010 09:50 PM, Steve Howell wrote:
>
>
>
> > It would be nice if Ruby supported a sort_by on steroids.
>
> >   sorted_list = list.multi_field_sort_by(
> >     { |x| x.department.name },
> >     { |x| x.position.name },
> >     desc { |x| x.level },
> >     desc { |x| x.salary ? x.salary : x.rate * db_lookup(x,
> > 'hours_worked') }
> >   )
>
> > I believe you could write a decent multi_field_sort_by in Ruby that
> > would be efficient for large enough lists to outperform more tedious
> > approaches, but it would be even better if Ruby natively supported it.
>
> > My proposed syntax might be slightly off, but you get the idea.  You'd
> > pass a list of blocks that represent the successive tiebreakers, and
> > multi_field_sort_by would presumably cache the results from each
> > transformation, evaluating the blocks only as necessary.  The "desc"
> > thingy would actually produce some kind of wrapper that
> > multi_field_sort_by could introspect to know that it needs to apply a
> > particular tiebreaker in reverse order.
>
> How about something like this:
>
> module Enumerable
>   # sort_by will take a key generator and an optional comparator
>   # and perform a Schwartzian Transform over the data.
>   #
>   # This is a general solution which is relatively inefficient than
>   # a purpose-built sorting function if the keys are trivial to
>   # generate.
>   def sort_by(cmp = lambda { |a, b| a <=> b }, &key)
>     collect do |item|   # Generate keys from the list items.
>       [key[item], item]
>     end.sort do |a, b|  # Sort the keys.
>       cmp[a[0], b[0]]
>     end.collect do |kv| # Return the items in key sort order.
>       kv[1]
>     end
>   end
> end
>
> # This will cause the sort to operate over the second and then
> # the first column.
> key = lambda { |item| [item[1], item[0]] }
>
> # This will cause the sort to operate normally on the second
> # column and in reverse on the first column.
> cmp = lambda do |a, b|
>         res = a[0] <=> b[0]
>         break res unless res == 0
>         b[1] <=> a[1]
>       end
>
> # Sample data from Ryan's post.
> a = [
>   ["radio", 30, 5],
>   ["radio", 20, 5],
>   ["archie", 20, 5],
>   ["newton", 10, 3]
> ]
>
> # Sort over the second and then first columns each in normal order.
> p a.sort_by(&key)
> # => [["newton", 10, 3], ["archie", 20, 5], ["radio", 20, 5],
> #                                                  ["radio", 30, 5]]
>
> # Sort over the second column in normal order and then the first
> # column in reverse order.
> p a.sort_by(cmp, &key)
> # => [["newton", 10, 3], ["radio", 20, 5], ["archie", 20, 5],
> #                                                  ["radio", 30, 5]]

I think it's a good start, but it still requires you to write a
somewhat customized cmp function.  A truly optimized multi-field sort
might also be able to avoid calculating all elements of the key as
well, since they are often only needed as tiebreakers.