From: Florian Frank <flori@...>
Date: 2004-10-05T03:25:19+09:00
Subject: Re: How to sort a table in Ruby?

On 04.10.2004, at 15:04, Gavin Kistner wrote:
> The reason that #sort_by is better than #sort is described in the 
> documentation. In short (IIRC) it's because it caches the key values 
> for each row (performing the block only once for each row) and uses 
> those to sort, rather than invoking the block for every unique pair it 
> has to compare.

sort_by is only better if creating a temporary array of length n for 
sort keys is faster than yielding the block or calling the <=> method 
on elements ca. n*log(n) times. In theory this is always computational 
faster but not necessarily on real machines that have to manage the 
required memory. Using sort! instead of sort also can make a 
difference.

The trade-off leans towards sort_by if the computations of the keys is 
really slow (like accessing the filesystem or doing a dns-lookup) or if 
comparing the computed keys is much faster than comparing the elements 
directly. The last case can be used to speed up a sort by computing a 
string of a complex object which can be compared more efficiently than
comparing the objects themselves. An interesting article on this topic 
is "A Fresh Look at Efficient Perl Sorting" by Uri Guttman and Larry 
Rosler, even if it's quite perl-centric:
	http://www.sysarch.com/perl/sort_paper.html

> A downside, however, is the inability to specify something like a 
> reverse sort. (Although for that case you can just reverse the array 
> afterwards.)

If your elements respond to a meaningful unary - you can do something 
like
	[1,3,4,2,5].sort_by { |x|  -x }
for reverse sorting.

> Actually, does anyone have a compelling example where #sort produce a 
> result (which is reasonable) which #sort_by cannot? (By 'reasonable' I 
> mean that something like a.sort{ |x,y| x[3] <=> y[7] } does something 
> impossible for #sort_by, but probably would produce erratic results, 
> given no way of knowing in which order the pairs come.)

Well, you could always cheat like in this reverse sort example:

class Cheat < Struct.new(:a)
   def <=>(other) other.a <=> a end
end

[1,3,4,2,5].sort_by { |x| Cheat.new(x) }

Florian Frank