/
simple_skiplist.rb
84 lines (79 loc) · 2.01 KB
/
simple_skiplist.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
$:.unshift File.dirname(__FILE__) + "/../../lib"
require 'strokedb'
require 'benchmark'
include StrokeDB
puts "Serialization techniques"
len = 2_000
array = (1..len).map{ [rand(len).to_s]*2 }
biglist = Skiplist.from_a(array)
dumped = biglist.marshal_dump
Benchmark.bm(17) do |x|
# First technique: to_a/from_a
GC.start
x.report("Skiplist#to_a ") do
biglist.to_a
biglist.to_a
biglist.to_a
biglist.to_a
biglist.to_a
end
GC.start
x.report("Skiplist.from_a ") do
Skiplist.from_a(array)
Skiplist.from_a(array)
Skiplist.from_a(array)
Skiplist.from_a(array)
Skiplist.from_a(array)
end
# Another technique: Marshal.dump
GC.start
x.report("Skiplist#marshal_dump ") do
biglist.marshal_dump
biglist.marshal_dump
biglist.marshal_dump
biglist.marshal_dump
biglist.marshal_dump
end
GC.start
x.report("Skiplist#marshal_load ") do
Skiplist.allocate.marshal_load(dumped.dup)
Skiplist.allocate.marshal_load(dumped.dup)
Skiplist.allocate.marshal_load(dumped.dup)
Skiplist.allocate.marshal_load(dumped.dup)
Skiplist.allocate.marshal_load(dumped.dup)
end
end
puts
puts "Find/insert techniques"
Benchmark.bm(42) do |x|
langs = [:C] if RUBY_PLATFORM !~ /java/
langs = [:Java] if RUBY_PLATFORM =~ /java/
Skiplist.with_optimizations(langs) do |lang|
GC.start
x.report("Skiplist#find 5000 #{lang}".ljust(32)) do
1000.times do
key = rand(len).to_s
biglist.find(key)
biglist.find(key)
biglist.find(key)
biglist.find(key)
biglist.find(key)
end
end
GC.start
x.report("Skiplist#insert 5000 #{lang}".ljust(32)) do
1000.times do
key = rand(len).to_s
biglist.insert(key, key)
key = rand(len).to_s
biglist.insert(key, key)
key = rand(len).to_s
biglist.insert(key, key)
key = rand(len).to_s
biglist.insert(key, key)
key = rand(len).to_s
biglist.insert(key, key)
end
end
end
end