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
|
#!/usr/bin/env ruby
#
# This is a simple speed benchmark suite for std containers,
# to verify their O(n) performance.
# It is not part of the standard tests.
require 'benchmark'
require 'mathn'
require 'ruby_li_std_speed'
include Ruby_li_std_speed
def benchmark(f, phigh, sequences)
puts f
print '%10s' % 'n'
maxlen = sequences.max { |a,b| a.to_s.size <=> b.to_s.size }
maxlen = maxlen.to_s.size - 12
sequences.each { |s| print "%#{maxlen}s" % "#{s.to_s.sub(/.*::/,'')}" }
puts
o_perf = Array.new(sequences.size, 0)
last_t = Array.new(sequences.size, nil)
1.upto(phigh) do |p|
n = 2**(p-1)
print "%10d" % n
sequences.each_with_index do |s, i|
cont = s.new((0..n).to_a)
Benchmark.benchmark('',0,"%#{maxlen-2}.6r") { |x|
t = x.report { f.call(cont) }
o_perf[i] += last_t[i] ? (t.real / last_t[i]) : t.real
last_t[i] = t.real
}
end
puts
end
print " avg. O(n)"
base = 1.0 / Math.log(2.0)
sequences.each_with_index do |s, i|
o_perf[i] /= phigh
# o_perf[i] = 1 if o_perf[i] < 1
o_perf[i] = Math.log(o_perf[i]) * base
print "%#{maxlen-1}.2f " % o_perf[i]
end
puts
end
def iterate(cont)
it = cont.begin
last = cont.end
while it != last
it.next
end
end
def erase(cont)
it = cont.end
# can't reuse begin since it might get invalidated
while it != cont.begin
it.previous
# set returns None, so need to reobtain end
it = cont.erase(it) || cont.end
end
end
def insert(cont)
size = cont.size
size.upto((size<<1) - 1) { |x| cont.push(x) }
end
if $0 == __FILE__
GC.disable
sequences = [RbVector,RbDeque,RbSet,RbList,
RbFloatVector,RbFloatDeque,RbFloatSet,RbFloatList]
n = 17
for f,phigh in [[method(:iterate),n], [method(:insert),n],
[method(:erase),n-4]]
benchmark(f, phigh, sequences)
end
end
|
