ordered_list_search.py

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)