# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.8.5 64-bit
#     name: python385jvsc74a57bd0aee8b7b246df8f9039afb4144a1f6fd8d2ca17a180786b69acc140d282b71a49
# ---

import random
import timeit
import math


def rand_tuple_gen(x, tuples = []):
    random.seed(42)
    
    for i in range(x*10):
        rnd = random.randint(1, x)
        i = 0
        while i < len(tuples) and rnd != tuples[i][0]:
            i += 1

        if i == len(tuples): # add new tuple
            tuples.append((rnd, 1))
        else:
            tuples[i] = (rnd, tuples[i][1] + 1)

    return tuples


rand_tuple_gen(100)

# %timeit rand_tuple_gen(100)
a = rand_tuple_gen(100)

# %timeit rand_tuple_gen(100, a)


# %timeit rand_tuple_gen(20)

# %timeit rand_tuple_gen(40)

# %timeit rand_tuple_gen(80)

def rand_bin_tuple_gen(x):
    random.seed(42)
    tuples = []

    def bin_insert(rnd, start, end):
        if end < start: # element not found
            tuples.insert(start, (rnd, 1))
            return
        
        split = (start + end) // 2
        if tuples[split][0] == rnd: # already exists
            tuples[split] = (rnd, tuples[split][1] + 1)
            return
        elif tuples[split][0] < rnd:
            return bin_insert(rnd, split + 1, end)
        else:
            return bin_insert(rnd, start, split - 1)
    
            

    for i in range(x*10):
        rnd = random.randint(1, x)
        bin_insert(rnd, 0, len(tuples)-1)

    return tuples

rand_bin_tuple_gen(10)


# %timeit rand_bin_tuple_gen(10000)

# %timeit rand_bin_tuple_gen(200)

def rand_int_index_solution(x):
    random.seed(42)
    lst = [0] * x

    for i in range(x*10):
        rnd = random.randint(1, x)
        lst[rnd-1] += 1

    return lst


rand_int_index_solution(10)


# %timeit rand_int_index_solution(10000)

# %timeit rand_int_index_solution(20000)

def rand_int_dict(x):
    random.seed(42)
    d = {}

    for i in range(x*10):
        rnd = random.randint(1, x)

        if rnd not in d:
            d[rnd] = 0
        d[rnd] += 1

    return d


# a = %timeit rand_int_dict(10)
a

# %timeit rand_int_dict(10000)

# a = %timeit rand_int_dict(20000)

# +


def measure_times(func, last_result_only=False, number=1):
    """
    Runs func on successively growing data (amount doubled for each run) and measures time for comparison
    :param func: function to measure times for
    :param number: number of runs per measurement (default: 1 because of long duration with large data already)
    :return: None
    """
    n = 10
    times = []
    t1 = timeit.timeit(lambda: func(n), number=number)
    times.append((n, t1))
    if not last_result_only:
        print(n, ' values: ', t1, 'sec')
    while t1 < 10 and n < 1000000:
        n *= 2
        t0 = t1
        t1 = timeit.timeit(lambda: func(n), number=number)
        times.append((n, t1))
        if not last_result_only:
            print(n, ' values: ', t1, 'sec, ratio: ', t1 / t0)
    if last_result_only:
        print(n, ' values: ', t1, 'sec, ratio: ', t1 / t0)

    return times



# -

simple_list_times = measure_times(rand_int_index_solution)
dict_times = measure_times(rand_int_dict)
bin_search_times = measure_times(rand_bin_tuple_gen)
seq_search_times = measure_times(rand_tuple_gen)

# +
import matplotlib.pyplot as plt
import numpy as np


lsts = [("Einfache Liste", simple_list_times), ("Dictionary", dict_times), ("Binärsuche", bin_search_times), ("Sequenzielle Suche", seq_search_times)]

for lst in lsts:
    x, y = np.array(lst[1]).T
    plt.plot(x, y, label=lst[0])



plt.title('Laufzeit der 4 Versuche')
plt.xlabel('Problemgrösse n')
plt.ylabel('Laufzeit [s]')
plt.legend()
plt.yscale("linear")
plt.show()
# -



StarcoderdataJupyterScriptsDedupFiltered