Source

topn /

Filename Size Date modified Message
1.1 KB
1.2 KB
378 B
472 B
111 B
519 B
700 B
This small project provides benchmarking for various approaches to
implementing the following function:

Array#topn(n) { |a,b| } => ary

where	n	is the maximum number of elements to select
	ary	is an array containing the top n elements

The block should return:
-1 if a is ahead of b
 0 if they are equal
 1 if a is after b

The returned array does not have to be sorted itself, it merely
must contain the top n items.

I've supplied three versions of this method:

topn0.rb	the obvious sort and slice
topn1.rb	collect only the top n by insertion sort
topn2.rb	collect only the top n, without sorting

If also provided the following two benchmark harnesses:

test_ruby.rb	uses the 'profiler' module for Ruby
test_rbx.rb	uses the -Xprofile option for Rubinius

Invoke either of these at the command line, specifying the
version of the method to use as the first argument.  An optional
second argument is the number of top items to collect (default = 15),
and the optional third argument is the maximum size of the array to
test (default = 100).

Using Ruby 1.8.7, topn0.rb beats the others hands down in my testing.
Surprisingly, with Rubinius this approach is the slowest of the three.
Apparently, Rubinius' quicksort algorithm needs improving.