fractional-cascading-benchmark.py

import bisect
import random
import time
from datetime import datetime

def get_locations_1(x, arr):
    return [bisect.bisect_left(l, x) for l in arr]

def get_pos_arr(arr):
    # For each of the element in `arr` positions will hold
    # the location where the element `arr[i][j]` will be inserted.
    positions = []
    for i in range(len(arr)):
        positions.append([])
        for j in range(len(arr[i])):
            positions[i].append([[]] * len(arr[i]))
            positions[i][j] = [-1] * len(arr)

    for i, l in enumerate(arr):
        for j, e in enumerate(l):
            for k, m in enumerate(arr):
                positions[i][j][k] = int(bisect.bisect_left(m, e))

    pos_arr = sorted([
        (y, positions[i][j],)
        for i, x in enumerate(arr)
            for j, y in enumerate(x)
        ], key=lambda x: x[0])

    return pos_arr, list(zip(*pos_arr))[0]


def get_locations_2(x, arr, pos_arr, U):
    index = bisect.bisect_left(U, x)
    if index == len(pos_arr):
        return [len(l) for l in arr]
    return pos_arr[index][1]


def populate_arr(n, k, min_val, max_val):
    arr = []
    for i in range(k):
        arr.append([])
        arr[i] = sorted(random.sample(range(min_val, max_val), n))
    return arr


def get_locations_3(x, arr, m_arr, pointers):
    locations = []
    loc, next_loc = pointers[0][bisect.bisect_left(m_arr[0], x)]
    locations.append(loc)
    for i in range(1, len(m_arr)):
        if x <= m_arr[i][next_loc-1]:
            loc, next_loc = pointers[i][next_loc-1]
        else:
            loc, next_loc = pointers[i][next_loc]
        locations.append(loc)
    return locations


def get_m_arr(arr):
    MIN_VAL, MAX_VAL = -1000000000, 1000000000
    m_arr = []
    m_arr.insert(0, [x for x in arr[-1]])
    for i in range(len(arr) - 2, -1, -1):
        m_arr.insert(0, sorted([x for k, x in enumerate(m_arr[0]) if k % 2] + arr[i]))
    for l in m_arr:
        l.insert(0, MIN_VAL)
        l.append(MAX_VAL)
    # For each of the element in `arr` positions will hold
    # the location where the element `arr[i][j]` will be inserted.
    pointers = []
    for i in range(len(m_arr)):
        pointers.append([])
        for j in range(len(m_arr[i])):
            pointers[i].append([[]] * len(arr[i]))
            pointers[i][j] = [-1] * 2

    for i, l in enumerate(m_arr):
      for j, m in enumerate(m_arr[i]):
        pointers[i][j] = [
            bisect.bisect_left(arr[i], m_arr[i][j]),
            0 if i == len(m_arr) - 1 else bisect.bisect_left(m_arr[i+1], m_arr[i][j]),
        ]

    return m_arr, pointers

def call():
    times = []
    for n in range(1000, 1000000, 500):
        print(n, datetime.now())
        for k in range(10, 11):
            min_v, max_v = 1, 2*n
            arr = populate_arr(n, k, min_v, max_v)
            pos_arr, U = get_pos_arr(arr)
            m_arr, pointers = get_m_arr(arr)

            s0 = time.time()
            l1 = get_locations_1(4, arr)
            t1 = (time.time() - s0) * 1000

            s0 = time.time()
            m1 = get_locations_2(4, arr, pos_arr, U)
            t2 = (time.time() - s0) * 1000

            s0 = time.time()
            n1 = get_locations_3(4, arr, m_arr, pointers)
            t3 = (time.time() - s0) * 1000

            yield (str(n), str(k), str(t1), str(t2), str(t3),)


with open("bench.csv", "w") as f:
    f.write("n,k,t1,t2,t3\n")
    t = call()
    for x in t:
        f.write(",".join(x))
        f.write("\n")
        f.flush()