-
Notifications
You must be signed in to change notification settings - Fork 1
/
bucketsToUpdate.py
139 lines (103 loc) · 3.42 KB
/
bucketsToUpdate.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
PLACES = [10**unit for unit in range(1, 10)]
cache = {}
cache2 = {}
bucketsToUpdate = set()
def _getBucketsToUpdate(number):
buckets = []
for place in PLACES:
bucket = int(number / place) * place
if bucket == 0:
break
buckets.append(int(number / place) * place)
return set(buckets)
def _getBucketsToUpdate2(number):
buckets = []
cacheMissPositions = {}
for indx, place in enumerate(PLACES):
bucket = int(number / place) * place
cachekey = str(bucket)
if(bucket != 0):
# print("appending", bucket)
buckets.append(bucket)
if(cachekey in cache2.keys() and cache2[cachekey] != None):
# print("Cache hit", bucket)
allBuckets = buckets + sorted(cache2[cachekey])
for bucket in cacheMissPositions.keys():
cache2[bucket] = set(allBuckets[cacheMissPositions[bucket]:])
# print("Cache", bucket , cache2[bucket], allBuckets)
return set(allBuckets)
else:
cacheMissPositions[str(bucket)] = indx
if(bucket == 0 or place == PLACES[-1]):
# print("Scan End, Caching intermideiates")
# cache everything
for bucket in cacheMissPositions.keys():
cache2[bucket] = set(buckets[cacheMissPositions[bucket]:])
# print("Cache", bucket , cache2[bucket])
break
# print("asdsad")
return set(buckets)
def _getHigherBuckets(number, place=1, startingPlace = 1):
if(number == 0):
return set()
cachekey = str(number)+"_"+str(place)
if(cachekey in cache.keys() and cache[cachekey] != None):
# print("cache hit for", number)
return cache[cachekey]
cache[cachekey] = set()
unit = 10**place
higherBuckets = _getHigherBuckets(int(number / (10**place))*(10**place), place+1, startingPlace)
if(place != startingPlace):
cache[cachekey] = higherBuckets.union(set([number]))
else:
cache[cachekey] = higherBuckets
return cache[cachekey]
# bucket = int(number / unit) * unit
# if bucket == 0:
# return None
# else:
# return localBuckets
# set.add()
# print(int(number / place) * place)
# def bucketify(startNum, endNum):
# print("Bucketifying", startNum, "...", endNum)
# place = 0
# currentNum = startNum
# direction = "raising"
# print(currentNum)
# toRetrieve = [currentNum]
# while(currentNum != endNum):
# currentNum, place, direction= _bucketify(currentNum, startNum, endNum, place, direction)
# toRetrieve.append(currentNum)
# print(sorted(list(set(toRetrieve))))
import time
# print(323166712-322136123)
# start = time.time()
# for i in range(323036123, 323166712):
# _getBucketsToUpdate(i)
# end = time.time()
# print("Time Taken:", end-start)
# print("...........................")
start = time.time()
allUpdates = set()
for i in range(323036123, 323036123+2592000):
for val in _getBucketsToUpdate2(i):
allUpdates.add(val)
# allUpdates = allUpdates.union(_getBucketsToUpdate2(i))
end = time.time()
print("Time Taken:", end-start)
print("Total Updates:", len(allUpdates))
print("...........................")
# start = time.time()
# for i in range(323036123, 323166712):
# _getHigherBuckets(i)
# end = time.time()
# print("Time Taken:", end-start)
# # bucketify(1518513475, 1518513532)
# PROOF
# start = time.time()
# for i in range(322136123, 323166712):
# assert (sorted(_getBucketsToUpdate2(i)) == sorted(_getBucketsToUpdate(i)))
# end = time.time()
# print("Time Taken:", end-start)
# print("...........................")