From: Sergey Chernov <real.sergeych@...>
Date: 2010-05-14T03:23:06+09:00
Subject: Re: Putting value in sorted array

Gary Wright wrote:
> On Dec 8, 2007, at 3:27 PM, Jari Williamsson wrote:
>> Thanks for the tip! I optimized it into:
>>
>> arr = [5, 3, 1]
>> insert_value = 2
>> arr.sort! { |a,b| b <=> a } if !(arr << insert_value).uniq!
> 
> That is a lot of work to insert an item into a sorted array.

sorting after each insertion is a bad idea. there is a quite simple 
binary search that provide super effective way to insert into sorted 
arrays. It could be done, for example, like this:

class SortedArray < Array

  def self.[] *array
    SortedArray.new(array)
  end

  def initialize array=nil
    super( array.sort ) if array
  end

  def << value
    insert index_of_last_LE(value), value
  end

  alias push <<
  alias shift <<

  def index_of_last_LE value
    # puts "Insertgin #{value} into #{inspect}"
    l,r = 0, length-1
    while l <= r
      m = (r+l) / 2
      # puts "#{l}(#{self[l]})--#{m}(#{self[m]})--#{r}(#{self[r]})"
      if value < self[m]
        r = m - 1
      else
        l = m + 1
      end
    end
    # puts "Answer: #{l}:(#{self[l]})"
    l
  end
end

The difference is great if comparison and/or copy is expesive (say, 
strings), and when array is long:

bm(12) do |x|
  x.report('SortedArray') { a = SortedArray[]; 10000.times { a << 
rand(300) } }
  x.report('Array.sort') { a = []; 10000.times { a << rand(300); a.sort! 
} }
end

                  user     system      total        real
SortedArray 0.180000   0.000000   0.180000 (  0.192040)
Array.sort    3.500000   0.010000   3.510000 (  3.515578)

Though, single sort! for a big array is times more effective than adding 
elements to SortedArray one by one. Checked on 1.9.1.
-- 
Posted via http://www.ruby-forum.com/.