<jupyter_start><jupyter_text>Lookup performance checkLet's check the performance of the lookup function by creating a random set of N elements<jupyter_code>import random
from time import time

#V1: linear code ~ N

def lookup(L, v):
    for i in range(len(L)):
        if L[i] == v:
            return i
        elif L[i] > v:
            return -1
    return -1

#V2: dicotomic search ~ log N
def lookup_rec(L, v, start,end):
    if end < start:
        return -1
    else:
        m = (start + end)//2
        if L[m] == v: #found!
            return m
        elif v < L[m]: #look to the left
            return lookup_rec(L, v, start, m-1)
        else: #look to the right
            return lookup_rec(L, v, m+1, end)
        

        
if __name__ == "__main__":
    values = [random.randint(-30,30) for x in range(0,50000000)]
    
    searched_vals = [random.randint(-30,30) for x in range(1000)]
    input("Ready?")
    for i in range(1,5):
        st = time()
        print("V1: {} elements. Looking for {}, index: {}. Elapsed time: {:.3f}s".format(100000000*i,
                                                                           searched_vals[i],
                                                                           lookup(values[0:10000000*i], searched_vals[i]), 
                                                                           time()-st))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11245551601423487, 'fraction_numerical': 0.036298932384341634, 'mean_word_length': 1.4494773519163764, 'pattern_counts': {'":': 1, '<': 7, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 3, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '45536', 'license': 'Apache-2.0', 'n_tokens_mistral': 438, 'n_tokens_neox': 410, 'n_words': 126, 'path': 'lookup_performance.ipynb', 'repo_name': 'lucabianco78/sciproAlgo2020', 'size': '1405'}