# Quick and dirty benchmark to demonstrate that binary search is
# competitive against dictionaries based on hashes

from time import time
import numpy
from query_ext import BinarySearch

#nelem = 500000
nelem = 500000
bits64 = 2**63
numpy.random.seed(1)

def calibrate_loop():
    for i in xrange(nelem):
        x = rnd[i]

def do_dict_queries():
    for i in xrange(nelem):
        x = rnd[i]
        t = id2name[x]
        #print x,":",t,","

def do_binary_queries(query):
    for i in xrange(nelem):
        x = rnd[i]
        t = query[x]
        #print x,":",t,","

# Create the original key list
keys = numpy.empty(nelem, dtype='i8')
keys[:] = numpy.random.rand(nelem)*bits64

# Create a list of keys to iterate over
rnd = numpy.random.randint(0, nelem, nelem)
rnd = keys[rnd]

# Get a regular list for keys and rnd
keys = keys.tolist()
rnd = rnd.tolist()

print "Calibrating loop..."
t1 = time()
calibrate_loop()
tref = time()-t1
print "Calibrating time:", round(tref, 3)

print "Creating the dictionary..."
id2name = {}
t1 = time()
for i in xrange(nelem):
    id2name[keys[i]] = i
print "Time for dict creation:", round(time()-t1, 3)

print "Timing queries with a dict..."
t1 = time()
do_dict_queries()
print "Time for dict query:", round((time()-t1)-tref, 3)

# Get rid of the dictionary
del id2name

# Build the array of strings
values = range(nelem)

print "Creating BinarySearch object..."
t1 = time()
query = BinarySearch(keys, values)
print "Time for BinarySearch creation:", round(time()-t1, 3)

print "Timing queries with a BinarySearch..."
t1 = time()
do_binary_queries(query)
print "Time for BinarySearch queries:", round((time()-t1)-tref, 3)