Re: Is high-speed sorting impossible with Ruby?

Just playing with the code a little, more education than speed.

On 28.11.2011 09:05, Ryan Davis wrote:
>    $stdin.gets
>    puts $stdin.readlines.map(&:to_i).sort

Your solution could be written like

> $stdin.gets
>
> a = $stdin.readlines
> b = a.map(&:to_i)
> c = b.sort
>
> puts c

while processing of a, b, and c is completely sequential. All three 
objects created are arrays full of data: a contains all string lines 
read in, b makes all these entries into integers, c is the same sorted. 
Three large arrays. All sequentially processed.

A similar solution, at first glance only marginally different, is the 
following:

> $stdin.gets
> puts $stdin.each_line.sort_by(&:to_i)

Besides the fact that this solution is slower than yours, it uses a neat 
little technique of Ruby 1.9, Enumerators. Here, only a single big array 
is created, which is the result array. IO#each_line() does not read in 
the whole file at once but provides an Enumerator – iteration fiber – 
that passes each read line to the .sort_by() call _while they are read_. 
Only sort_by will exhaustively fetch the items and eventually sort them 
based on the sorting criteria.

Driving pipelining with the Enumerators to the max, we need a filter 
chain. Let’s set up a generic filter (which is still not there in 
Enumerator?) similar to the one described ages ago in issue #707 
[http://redmine.ruby-lang.org/issues/707]

> class Enumerator
>   def filter1(&blk)
>     self.class.new do |y|
>       each do |*input|
>         y << blk.call(*input)
>       end
>     end
>   end
> end
>
> $stdin.gets
> puts $stdin.each_line.filter1(&:to_i).sort

Let’s expand the last line into smaller chunks, similar to the 
explanation of your code:

> a = $stdin.each_line
> b = a.filter1(&:to_i)
> c = b.sort
>
> puts c

Now, walking the code, nothing really happens until we hit b.sort – the 
creation of the objects a and b will just setup the filter chain and not 
yet pull any data from $stdin. Once called on an Enumerator, #sort 
cannot perform its action and return even a single entry before knowing 
all entries, so it will call up b.next until it receives a 
»StopIteration« exception. But for b to return a new value, it first has 
to apply .to_i to the next value on its input, which is again an 
iterator, a. So next is the call to a.next which will return the first 
line read from $stdin. Finally we can walk our way back to sort: The 
vaue is returned to the filter so it can be converted (to_i) and 
returned from b.next. Finally the number can take part in the sorting 
process.

In theory, if all these operations were considered non-destructive, 
.each_line, .filter1 and .sort could run in three different threads 
asynchronously, with buffers in between, utilizing the whole CPU and 
probably reducing the overall execution time. But this is not the case: 
There must not be any read-ahead by any of these designated threads, 
drastically limiting their achievable concurrency performance from the 
beginning.

End of the Enumerator lesson. :)

– Matthias