| 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 | |
|---|
| 19 | use System.Diagnostics |
|---|
| 20 | use Treap |
|---|
| 21 | |
|---|
| 22 | class 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 | |
|---|
