Created
August 15, 2023 03:39
-
-
Save recuraki/3f23b62b4b6f4e4fee124e9f9ebf6a4c to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import time | |
# [1, 2, 3, ...N, 1, 2, 3, ...N]というリストを作る | |
n = 200000 | |
start = time.time() | |
listSeq = list(range(n//2)) | |
d = dict() | |
for x in listSeq: d[x] = True | |
print("listSeq elapsed_time:{0}".format(time.time() - start) + "[sec]") # listSeq elapsed_time:0.0070133209228515625[sec] | |
# [2^17+1(=1), 6,31, 156]というリストを作る | |
d = dict() | |
start = time.time() | |
listCollision = [] | |
mask = (1<<17) - 1 # 0xffff | |
listCollision.append(mask+2) # ind = 1 | |
ind = 6 # ind = 6->31->156... | |
print(listCollision) | |
for i in range(1,43000): # key=1と衝突するキーで埋める。この値が大きすぎると環境により(pypy?)うまくぶつからない。おそらくdk_sizeが変わってしまうのか? | |
listCollision.append(ind) | |
ind = (ind * 5 + 1) & mask | |
print(min(listCollision), max(listCollision)) # -> 5 131073 | |
for i in range(1, n-len(listCollision)): # 1で埋める。(各アクセスは上記で入れたkeyとぶつかる) | |
listCollision.append(1) | |
print("listColision", listCollision[:10]) # listColision [131073, 6, 31, 156, 781, 3906, 19531, 97656, 95065, 82110] | |
for x in listCollision: d[x] = True | |
print("listCollision elapsed_time:{0}".format(time.time() - start) + "[sec]") # listCollision elapsed_time:16.341837167739868[sec] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment