Wiki

Ticket #263: speedTreap.cobra

File speedTreap.cobra, 2.5 KB (added by hopscc, 7 years ago)
Line 
1# Compare setup+access speed of Dict vs Treap vs List
2# Treap: 9.5x slower than Dict,
3#        1.3x slower than List (contains),
4#        1.4x FASTER than Sorted-Dict
5#
6#              Treap: 1146 1.00
7#                Dict: 0117 0.10
8#         Sorted-Dict: 1726 1.51
9#       List-contains: 0826 0.72
10#             List-in: 0840 0.73
11
12#   Changing to KeyValuePair slows down to ~1.2x faster than Sorted-Dict
13#               Treap: 1381 1.00
14#                Dict: 0115 0.08
15#         Sorted-Dict: 1713 1.24
16#       List-contains: 0833 0.60
17#             List-in: 0837 0.61
18
19use System.Diagnostics
20use Treap
21
22class SpeedTreap
23    def print( desc as String, ms, ratio) is shared
24        print '[desc.padLeft(20)]: [ms:D4] [ratio:N2]'
25       
26    def main is shared
27        count = 1_000_000       
28        sw = Stopwatch()
29       
30       
31        td = Treap<of String, bool>()
32        sw.start
33        for c in 'abcdefghijklmnopqrstuvwxyz'
34            td[c.toString] = true
35        #sw.start
36        for i in count
37            #t = td['k']
38            #t = td['e']
39            assert td['y']
40        sw.stop
41        t1 = sw.elapsedMilliseconds
42        .print('Treap', t1, 1.00)
43        tbase = t1
44        sw.reset
45       
46        d = Dictionary<of String, bool>() # {:}
47        sw.start
48        for c in 'abcdefghijklmnopqrstuvwxyz'
49            d[c.toString] = true
50        #sw.start
51        for i in count
52            #t = d['k']
53            #t = d['e']
54            assert d['y']
55        sw.stop
56        t1 = sw.elapsedMilliseconds
57        .print('Dict', t1, t1/tbase)
58        sw.reset
59       
60        sd = SortedDictionary<of String, bool>()
61        sw.start
62        for c in 'abcdefghijklmnopqrstuvwxyz'
63            sd[c.toString] = true
64        #sw.start
65        for i in count
66            #t = d['k']
67            #t = d['e']
68            assert sd['y']
69        sw.stop
70        t1 = sw.elapsedMilliseconds
71        .print('Sorted-Dict', t1, t1/tbase)
72        #print 'Sorted-Dict:', t1, t1/tbase
73        sw.reset
74       
75        ld = List<of String>()
76        sw.start
77        for c in 'abcdefghijklmnopqrstuvwxyz'
78            ld.add(c.toString)
79        #sw.start
80        for i in count
81            #t = td['k']
82            #t = td['e']
83            #assert 'y' in ld
84            assert ld.contains('y')
85        sw.stop
86        t1 = sw.elapsedMilliseconds
87        .print('List-contains', t1, t1/tbase)
88        #print 'List-contains:', t1, t1/tbase
89        sw.reset
90   
91        ld.clear
92        sw.start
93        for c in 'abcdefghijklmnopqrstuvwxyz'
94            ld.add(c.toString)
95        for i in count
96            #t = td['k']
97            #t = td['e']
98            #assert 'y' in ld
99            assert 'y' in ld
100        sw.stop
101        t1 = sw.elapsedMilliseconds
102        .print('List-in', t1, t1/tbase)
103        #print 'List1:', t1, t1/tbase
104        sw.reset
105