Skip to content

Instantly share code, notes, and snippets.

@felixyz
Created September 16, 2013 15:40
Show Gist options
  • Save felixyz/6582352 to your computer and use it in GitHub Desktop.
Save felixyz/6582352 to your computer and use it in GitHub Desktop.
Compares speed of two different methods of inserting items in an array.
require 'benchmark'
def insert_then_sort(results, missing_items)
missing_items.each do |id|
results << {id: id, val: nil}
end
results.sort_by!{|item| item[:id] }
results
end
def insert_using_cursors(results, missing_items)
mi_cursor = 0
rs_cursor = 0
complete_set = []
while mi_cursor < missing_items.count
value_to_insert = missing_items[mi_cursor]
mi_cursor += 1
while rs_cursor < results.count && results[rs_cursor][:id] < value_to_insert
complete_set << results[rs_cursor]
rs_cursor += 1
end
complete_set << {id: value_to_insert, val: nil}
end
while rs_cursor < results.count ; complete_set << results[rs_cursor] ; rs_cursor += 1 ; end
complete_set
end
results = []
missing_items = []
100_000.times do |n|
if [true, false].sample
results << {id: n, val: "fortitude"}
else
missing_items << n
end
end
res1 = nil
res2 = nil
puts "INSERT THEN SORT"
puts Benchmark.measure { res1 = insert_then_sort(results.dup, missing_items.dup) }
puts "INSERT USING CURSORS"
puts Benchmark.measure { res2 = insert_using_cursors(results.dup, missing_items.dup) }
# puts
# puts "==== 1"
# puts res1
# puts "==== 2"
# puts res2
unless res1 == res2
puts "WARNING: The result sets were not identical!"
end
__END__
With 10,000 items
=================
INSERT THEN SORT
0.150000 0.000000 0.150000 ( 0.161145)
INSERT USING CURSORS
0.040000 0.010000 0.050000 ( 0.051906)
With 1,000,000 items
=================
INSERT THEN SORT
2.430000 0.050000 2.480000 ( 2.577645)
INSERT USING CURSORS
1.040000 0.040000 1.080000 ( 1.076837)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment