From: Robert Klemme <shortcutter@...>
Date: 2007-10-08T18:51:05+09:00
Subject: Re: #sort_by and #sort_obj

2007/10/8, Eric Hodel <drbrain@segment7.net>:
> On Oct 7, 2007, at 03:34 , Trans wrote:
> > On Oct 7, 2:21 am, Eric Hodel <drbr...@segment7.net> wrote:
> >> I haven't seen this technique in the wild before.
> >>
> >> If you have custom sorting using the spaceship:
> >>
> >> class Something
> >>    def <=>(other)
> >>      [@name, @version] <=> [other.name, other.version]
> >>    end
> >> end
> >>
> >> You can't easily use the more-efficient #sort_by because you'll need
> >> to know how to sort Somethings, which involves duplication:
> >>
> >> somethings.sort_by { |s| [s.name, s.version] }
> >>
> >> Instead you can add a method that returns the thing to sort by:
> >>
> >> class Something
> >>    def sort_obj
> >>      [@name, @version]
> >>    end
> >>
> >>    def <=>(other)
> >>      sort_obj <=> other.sort_obj
> >>    end
> >> end
> >>
> >> So now using #sort_by is easy:
> >>
> >> somethings.sort_by { |s| s.sort_obj }
> >>
> >> I don't know if the name #sort_obj is appropriate, but I'm not coming
> >> up with something better.
> >>
> >> See also:
> >>
> >> http://blog.segment7.net/articles/2007/10/07/sort_by-and-sort_obj
> >
> > Nice. In fact, it seems this could dethrone <=> as the primary method
> > Sortable depends on.
>
> My primary goal was reducing the number of method calls and objects
> created, boosting speed.

I'm afraid the performance issue is not that easy: I can imagine where
the <=> approach is more efficient. Here's the reason: with #sort_by
you need to keep *all* keys in memory for the whole sorting process
which can cost a lot of memory.  Creating those for pairwise
comparison (as with <=>) is more CPU intensive because more temp
arrays have to be created but the overall memory usage might be lower
because they are kept during a single comparison operation only (see
also Rick's benchmark). Allocating that much memory from the OS for
the #sort_by case might actually slow the sorting down dramatically.

>  The downside to this is that you can't sort
> heterogeneous collections using #sort_obj.  When sorting using #<=>
> this would be easier.

Not necessarily because the <=> operators might not be able to work
with elements from the other types and thus sorting might fail as
miserably. :-)

Kind regards

robert