Gary W. wrote:
On Dec 8, 2007, at 3:27 PM, Jari W. 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.