Skip to content

Instantly share code, notes, and snippets.

@blindFS
Last active August 29, 2015 14:07
Show Gist options
  • Save blindFS/427f13aa2c4b55d41552 to your computer and use it in GitHub Desktop.
Save blindFS/427f13aa2c4b55d41552 to your computer and use it in GitHub Desktop.
import random
import math
import time
n = 9999
val = range(1, n+1)
random.shuffle(val)
def get_ptr(v):
if v < n:
return val.index(v+1)+1
else:
return 0
ptr = map(get_ptr, val)
head = val.index(1)
def search(x, i):
while x > val[i]:
i = ptr[i]-1
return i+1
def a(x):
return search(x, head)
def b(x):
i = head
max = val[i]
for j in range(int(math.sqrt(n))):
if max < val[j] <= x:
i = j
max = val[j]
return search(x, i)
def c(x):
i = head
max = val[i]
sqrt_n = int(math.sqrt(n))
group_i = random.randint(0, sqrt_n)
for j in range(sqrt_n):
index = j*sqrt_n+group_i
y = val[index]
if max < y <= x:
i = index
max = y
return search(x, i)
def d(x):
i = random.randint(0, n-1)
y = val[i]
if x < y:
return search(x, head)
if x > y:
return search(x, ptr[i])
def calc_time(func):
start = time.time()
for num in range(1, n+1):
func(num)
end = time.time()
print "took %.2f seconds" % (end-start)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment