binary search stuff, for fun

binary_search_stuff.py

"""we play with large sorted integer arrays"""

import timeit
from typing import Union, Tuple
import random
ar_a = list(range(0, 10))
ar_b = list(range(-5, 5, 1))

ar_c = list(range(-100, 100))
ar_d = list(range(90, 101))

ar_solution = [0, 1, 2, 3, 4]

def intersect_trivial(a: list, b: list):
    """use the python API"""
    return list(set(a).intersection(set(b)))

def intersect(a: list, b: list):
    """intersection alg for sorted int arrays
    
    for each element of a:
        compare it to each element of slice[start:] of b:
        if it matches
            start <- index in b
            start over with next element    
    """
    met_bound = 0
    res = []
    for el in a:
        start = 0
        for i, el2 in enumerate(b[start:]):
            if el2 == el:
                start = i
                res.append(el)
                break
            elif el2 > el:
                start = i
                break
    return res

reports_depth = []
def lookup(needle: int, haystack: Union[range, list], ex=0):
    """binary partition for lookup, very naive algorithm that will copy slices around and thus be memory-intensive"""
    lh = len(haystack)
    mid = haystack[int(lh / 2)]
    if lh == 1:
        reports_depth.append(ex)
        return haystack[0] == needle
    elif mid > needle:
        return lookup(needle, haystack[0:int(lh / 2)], ex + 1)
    elif mid < needle:
        return lookup(needle, haystack[int(lh / 2):], ex + 1)
    else:
        # found
        reports_depth.append(ex)
        return True

def lookup_opti(needle: int, haystack: Union[range, list], start=0, end=None, ex=0, path=None):
    """binary partition that does not copy the haystack but rather just passes around indices, which should be a bit nicer on memory"""
    if end is None:
        end = len(haystack)
    lh = end - start
    mid = haystack[int(lh / 2) + start] 
    if lh == 1:
        reports_depth.append(ex)
        return haystack[0] == needle
    elif mid > needle:
        # take first half - same start but different end
        return lookup_opti(needle, haystack, start, start + int(lh / 2), ex + 1)
    elif mid < needle:
        # take second half - same end but different start
        return lookup_opti(needle, haystack, start + int(lh / 2), end, ex + 1)
    else:
        # found
        reports_depth.append(ex)
        return True
stk = range(0, 20_000_000, 2) # using range allows to have a shallow symbolic structure that does not take up memory and doesn't need to be passed by value (python slices are slice-by-value)
lstk = list(stk)
print(len(stk))

def lookup_giga_opti(needle: int, haystack: Union[list, range], pre_check_size=1000) -> bool:
    """use a gross lookup of where a value could be before with specified granularity before doing a native test of existence in a dumb, linear way"""
    start_bound, end_bound = gross_lookup_opti(needle, haystack, pre_check_size)
    to_chk = haystack[start_bound:end_bound]

    # return needle in to_chk # let's not cheat lol
    for elem in to_chk:
        if needle == elem:
            return True
        elif elem > needle:
            return False
    return False

def gross_lookup_opti(needle: int, haystack: Union[list, range], set_size=1000) -> Tuple[int, int]:
    """do a gross lookup of where an element could be in a sorted haystack and return its best guess, with a given size parameter"""
    s_size = len(haystack)
    start_point = 0
    mid_point = start_point + int(s_size / 2)
    while s_size > set_size:
        midval = haystack[mid_point]
        # update the set size
        s_size = mid_point - start_point
        if midval >= needle:
            # in case the middle value is more than our value we know
            # our value may only be on the left side of the set
            # so let's set mid_point to the middle of the left side
            # and check again
            mid_point = start_point + int(s_size / 2)
            continue
        elif midval < needle:
            # then we know the needle may only be on the right side of the
            # set. we shift the start point to the mid point and offset the
            # mid point to the center of the remainder
            start_point = mid_point
            mid_point = start_point + int(s_size / 2)
            continue
    return (start_point, mid_point)

def do_test():
    """this proves that my code outperforms naive 'in'
    my optimized code is faster on values, and has consistent time for matches and non-matches because it will do just anything between 20 and 24 executions for any result (bounded by n so that 2**(n-1) < len(haystack) and 2**n > len(haystack))
    """ 
    print("my code")
    print(timeit.timeit(lambda: lookup(50051, stk), number=10000))
    print(timeit.timeit(lambda: lookup(50000, stk), number=10000))
    print(timeit.timeit(lambda: lookup(500000, stk), number=10000))
    print(timeit.timeit(lambda: lookup(999999900000, stk), number=10000))
    print("my opti code")
    print(timeit.timeit(lambda: lookup_opti(50051, stk), number=10000))
    print(timeit.timeit(lambda: lookup_opti(50000, stk), number=10000))
    print(timeit.timeit(lambda: lookup_opti(500000, stk), number=10000))
    print(timeit.timeit(lambda: lookup_opti(999999900000, stk), number=10000))
    print("my opti code on values")
    print(timeit.timeit(lambda: lookup_opti(50051, lstk), number=1000))
    print(timeit.timeit(lambda: lookup_opti(50000, lstk), number=1000))
    print(timeit.timeit(lambda: lookup_opti(500000, lstk), number=1000))
    print(timeit.timeit(lambda: lookup_opti(999999900000, lstk), number=1000))
    print("native on range")
    print(timeit.timeit(lambda: 50051 in stk, number=10000))
    print(timeit.timeit(lambda: 50000 in stk, number=10000))
    print(timeit.timeit(lambda: 500000 in stk, number=10000))
    print(timeit.timeit(lambda: 999999900000 in stk, number=10000))
    print("native on values")
    print(timeit.timeit(lambda: 50051 in lstk, number=1000))
    print(timeit.timeit(lambda: 50000 in lstk, number=1000))
    print(timeit.timeit(lambda: 500000 in lstk, number=1000))
    print("just doing that dastard non-match 10 times")
    print(timeit.timeit(lambda: 999999900000 in lstk, number=10))
    print(min(reports_depth), max(reports_depth))
    print(do_test.__doc__)

def ri(a, b):
    return random.randint(a, b)

def do_smaller_test():
    num_to_test = ri(100, 9_999_999)
    print(f"testing number {num_to_test} and random neighbors...")
    print("basic binpart lookup")
    print(timeit.timeit(lambda: lookup(num_to_test + ri(-100, 100), stk), number=10000))
    print("mere binpart opti")
    print(timeit.timeit(lambda: lookup_opti(num_to_test + ri(-100, 100), stk), number=10000))
    print("giga binpart opti with various linear lookup sizes")
    for i in (1, 2, 3, 6, 12, 25, 50, 100, 200, 400, 800, 1600):
        print(f"\t{i}")
        print(timeit.timeit(lambda: lookup_giga_opti(num_to_test + ri(-100, 100), stk, i), number=10000))
#do_test()
do_smaller_test()

example_execution.md

execution example

testing number 4192140 and random neighbors...
basic binpart lookup
0.24330062000080943
mere binpart opti
0.16545362501346972
giga binpart opti with various linear lookup sizes
    1
0.10087132500484586
    2
0.09616238399758004
    3
0.10445303999586031
    6
0.15915612000389956
    12
0.15437415400811005
    25
0.10395679700013716
    50
0.09354111501306761    
    100
0.0990587440028321    
    200
0.12257004099956248    
    400
0.16662622400326654
    800
0.1676528810057789
    1600
0.16182698900229298
(finished in 3.73s)