Re: Is high-speed sorting impossible with Ruby?

2011/11/29 Matthias W=E4chter <[e-mail]>:
> On 29.11.2011 02:05, Josh Cheek wrote:
>>
>> 2011/11/28 Matthias W=E4chter<[e-mail]>
>>
>>> A similar solution, at first glance only marginally different, is the
>>> following:
>>>
>>> =A0$stdin.gets
>>>>
>>>> puts $stdin.each_line.sort_by(&:to_**i)
>>>>
>>>
>>> Besides the fact that this solution is slower than yours, it uses a nea=
t
>>> little technique of Ruby 1.9, Enumerators.
>>
>>
>> $stdin is already enumerable, so each_line isn't necessary
>>
>> puts $stdin.drop(1).sort_by(&:to_i)
>
> Great one-liner, thanks!
>
> But in the context of my posting, it is not following the Enumerator
> principle. $stdin.drop(1) creates a large array on its output which I wan=
ted
> to avoid.

How do you avoid having an Array with all items when sorting?  If you
want to do that you need more advanced sorting algorithms (external
sorting) where not all the data is in main memory all the time.

> What we need is an enumeratoresque version of Enumerable#drop, which I ca=
ll
> drop_first. It will only consume on its input
>
>> class Enumerator
>> =A0def filter1(&blk)
>> =A0 =A0self.class.new do |y|
>> =A0 =A0 =A0each do |*input|
>> =A0 =A0 =A0 =A0y << blk.call(*input)
>> =A0 =A0 =A0end
>> =A0 =A0end
>> =A0end
>>
>> =A0def drop_first(n)
>> =A0 =A0self.class.new do |y|
>> =A0 =A0 =A0with_index do |input,idx|
>> =A0 =A0 =A0 =A0y << input if idx >=3D n
>> =A0 =A0 =A0end
>> =A0 =A0end
>> =A0end
>> end
>>
>> puts $stdin.to_enum(:each_line).drop_first(1).filter1(&:to_i).sort
>
> Performance-wise not better at all, but a nice excursion.

Why so complicated?  You can just do

module Enumerable
  def drop1(n)
    each_with_index {|x,i| yield x if i >=3D n}
  end
end

Or, also callable without a block:

module Enumerable
  def drop1(n)
    if block_given?
      each_with_index {|x,i| yield x if i >=3D n}
    else
      enum_for(:drop1, n)
    end
  end
end


irb(main):037:0> Source.new.drop1(2) {|i| printf "*block %2d\n", i}
before  0
after   0
before  1
after   1
before  2
*block  2
after   2
before  3
*block  3
after   3
before  4
*block  4
after   4
=3D> #<Source:0x102b4890>

But you can achieve the same memory complexity with standard means:

puts $stdin.drop(1).map!(&:to_i).sort!

Here #drop creates the Array once and all other operations work on that:

irb(main):054:0> a=3DArray.new(10){rand 20}
=3D> [14, 6, 6, 0, 14, 16, 19, 10, 14, 0]
irb(main):055:0> a.object_id
=3D> 135532690
irb(main):056:0> a.drop(1).tap {|o| p o.object_id}.map!(&:to_i).tap
{|o| p o.object_id}.sort!.tap {|o| p o.object_id}
134354700
134354700
134354700
=3D> [0, 0, 6, 6, 10, 14, 14, 16, 19]

Kind regards

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/