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
|
#!/usr/bin/env ruby
require 'benchmark'
require 'li_std_speed'
include Li_std_speed
def benchmark(f, phigh, sequences)
print f.class
puts '%10s ' % 'n' + sequences.inject('') { |a,s| a << '%10s' % s.class }
0.upto(phigh-1) do |p|
n = 2**p
print "%10d"%n
$stdout.flush
for s in sequences
cont = s.new((0..n).to_a)
Benchmark.benchmark { f.call(cont) }
end
end
end
def iterate(cont)
# expected: O(n)
# got: O(n**2) for set/list (vector/deque fine)
it = cont.begin
last = cont.end
while it != last
it.next
end
end
def erase(cont)
# expected: O(n)
# got: O(n**2) for vector/deque and O(n**3) for set/list
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) or cont.end
end
end
def insert(cont)
it = cont.end
size = cont.size
if cont.kind_of? RbSet
# swig stl missing hint version of insert for set
# expected would be O(n) with iterator hint version
# expected: O(n*log(n))
# got: O(n**3*log(n))
size.upto(size<<1) { |x| cont.insert(x) }
else
# expected: O(n)
# got: O(n**3) for list (vector/deque fine)
size.upto(size<<1) { |x| cont.push(x) }
end
end
if $0 == __FILE__
sequences = [RbVector,RbDeque,RbSet,RbList]
for f,phigh in [[method(:iterate),15], [method(:insert),15],
[method(:erase),11]]
benchmark(f, phigh, sequences)
end
end
|
