-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTreesSegmentTests.py
248 lines (213 loc) · 36.6 KB
/
TreesSegmentTests.py
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
from unittest import TestCase
from unittest import skip, skipIf
from TreesSegment import *
from itertools import combinations
import random
class stTest(TestCase):
#######
# Tests cases for correctness of Solution
#######
T0 = [2, 5, 1, 4, 9, 3]
T1 = [26, 5, 20, 23, 44, 17, 17, 4, 50, 9] # i=0 j=7
######
# Tests to benchmark solutions. Turn on if benchmarking:
T_large_skip = True
#
# All in all:
# - naive solution is faster for small arrays (len<1000) or if j-i is very small.
# - Segment Tree solution works exponentially faster (e.5 30x) for large data sets (n=90000) and j-i is large (e.g 5000+)
# - Implementing Segment Tree via array or dynammically linked Nodes doesn't seem to have any performance difference.
# Every i,j test (combinatorial)
# This test can take 3 + 3 + 6 minutes to execute.
# [random.randint(0,200) for i in xrange(5000)] # -> 12497500 combinations.
# naive: 7m 11s
# mst: 3m 28s
# starr: 3m 31s
#T_large = 5 * [108, 87, 140, 113, 112, 31, 23, 10, 181, 44, 30, 137, 188, 17, 4, 26, 65, 153, 152, 148, 68, 89, 147, 87, 118, 3, 42, 166, 12, 188, 159, 99, 17, 74, 33, 24, 70, 73, 65, 23, 25, 144, 179, 73, 14, 194, 120, 14, 98, 161, 46, 45, 106, 33, 113, 90, 85, 188, 197, 101, 94, 174, 137, 93, 100, 141, 96, 182, 86, 169, 176, 58, 178, 100, 112, 71, 101, 159, 171, 105, 157, 146, 40, 101, 1, 193, 32, 185, 88, 120, 139, 151, 42, 84, 32, 147, 136, 170, 47, 123, 44, 132, 77, 79, 41, 183, 2, 113, 14, 159, 7, 81, 24, 102, 43, 105, 168, 55, 95, 77, 105, 178, 149, 5, 85, 198, 70, 122, 152, 133, 131, 79, 107, 50, 20, 134, 94, 175, 23, 145, 131, 120, 101, 74, 90, 85, 125, 28, 67, 40, 83, 123, 64, 137, 172, 62, 161, 133, 115, 173, 31, 120, 126, 191, 143, 121, 184, 174, 33, 21, 81, 5, 111, 54, 103, 49, 128, 133, 49, 68, 157, 135, 153, 97, 88, 176, 156, 100, 131, 51, 84, 15, 21, 78, 47, 0, 155, 162, 60, 110, 125, 127, 21, 9, 164, 48, 153, 177, 122, 87, 2, 162, 28, 112, 9, 193, 78, 23, 102, 60, 122, 192, 27, 161, 14, 151, 119, 145, 71, 114, 125, 119, 12, 39, 157, 71, 151, 132, 14, 108, 181, 175, 20, 171, 19, 9, 167, 47, 5, 16, 59, 81, 144, 80, 146, 126, 173, 72, 114, 95, 75, 58, 73, 58, 123, 33, 189, 13, 31, 182, 77, 168, 120, 159, 186, 196, 168, 182, 144, 130, 171, 23, 174, 27, 122, 184, 19, 32, 136, 84, 19, 44, 157, 72, 27, 181, 170, 18, 160, 188, 109, 106, 163, 112, 169, 132, 91, 198, 46, 25, 13, 68, 46, 62, 117, 127, 47, 31, 131, 60, 179, 147, 49, 91, 153, 102, 151, 98, 125, 88, 52, 185, 25, 105, 68, 138, 164, 17, 176, 23, 47, 15, 84, 145, 85, 162, 50, 128, 41, 105, 66, 162, 57, 145, 199, 19, 35, 18, 148, 178, 86, 13, 175, 180, 9, 58, 164, 12, 174, 14, 79, 41, 15, 81, 36, 181, 185, 111, 100, 193, 26, 21, 88, 94, 113, 19, 70, 137, 154, 181, 157, 37, 115, 93, 141, 156, 10, 18, 187, 148, 147, 45, 92, 181, 150, 111, 62, 52, 142, 185, 85, 84, 122, 34, 55, 48, 200, 127, 113, 69, 25, 111, 163, 28, 44, 70, 36, 70, 95, 195, 0, 38, 46, 14, 95, 72, 184, 163, 150, 6, 43, 72, 76, 9, 157, 70, 188, 92, 169, 0, 109, 7, 167, 4, 6, 179, 93, 91, 38, 50, 95, 114, 42, 169, 124, 195, 177, 111, 117, 197, 195, 158, 54, 93, 85, 60, 22, 15, 195, 163, 135, 38, 138, 15, 71, 151, 135, 116, 82, 152, 167, 165, 134, 77, 198, 56, 17, 2, 61, 66, 20, 187, 118, 9, 180, 22, 120, 35, 11, 184, 129, 166, 153, 65, 125, 33, 182, 98, 42, 77, 141, 5, 143, 93, 138, 51, 26, 131, 99, 159, 76, 38, 137, 173, 17, 30, 39, 137, 150, 112, 150, 172, 124, 172, 13, 43, 64, 96, 96, 58, 63, 35, 82, 29, 28, 163, 170, 142, 188, 81, 56, 19, 39, 91, 103, 158, 58, 138, 79, 77, 11, 112, 142, 89, 188, 138, 25, 29, 82, 126, 23, 15, 14, 157, 62, 139, 148, 90, 196, 65, 111, 131, 73, 187, 104, 193, 156, 156, 66, 5, 40, 25, 86, 67, 49, 96, 53, 20, 110, 49, 115, 193, 41, 97, 126, 100, 6, 150, 57, 16, 17, 12, 119, 158, 19, 55, 165, 79, 22, 132, 13, 162, 125, 143, 143, 122, 25, 157, 60, 72, 99, 57, 150, 176, 62, 179, 0, 85, 17, 60, 125, 100, 42, 62, 132, 193, 131, 197, 190, 62, 75, 39, 165, 24, 37, 55, 15, 51, 167, 100, 61, 174, 6, 80, 132, 135, 99, 182, 46, 38, 45, 80, 158, 126, 117, 174, 3, 120, 151, 117, 48, 191, 138, 129, 174, 80, 54, 99, 19, 36, 44, 134, 191, 96, 97, 102, 19, 155, 179, 26, 157, 34, 44, 175, 116, 87, 8, 59, 162, 75, 130, 168, 195, 113, 1, 103, 86, 60, 198, 141, 33, 136, 159, 117, 160, 114, 98, 101, 197, 172, 199, 118, 76, 154, 21, 4, 66, 160, 93, 42, 200, 178, 62, 189, 114, 186, 93, 5, 77, 111, 110, 64, 133, 82, 90, 146, 122, 120, 111, 40, 6, 46, 37, 23, 131, 146, 112, 55, 108, 80, 68, 82, 88, 199, 27, 143, 33, 110, 98, 142, 108, 111, 71, 129, 27, 148, 5, 105, 72, 37, 68, 149, 72, 32, 63, 68, 67, 156, 145, 116, 52, 133, 176, 198, 155, 130, 18, 149, 5, 101, 110, 9, 10, 130, 43, 60, 116, 145, 57, 59, 184, 40, 68, 183, 51, 89, 166, 115, 87, 162, 127, 76, 35, 186, 52, 163, 152, 30, 142, 37, 62, 116, 91, 126, 193, 156, 154, 87, 4, 16, 57, 134, 150, 84, 71, 41, 60, 179, 9, 127, 23, 191, 149, 11, 150, 187, 41, 19, 187, 42, 114, 158, 25, 12, 18, 118, 191, 149, 117, 30, 124, 88, 90, 53, 104, 18, 190, 44, 1, 72, 162, 164, 103, 39, 54, 141, 35, 60, 4, 104, 96, 157, 9, 11, 199, 118, 170, 22, 96, 187, 185, 144, 10, 62, 190, 114, 82, 182, 18, 140, 182, 8, 22, 9, 20, 82, 58, 190, 96, 98, 78, 64, 87, 88, 116, 193, 162, 108, 158, 123, 27, 77, 61, 170, 172, 31, 145, 94, 17, 22, 103, 88, 27, 89, 168, 198, 131, 170, 96, 180, 149, 4, 17, 124, 3, 112, 34, 160, 80, 171, 47, 1, 0, 19, 39, 80, 49, 43, 5, 114, 185, 123, 85, 63, 68, 32, 128, 18, 161, 153, 163]
# naive method better than mst for smaller lists where we often have to traverse small i,j ranges.
# [random.randint(0,200) for i in xrange(1000)] # -> 499500 combinations.
# naive: 4s
# mst: 6s
# mst starr: 7s
T_large = [73, 153, 117, 18, 105, 140, 162, 92, 131, 102, 104, 65, 187, 198, 20, 55, 39, 99, 119, 107, 158, 119, 13, 79, 32, 115, 78, 57, 129, 100, 131, 10, 142, 107, 142, 91, 165, 83, 184, 41, 107, 172, 3, 29, 93, 82, 45, 54, 198, 189, 196, 111, 30, 101, 94, 23, 92, 34, 174, 41, 56, 173, 2, 151, 193, 145, 164, 68, 58, 147, 111, 75, 144, 106, 139, 93, 22, 192, 126, 81, 196, 97, 72, 13, 52, 48, 127, 129, 171, 19, 13, 183, 190, 33, 161, 55, 70, 126, 42, 1, 71, 28, 26, 40, 8, 164, 154, 188, 103, 34, 143, 92, 88, 85, 97, 33, 190, 76, 103, 8, 11, 160, 154, 79, 44, 51, 196, 59, 51, 72, 121, 155, 77, 158, 171, 130, 120, 141, 139, 150, 50, 191, 162, 89, 68, 28, 163, 1, 3, 54, 67, 164, 11, 94, 53, 133, 86, 111, 151, 22, 41, 4, 145, 131, 24, 151, 188, 78, 23, 6, 9, 82, 58, 20, 142, 0, 179, 68, 164, 146, 62, 181, 168, 101, 49, 48, 30, 33, 197, 111, 72, 178, 72, 196, 183, 150, 167, 157, 191, 38, 98, 198, 122, 199, 137, 105, 18, 76, 176, 68, 23, 84, 98, 84, 133, 198, 153, 196, 149, 22, 182, 192, 111, 172, 76, 198, 92, 103, 93, 80, 9, 34, 177, 127, 59, 128, 5, 23, 186, 68, 131, 142, 23, 39, 22, 128, 114, 89, 171, 86, 148, 70, 113, 115, 137, 62, 125, 61, 194, 129, 33, 161, 115, 87, 92, 128, 105, 164, 115, 65, 74, 82, 110, 87, 105, 39, 125, 175, 160, 4, 139, 174, 82, 166, 117, 146, 110, 110, 179, 148, 137, 87, 7, 38, 171, 74, 30, 12, 30, 118, 56, 122, 123, 128, 77, 133, 108, 178, 32, 37, 188, 2, 181, 36, 110, 159, 110, 54, 175, 156, 23, 1, 133, 25, 24, 67, 133, 156, 110, 21, 51, 115, 116, 109, 48, 190, 17, 196, 4, 44, 16, 59, 127, 16, 7, 195, 13, 94, 86, 28, 22, 197, 134, 178, 89, 159, 198, 192, 162, 23, 168, 107, 191, 198, 100, 45, 52, 13, 47, 41, 79, 129, 148, 141, 176, 115, 144, 108, 189, 177, 91, 196, 178, 164, 170, 24, 74, 98, 79, 64, 194, 19, 60, 28, 138, 89, 142, 143, 40, 130, 22, 130, 58, 134, 21, 103, 17, 172, 66, 153, 86, 53, 31, 7, 40, 1, 94, 140, 95, 137, 15, 40, 95, 103, 5, 169, 155, 98, 69, 87, 188, 89, 157, 178, 108, 186, 92, 57, 79, 40, 55, 77, 180, 184, 83, 46, 5, 50, 116, 198, 3, 71, 31, 160, 29, 94, 12, 186, 188, 76, 1, 51, 35, 94, 82, 52, 92, 56, 186, 3, 144, 135, 15, 129, 32, 199, 94, 105, 102, 147, 52, 192, 148, 32, 142, 128, 140, 180, 87, 106, 68, 169, 55, 177, 150, 46, 100, 119, 38, 192, 171, 3, 120, 41, 149, 170, 28, 29, 178, 145, 94, 195, 33, 124, 102, 90, 16, 92, 88, 198, 60, 152, 188, 126, 186, 73, 32, 1, 88, 161, 168, 35, 68, 136, 108, 184, 196, 59, 118, 96, 25, 25, 172, 181, 87, 22, 5, 68, 23, 94, 31, 27, 54, 118, 38, 96, 19, 13, 1, 114, 20, 26, 116, 23, 62, 3, 184, 185, 52, 109, 35, 86, 113, 58, 14, 103, 24, 87, 29, 105, 158, 106, 21, 52, 34, 106, 92, 109, 185, 67, 78, 152, 196, 29, 174, 156, 142, 151, 103, 23, 74, 152, 126, 85, 155, 153, 29, 117, 34, 56, 167, 88, 149, 111, 186, 98, 131, 183, 119, 59, 13, 164, 162, 37, 200, 68, 142, 22, 25, 159, 166, 146, 20, 146, 149, 130, 34, 162, 176, 72, 63, 26, 56, 179, 75, 153, 126, 18, 178, 181, 131, 69, 99, 13, 78, 89, 127, 70, 82, 197, 141, 102, 6, 90, 79, 144, 133, 13, 176, 57, 193, 68, 8, 135, 160, 142, 11, 180, 196, 157, 11, 182, 45, 135, 1, 69, 123, 26, 199, 194, 156, 158, 147, 28, 17, 166, 184, 47, 89, 188, 49, 37, 73, 194, 105, 133, 50, 104, 140, 10, 30, 110, 6, 114, 8, 166, 84, 35, 148, 32, 200, 99, 106, 75, 83, 41, 31, 125, 32, 34, 108, 99, 7, 22, 137, 129, 15, 114, 40, 182, 36, 95, 99, 19, 117, 66, 110, 192, 196, 86, 182, 186, 27, 194, 12, 106, 74, 45, 125, 33, 145, 53, 179, 30, 1, 133, 119, 110, 24, 34, 173, 87, 66, 3, 7, 127, 25, 70, 163, 116, 195, 185, 145, 86, 188, 92, 89, 70, 152, 94, 136, 15, 66, 170, 52, 130, 133, 5, 153, 62, 55, 110, 45, 46, 5, 56, 160, 30, 78, 169, 182, 53, 49, 143, 62, 128, 45, 37, 160, 74, 189, 198, 13, 13, 160, 140, 80, 59, 31, 124, 27, 6, 134, 162, 134, 13, 29, 63, 64, 13, 84, 143, 35, 27, 125, 108, 88, 160, 122, 136, 140, 3, 34, 100, 79, 17, 54, 11, 34, 60, 33, 94, 101, 198, 58, 112, 60, 37, 72, 135, 11, 33, 181, 163, 1, 49, 191, 47, 79, 29, 81, 130, 73, 187, 70, 87, 155, 37, 84, 18, 189, 49, 190, 153, 132, 52, 86, 111, 119, 13, 105, 150, 4, 79, 188, 6, 136, 24, 165, 191, 117, 191, 101, 181, 69, 195, 50, 183, 78, 138, 49, 47, 36, 4, 34, 147, 7, 55, 7, 180, 7, 175, 37, 137, 195, 137, 105, 184, 154, 111, 43, 185, 163, 66, 62, 22, 51, 115, 41, 74, 21, 103, 97, 126, 76, 162, 98, 176, 23, 142, 100, 179, 52, 21, 95, 180, 5, 141, 97, 69, 105, 144, 16, 0, 56, 58, 41, 93, 132, 30, 141, 139, 65, 90, 191, 137, 16, 70, 46, 25, 83, 123, 148, 127, 85, 118, 130, 78, 88, 175]
# Emulating long lists and queries with large-enough distance shows mst is better.
# [random.randint(0, 200) for i in xrange(10000)]
# naive: 729ms # Naive method is 4 times slower.
# mst: 280ms
# mst strarr: 258ms
T_large2 = 10 * [165, 124, 20, 17, 128, 176, 119, 71, 185, 60, 93, 168, 10, 180, 152, 162, 21, 90, 28, 163, 51, 130, 178, 175, 90, 34, 187, 145, 3, 71, 162, 121, 62, 127, 56, 92, 96, 74, 37, 48, 30, 12, 134, 33, 59, 183, 108, 87, 20, 97, 134, 38, 49, 111, 74, 139, 48, 9, 19, 70, 96, 81, 39, 142, 58, 146, 73, 125, 186, 15, 136, 157, 102, 17, 87, 66, 155, 161, 152, 76, 153, 120, 59, 69, 21, 13, 113, 164, 149, 150, 180, 22, 134, 20, 71, 61, 139, 100, 106, 70, 34, 165, 174, 98, 191, 2, 104, 133, 66, 158, 39, 106, 103, 76, 121, 134, 145, 51, 167, 63, 143, 68, 81, 139, 126, 66, 174, 166, 0, 134, 134, 135, 113, 99, 84, 112, 154, 105, 128, 157, 41, 119, 122, 177, 193, 167, 143, 48, 183, 169, 68, 76, 3, 76, 15, 34, 189, 132, 70, 15, 15, 118, 194, 146, 30, 131, 131, 154, 124, 145, 140, 37, 101, 121, 70, 74, 56, 3, 196, 105, 93, 8, 101, 189, 7, 74, 56, 59, 76, 194, 54, 106, 79, 70, 110, 158, 51, 191, 18, 70, 188, 53, 194, 104, 181, 179, 98, 44, 12, 84, 173, 71, 161, 102, 81, 162, 181, 165, 95, 84, 37, 52, 14, 8, 11, 194, 49, 100, 1, 149, 40, 23, 156, 94, 181, 93, 123, 113, 39, 130, 137, 16, 90, 195, 134, 12, 49, 95, 73, 163, 30, 125, 168, 177, 105, 70, 28, 39, 91, 185, 19, 56, 172, 187, 178, 161, 141, 192, 86, 92, 108, 49, 81, 76, 141, 19, 116, 83, 179, 133, 94, 148, 182, 85, 6, 26, 154, 129, 20, 22, 8, 124, 68, 65, 84, 10, 134, 146, 27, 59, 173, 158, 26, 162, 7, 165, 11, 64, 196, 119, 17, 79, 51, 6, 31, 94, 96, 14, 32, 43, 104, 87, 30, 65, 73, 191, 185, 0, 149, 107, 181, 47, 53, 149, 35, 175, 50, 153, 130, 41, 80, 116, 122, 140, 150, 55, 94, 139, 70, 78, 27, 89, 128, 51, 193, 68, 135, 104, 130, 97, 128, 159, 124, 145, 185, 164, 145, 193, 46, 89, 81, 122, 92, 184, 161, 97, 26, 176, 73, 180, 105, 154, 121, 81, 64, 107, 84, 199, 59, 3, 150, 37, 130, 129, 200, 19, 194, 200, 170, 134, 167, 47, 116, 173, 197, 10, 16, 10, 126, 58, 93, 118, 74, 12, 40, 181, 19, 92, 150, 85, 131, 3, 28, 94, 96, 86, 77, 99, 50, 147, 140, 198, 89, 120, 127, 60, 124, 92, 155, 62, 83, 95, 65, 121, 183, 153, 118, 177, 44, 167, 149, 21, 112, 49, 115, 42, 116, 26, 107, 3, 94, 25, 117, 50, 198, 169, 160, 172, 84, 177, 185, 196, 113, 6, 195, 111, 12, 15, 97, 25, 49, 48, 83, 66, 120, 86, 127, 112, 74, 125, 27, 164, 186, 57, 99, 122, 181, 21, 9, 15, 135, 43, 85, 182, 200, 29, 15, 54, 62, 88, 53, 66, 18, 132, 98, 3, 183, 130, 153, 121, 15, 106, 54, 44, 60, 109, 39, 116, 53, 74, 197, 67, 5, 62, 108, 33, 112, 151, 168, 145, 199, 13, 115, 38, 99, 114, 123, 5, 5, 150, 193, 175, 121, 197, 76, 76, 69, 179, 152, 80, 172, 84, 76, 63, 131, 139, 63, 199, 151, 34, 57, 128, 17, 44, 96, 107, 95, 142, 77, 40, 59, 169, 17, 8, 143, 190, 172, 31, 126, 118, 136, 63, 37, 99, 118, 47, 164, 148, 129, 92, 184, 152, 55, 199, 19, 22, 69, 161, 122, 188, 50, 10, 157, 186, 155, 16, 148, 73, 111, 114, 46, 188, 16, 6, 34, 87, 139, 175, 96, 42, 133, 58, 30, 48, 34, 180, 90, 182, 169, 52, 30, 75, 142, 93, 13, 81, 60, 108, 118, 168, 0, 142, 36, 60, 39, 180, 52, 53, 97, 171, 63, 12, 53, 100, 113, 194, 14, 58, 182, 87, 112, 61, 36, 40, 84, 25, 37, 36, 195, 190, 115, 7, 154, 31, 175, 51, 2, 121, 109, 101, 113, 159, 21, 14, 46, 125, 81, 182, 28, 59, 197, 170, 0, 111, 80, 187, 186, 141, 163, 76, 165, 94, 113, 129, 86, 10, 191, 133, 41, 146, 161, 191, 63, 187, 136, 139, 28, 52, 120, 131, 82, 163, 46, 122, 10, 166, 26, 114, 119, 158, 148, 79, 104, 69, 75, 146, 27, 197, 4, 98, 78, 144, 151, 129, 36, 159, 154, 8, 52, 48, 155, 164, 140, 57, 76, 7, 155, 141, 66, 173, 125, 48, 194, 1, 111, 41, 200, 150, 157, 154, 199, 108, 54, 52, 28, 131, 183, 166, 58, 169, 157, 166, 64, 28, 179, 77, 44, 70, 154, 34, 75, 11, 190, 21, 68, 24, 31, 128, 9, 164, 58, 176, 140, 106, 121, 168, 36, 180, 181, 179, 49, 30, 182, 119, 191, 57, 21, 87, 147, 19, 147, 34, 32, 129, 1, 26, 48, 6, 156, 18, 178, 22, 0, 37, 159, 78, 10, 131, 159, 49, 141, 69, 73, 44, 41, 108, 103, 9, 143, 59, 197, 65, 157, 87, 163, 163, 35, 18, 110, 86, 91, 13, 82, 132, 183, 138, 187, 31, 65, 117, 37, 188, 185, 162, 179, 121, 104, 149, 1, 155, 52, 109, 133, 91, 98, 24, 198, 47, 121, 132, 78, 36, 97, 189, 110, 126, 191, 187, 14, 14, 127, 198, 174, 146, 29, 197, 0, 76, 130, 56, 193, 12, 193, 52, 91, 51, 99, 82, 31, 112, 118, 11, 52, 54, 113, 20, 164, 118, 157, 181, 191, 175, 131, 155, 107, 83, 0, 47, 47, 74, 103, 117, 7, 8, 174, 160, 145, 47, 126, 43, 21, 56, 199, 183, 30, 36, 68, 61, 57, 163, 174, 135, 13, 26, 24, 155, 26, 196, 23, 94, 96, 99, 41, 135, 189, 67, 81, 181, 93, 197, 58, 99, 16, 185, 172, 10, 112, 35, 132, 49, 115]
# while len(Q) < 9000:
# a, b = random.randint(0, 9999), random.randint(0, 9999)
# i = min(a,b)
# j = max(a,b)
# if j - i < 500:
# continue
# else:
# Q.append((i,j))
## Leo: 500 * 18 = 9000. (9000 items slow down IDE)
T_large2_queries = 18 * [(1200, 9494), (4518, 9975), (4763, 8122), (260, 8007), (291, 1060), (1447, 6072), (481, 8564), (4168, 5797), (3920, 7735), (1511, 5159), (4208, 5871), (3276, 4029), (5596, 7196), (6284, 7317), (2964, 5036), (7233, 9127), (1667, 6361), (2160, 7478), (3030, 9440), (1342, 3582), (2463, 8848), (7007, 7984), (5896, 8539), (7164, 9781), (4665, 8121), (597, 5626), (6278, 7665), (5001, 7584), (2919, 7412), (1502, 2704), (233, 7539), (6561, 9547), (508, 4188), (3667, 7925), (3512, 4419), (6140, 9667), (385, 5772), (52, 7759), (2551, 9448), (166, 9642), (2368, 5485), (552, 5688), (7458, 9609), (1772, 9398), (589, 6235), (1321, 5514), (5733, 9692), (2027, 2993), (4641, 6646), (1971, 3900), (812, 5086), (1636, 3494), (3164, 8752), (4591, 7393), (2987, 8597), (3939, 6460), (4193, 5953), (663, 4470), (5067, 5701), (445, 5419), (1771, 7474), (6411, 8204), (871, 4591), (4205, 9384), (781, 8143), (242, 2045), (4263, 8963), (7343, 9313), (3462, 8739), (6117, 9402), (2688, 5120), (5007, 8227), (3973, 5731), (463, 3819), (1315, 6353), (8060, 8658), (2731, 9499), (3950, 5110), (5472, 6674), (4970, 8600), (1353, 2419), (13, 1383), (4677, 8670), (7376, 9964), (138, 2562), (1129, 7793), (2287, 2996), (5141, 9583), (1119, 7729), (50, 7921), (2440, 8582), (5058, 8758), (7356, 9962), (971, 9150), (667, 3834), (6970, 8216), (1131, 7463), (5272, 6542), (2856, 5679), (8566, 9275), (2263, 7898), (4625, 5898), (765, 7346), (1210, 8468), (3517, 7850), (1780, 5523), (5446, 8393), (391, 5240), (1201, 5899), (3414, 9006), (1577, 4670), (7280, 8124), (3238, 7853), (2928, 4905), (617, 3183), (4042, 8604), (597, 3978), (978, 1508), (2182, 7668), (1792, 5764), (1906, 7602), (3718, 8579), (4718, 6586), (1910, 2621), (4389, 8246), (5347, 6520), (1346, 6406), (2337, 6196), (6325, 9302), (1081, 9951), (689, 5009), (174, 9695), (5191, 9509), (4094, 7334), (109, 6991), (1391, 3797), (932, 4799), (2300, 6764), (97, 9299), (1837, 9507), (2494, 3720), (436, 3703), (4387, 6132), (5593, 6780), (3451, 8411), (4685, 7237), (2566, 3982), (33, 8302), (5071, 6694), (5038, 5600), (3692, 5008), (4485, 9428), (2114, 8919), (2961, 3840), (115, 6191), (765, 4171), (1891, 5010), (5559, 8046), (4260, 8764), (825, 7600), (3350, 4738), (3153, 5926), (4224, 5405), (5721, 7381), (4547, 5144), (2531, 7683), (4970, 9306), (3231, 4401), (5853, 9287), (1667, 4570), (131, 1464), (2388, 7755), (60, 4828), (5456, 9241), (1151, 6629), (557, 1824), (3084, 9717), (3151, 4491), (4403, 7424), (1061, 4258), (4911, 6427), (3854, 5989), (2700, 7475), (1156, 9090), (1418, 8281), (67, 653), (4324, 9599), (6918, 9763), (6601, 8926), (348, 4445), (3459, 7425), (2010, 5846), (4200, 5579), (3200, 7834), (3333, 6946), (806, 7194), (1289, 4717), (1472, 4781), (7469, 9790), (1405, 7301), (5748, 6556), (6553, 9592), (503, 3015), (2042, 9382), (1618, 4027), (26, 588), (733, 2080), (8102, 9267), (1144, 6078), (3958, 8223), (979, 3344), (4860, 9745), (4252, 5578), (2374, 7507), (2044, 9837), (1299, 8735), (8862, 9981), (3394, 3961), (3377, 7655), (6353, 8365), (5742, 7469), (862, 3257), (2129, 4106), (913, 7611), (2084, 4997), (1620, 8871), (94, 5479), (818, 1382), (529, 5466), (1360, 6245), (961, 7374), (1577, 5590), (6635, 9355), (1461, 2182), (6012, 6894), (3410, 8935), (6535, 8289), (1591, 7666), (7912, 8692), (1743, 3559), (7633, 9961), (3615, 5074), (1951, 5369), (507, 5868), (3131, 5520), (2542, 6971), (3055, 8603), (8041, 8596), (1655, 3848), (4249, 5680), (325, 3686), (415, 1287), (794, 5283), (4367, 6955), (7107, 8219), (931, 5214), (3974, 8319), (4646, 8460), (4346, 7825), (6787, 8831), (4335, 6590), (2599, 7408), (4555, 6903), (1797, 5946), (2173, 8404), (2784, 8441), (1654, 5863), (6828, 8523), (668, 8022), (7305, 9554), (4900, 8698), (2629, 4575), (2307, 8227), (1740, 5540), (7368, 9283), (413, 8141), (1893, 5610), (4013, 5475), (533, 3064), (1635, 2428), (2414, 4375), (1064, 3434), (502, 8162), (3973, 8786), (6939, 8219), (161, 4427), (1481, 5599), (526, 5480), (1213, 5707), (3496, 7799), (3049, 9418), (3106, 7532), (2261, 5768), (3240, 7678), (968, 8273), (3306, 7006), (3836, 8794), (5882, 6614), (2483, 5024), (645, 4459), (3084, 8525), (5507, 7291), (3921, 8922), (4713, 6753), (3138, 9169), (793, 9258), (6521, 9609), (5831, 8849), (432, 7585), (4146, 8378), (1436, 3367), (2821, 6657), (3391, 4792), (443, 4414), (6076, 9558), (6053, 9344), (95, 9236), (92, 4122), (4280, 5901), (2479, 3005), (7065, 7795), (2529, 4075), (5044, 5730), (6481, 8683), (5335, 8954), (2125, 6754), (5856, 9039), (5549, 6118), (2505, 9798), (1240, 5322), (120, 4952), (5435, 8267), (3279, 9969), (5946, 7521), (8254, 8956), (3010, 8364), (8406, 9391), (3513, 5403), (5291, 6779), (5505, 9657), (521, 2581), (2426, 3589), (2727, 5600), (4763, 9970), (2010, 5313), (1729, 2524), (1984, 3145), (3224, 4008), (1399, 7564), (2240, 6231), (620, 9156), (3408, 9762), (294, 9539), (1479, 6467), (1555, 9870), (3324, 5728), (6293, 8053), (2820, 4756), (3531, 8026), (4338, 5137), (1997, 7827), (2552, 8594), (7059, 8718), (692, 9736), (4688, 5488), (5359, 8868), (5343, 9171), (1249, 9998), (801, 6662), (8299, 9456), (6268, 7803), (451, 1506), (2893, 6432), (861, 7778), (3496, 9869), (563, 3359), (4227, 7751), (655, 2603), (1240, 8465), (758, 8991), (965, 8716), (575, 4004), (635, 1577), (5448, 6129), (4688, 6749), (809, 8043), (5147, 6903), (2887, 5069), (1088, 6546), (5578, 7285), (1165, 6266), (4169, 5219), (634, 2361), (1465, 4863), (6024, 6855), (1411, 3563), (5460, 9910), (1980, 5785), (2223, 6539), (180, 3443), (137, 3548), (8231, 9513), (5103, 8025), (2442, 8526), (2252, 8868), (3733, 7613), (946, 4399), (6938, 9844), (5088, 9945), (1844, 6051), (4208, 9243), (3966, 6298), (6117, 9357), (1250, 8902), (1303, 4553), (3522, 6054), (888, 4337), (4165, 9671), (4795, 6305), (3302, 5677), (5752, 7753), (3847, 5583), (908, 4994), (3177, 6223), (3925, 9079), (87, 791), (7630, 9837), (6185, 7168), (3510, 6469), (1312, 8629), (622, 4348), (174, 4104), (5465, 7427), (468, 9170), (3380, 7437), (1733, 4968), (6403, 9220), (2613, 5229), (3269, 5464), (2893, 5876), (6757, 7602), (4294, 5106), (7690, 8490), (1177, 2867), (2147, 6901), (1541, 3447), (258, 4175), (5427, 6135), (1076, 3714), (3907, 8756), (729, 2579), (2309, 8115), (1831, 5020), (48, 7369), (4755, 5727), (4161, 8734), (2551, 7433), (1289, 3036), (3343, 8782), (7239, 8763), (3000, 7423), (1955, 3405), (3740, 5262), (1891, 9189), (6598, 9640), (5168, 6886), (8119, 9527), (408, 2319), (3971, 6225), (1309, 3622), (1797, 8728), (2883, 3712), (7210, 9869), (1776, 6370), (4415, 9336), (129, 5662), (3132, 8500), (5052, 9002), (2710, 8501), (4902, 6320), (8339, 9755), (262, 2986), (1723, 6890), (4973, 6769), (8850, 9836), (1842, 8072), (8170, 9307), (2040, 7727), (2620, 4427), (968, 8159), (3182, 9492), (6561, 9376), (3105, 9646), (6326, 6913), (1693, 8588), (5668, 8987), (406, 3041), (4974, 6787), (2065, 5768), (7639, 9472)]
# [random.randint(0, 50000-1) for i in xrange(50000)]
# Leo[edit]: Took a 1000 sample and clone it 50 times instead. 50k items in IDE slow it down a lot.
T_large3 = 50 * [11651, 14335, 48737, 3875, 48119, 39323, 35173, 8035, 40762, 23107, 9276, 36426, 44535, 45365, 45436, 14894, 45997, 34049, 38728, 26361, 35900, 35590, 32072, 9406, 6204, 2413, 5255, 34093, 8613, 29305, 22635, 12623, 8398, 44636, 4718, 12512, 12596, 8468, 32882, 4976, 14342, 13382, 45034, 52, 20830, 37388, 35122, 19803, 12607, 12555, 31166, 12830, 17346, 2728, 41299, 32646, 16022, 17114, 35998, 24347, 26668, 1945, 33368, 49468, 3920, 43438, 23811, 5129, 2811, 20389, 18593, 12024, 43581, 14994, 23741, 3237, 20015, 30227, 42759, 12983, 3158, 11513, 35829, 5665, 6464, 45283, 25710, 6210, 9781, 20723, 4355, 16008, 6685, 38684, 17447, 4495, 8438, 36259, 17309, 49652, 35158, 34261, 17172, 894, 45492, 10090, 27441, 6453, 5002, 40399, 20146, 44783, 1126, 22388, 33932, 42228, 34625, 43678, 13970, 32866, 4935, 15367, 2809, 23044, 10018, 33451, 34436, 13254, 16078, 16106, 49182, 12377, 24269, 36996, 38219, 27784, 43844, 41805, 14429, 11926, 4912, 46158, 41193, 38448, 8876, 33078, 23006, 49042, 12596, 47563, 3130, 17659, 29020, 7358, 33544, 6200, 43307, 34209, 37430, 28867, 40862, 44775, 2432, 27037, 20742, 3919, 44277, 22230, 7715, 4843, 21472, 46393, 19391, 48, 13505, 4306, 42742, 23980, 834, 11981, 20812, 20798, 1725, 42968, 16357, 10422, 9981, 25602, 45316, 10373, 41090, 4767, 2997, 23490, 43740, 33331, 13418, 31537, 3729, 2749, 28238, 31829, 18807, 37276, 39985, 42523, 49313, 11856, 14760, 14671, 5951, 41120, 29268, 32173, 37227, 29426, 40613, 9405, 35261, 8666, 9861, 40166, 20640, 42362, 15947, 48405, 18516, 39490, 22871, 29418, 108, 8505, 28906, 30330, 25897, 488, 186, 47803, 20469, 27462, 26019, 39275, 8435, 15592, 26677, 42146, 23487, 44604, 10663, 5584, 28382, 12023, 3288, 9596, 15619, 30718, 39710, 39831, 19552, 38279, 28185, 34166, 38225, 32747, 26656, 33435, 27908, 27931, 8446, 30466, 13874, 14858, 10529, 30674, 3814, 13381, 44669, 48642, 5342, 28602, 15872, 4466, 47185, 38543, 25013, 20099, 14307, 23744, 40503, 2267, 6916, 29865, 31323, 49324, 48209, 20700, 49450, 43258, 8457, 24609, 29954, 40523, 9632, 14531, 39220, 343, 1900, 23253, 47996, 10018, 28299, 4465, 27839, 47390, 16041, 26928, 39537, 30759, 3174, 40038, 42689, 41923, 23192, 16020, 36394, 49377, 25682, 2490, 19652, 37754, 26786, 35999, 5066, 36599, 26015, 17133, 26706, 44245, 7354, 38202, 15674, 26179, 21350, 22819, 43577, 10221, 27303, 33311, 25450, 49837, 4547, 4208, 605, 15666, 33141, 37894, 35055, 24797, 23343, 18034, 39512, 35665, 19869, 44076, 34023, 21217, 9974, 26056, 25573, 31946, 2909, 34085, 40914, 22796, 44276, 10318, 36457, 18060, 20033, 20777, 19344, 38825, 42761, 12397, 4001, 24040, 25088, 12857, 49090, 16415, 6421, 33036, 13500, 5255, 16177, 36225, 44847, 30300, 40886, 48170, 41895, 44777, 36254, 13929, 49465, 43689, 39783, 223, 29032, 49733, 36786, 21197, 13659, 13212, 12850, 18594, 706, 46663, 23006, 48719, 43929, 4989, 45282, 24381, 44048, 4431, 9689, 32616, 39417, 30494, 21357, 33081, 43056, 8509, 27669, 8070, 7883, 12321, 40455, 35417, 3543, 17824, 44835, 9768, 10408, 5232, 4247, 46121, 14915, 20182, 26585, 35553, 15974, 5301, 39452, 45930, 24203, 3686, 20015, 2704, 38316, 28271, 47238, 9296, 6439, 174, 17318, 22454, 41759, 3331, 21281, 8077, 41235, 41312, 42417, 27293, 20638, 47724, 22423, 6891, 12624, 41641, 35100, 47166, 41619, 36434, 42506, 17952, 13604, 49005, 28458, 5845, 17455, 39762, 35949, 45509, 43093, 21142, 37398, 45910, 1689, 18270, 32978, 9980, 19164, 45513, 24997, 43685, 943, 14455, 48535, 14861, 11705, 9636, 12907, 28294, 23591, 34774, 41856, 36041, 38483, 23893, 15034, 13495, 47709, 25510, 24474, 754, 30193, 48302, 27344, 28442, 31390, 12401, 45127, 42511, 49966, 9431, 21378, 49342, 6082, 8052, 7889, 10325, 16050, 18645, 34925, 44914, 40772, 15762, 22083, 37390, 49042, 31693, 40877, 17483, 49932, 49398, 49344, 45925, 25161, 21077, 26108, 3505, 42347, 35895, 35267, 17877, 25394, 8438, 34858, 19549, 44102, 40661, 20226, 27602, 48735, 49343, 29455, 34782, 12753, 48181, 17198, 8547, 6385, 3725, 13602, 49446, 40240, 24163, 38411, 15636, 41457, 340, 384, 23553, 3068, 37465, 39828, 3152, 45647, 12245, 32265, 13218, 1167, 41600, 34798, 14551, 29759, 24578, 15849, 16051, 27678, 10830, 28599, 17957, 20795, 22226, 32367, 26127, 30895, 25448, 47988, 49967, 976, 24404, 24405, 18561, 49584, 46509, 31308, 11037, 40763, 37816, 39286, 15489, 10305, 48431, 5445, 8480, 22595, 20945, 20003, 7424, 24241, 21391, 20832, 5066, 40406, 30911, 13293, 11388, 24681, 49754, 8236, 31808, 15875, 33437, 28854, 8390, 44254, 13777, 13603, 36713, 28021, 3398, 40385, 38517, 35623, 5108, 16104, 25124, 7985, 26415, 10997, 43446, 9905, 36857, 42062, 30287, 183, 14503, 30708, 42563, 25776, 10337, 33067, 13746, 19953, 21654, 11054, 4887, 29792, 43612, 24238, 49749, 22706, 13637, 24140, 49090, 13877, 48312, 9270, 49640, 28593, 42109, 34053, 4367, 19441, 17269, 6177, 446, 4, 18765, 22480, 49645, 17849, 23110, 37666, 39699, 1064, 1338, 12196, 41166, 8139, 49866, 19815, 11928, 19662, 14156, 20068, 14141, 16957, 8573, 9228, 11502, 35308, 34580, 37080, 32854, 27444, 49912, 33510, 23, 4088, 14398, 14175, 22767, 26696, 27965, 1485, 22610, 15093, 39890, 3649, 41721, 10911, 40557, 35230, 24948, 326, 15872, 36421, 37109, 37857, 4595, 28999, 12125, 34060, 18957, 38139, 27903, 10833, 27523, 24543, 38477, 25834, 22276, 12994, 46019, 24102, 47258, 19677, 42707, 34476, 28431, 47992, 10580, 21345, 23286, 44971, 5640, 21498, 4402, 43752, 9191, 29552, 24591, 28087, 31397, 14303, 44315, 44154, 46476, 4600, 23392, 26506, 7059, 33417, 23422, 13936, 1197, 35499, 31504, 19153, 38349, 13738, 3907, 7704, 16096, 42349, 26588, 34814, 9898, 17873, 37349, 41008, 221, 48573, 11319, 16689, 32371, 23356, 12966, 47186, 23171, 21995, 46097, 25719, 41822, 23195, 26366, 15408, 11916, 6748, 1972, 23275, 37961, 31437, 18295, 29446, 30438, 39272, 38313, 13215, 33372, 44180, 41806, 42487, 48563, 620, 32031, 36534, 3689, 10741, 21696, 31006, 9511, 12174, 921, 44791, 1811, 21031, 39504, 29747, 49005, 21676, 31873, 47849, 4971, 16635, 15627, 14482, 16654, 35442, 30863, 46052, 45754, 46, 33149, 34675, 14944, 8241, 43736, 6830, 11597, 21464, 11456, 41483, 25929, 22446, 4933, 4232, 2595, 35205, 979, 20546, 49612, 48896, 2503, 21773, 35490, 21287, 45892, 38632, 7993, 18491, 3081, 38698, 4624, 2282, 43912, 17753, 12560, 2345, 32517, 19347, 35090, 3385, 8883, 42275, 48383, 10679, 41481, 38661, 37846, 14866, 9882, 18625, 3910, 9533, 23427, 5308, 47620, 1855, 43161, 47645, 14423, 41211, 25614, 17252, 10451, 13947, 29606, 39994, 26443, 24547, 9942, 4685, 38499, 33442, 24521, 38060, 47814, 2364, 36087, 44479, 46124, 38264, 23949, 8004, 861, 39340, 33346, 36256, 45753, 48982, 47975, 43930, 27803, 32656, 34418, 49125, 16990, 44512, 38081, 12887, 4343, 4655, 24785, 522, 20043, 46195, 48887, 48063, 7119, 10078, 46715, 11914, 47520, 44422]
# Q = []
# while len(Q) < 90000:
# a, b = random.randint(0, 50000-1), random.randint(0, 50000-1)
# i = min(a, b)
# j = max(a, b)
# if j - i < 10000:
# continue
# else:
# Q.append((i, j))
# # Leo note: List with 90,000 elements is rather large and slows down IDE. Workaround: take the first 63 elements and duplicate it 1587 times.
# mst: 2s, 862ms
# mst starr: 2s 887ms <<< Interestingly enough, Tree array implementation doesn't give us much of a benifit.
# naive: 56s! <<< Exponential growth observed here.
T_large3_queries = 1587 * [(17459, 41445), (2867, 46776), (21890, 35494), (10413, 37391), (18814, 36558), (8717, 36794), (6054, 16332), (10237, 36801), (16380, 41365), (28254, 43939), (5944, 25342), (17449, 28410), (10297, 22554), (6017, 30209), (2800, 18339), (19153, 29603), (22948, 35368), (14412, 26648), (25779, 39097), (15089, 36888), (11275, 34909), (6383, 17036), (29806, 45000), (2252, 47316), (186, 39834), (7924, 37000), (4889, 35693), (14743, 45818), (24355, 36795), (16800, 37588), (23197, 44021), (20748, 46662), (21562, 35182), (4709, 41310), (20088, 42635), (391, 27711), (19533, 29721), (7015, 19397), (1781, 33282), (1711, 32460), (17994, 41199), (11159, 31606), (9453, 21142), (7966, 30053), (17933, 43031), (10475, 29688), (14370, 44780), (9907, 49181), (7055, 44731), (902, 26383), (14419, 49013), (4811, 17793), (3153, 36058), (1552, 15861), (21007, 45243), (1804, 40105), (31506, 49651), (5327, 30121), (8314, 19925), (15033, 27091), (23777, 49241), (5407, 24078), (10769, 30332)]
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance2_naive(self):
t_count = 0
for i, j in self.T_large2_queries:
min_val = min(self.T_large2[i:j+1])
t_count += 1
print("test_performance2_naive completed tests:", t_count)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance2_mst(self):
mst = SegmentTree(self.T_large2_queries, min)
t_count = 0
for i, j in self.T_large2_queries:
min_val = mst.query(i,j)
t_count += 1
print("test_performance2_mst completed tests:", t_count)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance2_mst_starr(self):
mst = SegmentTreeArr(self.T_large2_queries, min)
t_count = 0
for i, j in self.T_large2_queries:
min_val = mst.query(i,j)
t_count += 1
print("test_performance2_mst_starr completed tests:", t_count)
# This one is very slow. ~1 minute. Very good showcase of performance difference.
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance3_naive(self):
t_count = 0
for i, j in self.T_large3_queries:
min_val = min(self.T_large3[i:j+1])
t_count += 1
print("test_performance3_naive completed tests:", t_count)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance3_mst(self):
mst = SegmentTree(self.T_large3, min)
t_count = 0
for i, j in self.T_large3_queries:
min_val = mst.query(i,j)
t_count += 1
print("test_performance3_mst completed tests:", t_count)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance3_mst_starr(self):
mst = SegmentTreeArr(self.T_large3, min)
t_count = 0
for i, j in self.T_large3_queries:
min_val = mst.query(i,j)
t_count += 1
print("test_performance3_mst_starr completed tests:", t_count)
def test_min_queries_T0(self):
min_segment_tree = SegmentTree(self.T0, min)
# print "Min for 1,3 = ", min_segment_tree.query(1,3), " (expecting 1)"
for i, j in combinations(list(range(len(self.T0))), 2):
self.assertEqual(min(self.T0[i:j+1]), min_segment_tree.query(i, j))
def test_min_queries_T1(self):
mst = SegmentTree(self.T1, min)
mst_min = mst.query(0, 7)
min_min = min(self.T1[0:7+1])
self.assertEqual(mst_min, min_min, "{} {}".format(mst_min, min_min))
def test_max_queries_T0(self):
max_segment_tree = SegmentTree(self.T0, max)
# print "Min for 1,3 = ", min_segment_tree.query(1,3), " (expecting 1)"
for i, j in combinations(list(range(len(self.T0))), 2):
self.assertEqual(max(self.T0[i:j+1]), max_segment_tree.query(i, j))
def test_max_queries_T1(self):
mst = SegmentTree(self.T1, max)
mst_max = mst.query(0, 7)
max_max = max(self.T1[0:7+1])
self.assertEqual(mst_max, max_max, "{} {}".format(mst_max, max_max))
def test_starr_min_queries_T0(self):
min_segment_tree = SegmentTreeArr(self.T0, min)
# print "Min for 1,3 = ", min_segment_tree.query(1,3), " (expecting 1)"
for i, j in combinations(list(range(len(self.T0))), 2):
self.assertEqual(min(self.T0[i:j+1]), min_segment_tree.query(i, j))
def test_starr_min_queries_T1(self):
mst = SegmentTreeArr(self.T1, min)
mst_min = mst.query(0, 7)
min_min = min(self.T1[0:7+1])
self.assertEqual(mst_min, min_min, "{} {}".format(mst_min, min_min))
def test_min_queries_T_Rand(self):
"""Test with randomly generated lists. Test every possible index combination.
I caught a few subtle bugs with this method. Random testing is good!
"""
for t in range(1, 70):
L = [random.randint(0, 50) for _ in range(t)]
# print "L: ", L # Debug
# print "List with len: ", len(L)
min_segment_tree = SegmentTree(L, min)
for i, j in combinations(list(range(len(L))), 2):
m = min(L[i:j+1])
mq = min_segment_tree.query(i,j)
# print m == mq, i, j, L[i:j+1], m, mq # Debug
self.assertEqual(m, mq)
def test_max_queries_T_Rand(self):
"""Test with randomly generated lists. Test every possible index combination.
I caught a few subtle bugs with this method. Random testing is good!
"""
for t in range(1, 70):
L = [random.randint(0, 50) for _ in range(t)]
# print "L: ", L # Debug
# print "List with len: ", len(L)
min_segment_tree = SegmentTree(L, max)
for i, j in combinations(list(range(len(L))), 2):
m = max(L[i:j+1])
mq = min_segment_tree.query(i,j)
# print m == mq, i, j, L[i:j+1], m, mq # Debug
self.assertEqual(m, mq)
def test_min_queries_T_Rand_starr(self):
"""As above except for SegmentTreeArr"""
for t in range(1, 70):
L = [random.randint(0, 50) for _ in range(t)]
min_segment_tree = SegmentTreeArr(L, min)
for i, j in combinations(list(range(len(L))), 2):
m = min(L[i:j+1])
mq = min_segment_tree.query(i,j)
self.assertEqual(m, mq)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance_naive(self):
t_count = 0
for i, j in combinations(list(range(len(self.T_large))), 2):
min_val = min(self.T_large[i:j+1])
t_count += 1
print("naive implemented did ", t_count, "tests")
pass
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance_mst_generation(self):
mst = SegmentTree(self.T_large, min)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance_mst_generation_starr(self):
mst = SegmentTreeArr(self.T_large, min)
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance_mst_query(self):
mst = SegmentTree(self.T_large, min)
t_count = 0
for i, j in combinations(list(range(len(self.T_large))), 2):
min_val = mst.query(i, j)
t_count += 1
print("mst implementation did ", t_count, "tests")
pass
@skipIf(T_large_skip, "T_large_skip is True")
def test_performance_mst_query_starr(self):
mst = SegmentTreeArr(self.T_large, min)
t_count = 0
for i, j in combinations(list(range(len(self.T_large))), 2):
min_val = mst.query(i, j)
t_count += 1
print("mst implementation did ", t_count, "tests")
pass
# todo - max segment tree
# todo - sum_segment tree