<jupyter_start><jupyter_text>algorithm<jupyter_code>def timeit(fn, fargs, n_range, seconds=5):
    print(f'[timeit] {seconds} seconds per N')
   
    # timeit for N
    bench = []
    for n in n_range:
        args = fargs(n)
        calls = 0

        # benchmark
        timer = perf_counter()
        while perf_counter() - timer < seconds:
            fn(args)
            calls += 1
        timer = perf_counter() - timer

        # results
        bench.append([np.e, n, timer / calls])
        print(f'[N={n}] {calls / timer:.2f} calls/sec')

    # estimate complexity
    bench = np.log(bench)
    (alpha, beta), *_ = np.linalg.lstsq(bench[:, :2], bench[:, -1])
    print(f'estimated O({np.exp(alpha):.3} * N ^ {beta:.3f})')<jupyter_output><empty_output><jupyter_text>setup<jupyter_code>def combinatorial_sort(data):
    data = data.copy()
    for i, j in combinations(range(len(data)), 2):
        if data[i] > data[j]:
            data[i], data[j] = data[j], data[i]
    return data
def get_array(n):
    return np.random.randint(0, n, n)<jupyter_output><empty_output><jupyter_text>built-in sorted<jupyter_code>n_range = [100, 1000, 10000, 100000, 1000000]
timeit(sorted, get_array, n_range)<jupyter_output>[timeit] 5 seconds per N
[N=100] 44502.77 calls/sec
[N=1000] 3092.61 calls/sec
[N=10000] 231.72 calls/sec
[N=100000] 16.99 calls/sec
[N=1000000] 1.06 calls/sec
estimated O(1.11e-07 * N ^ 1.151)<jupyter_text>numpy sort<jupyter_code>n_range = [100, 1000, 10000, 100000, 1000000]
timeit(np.sort, get_array, n_range)<jupyter_output>[timeit] 5 seconds per N
[N=100] 304622.14 calls/sec
[N=1000] 55807.77 calls/sec
[N=10000] 1966.49 calls/sec
[N=100000] 164.66 calls/sec
[N=1000000] 13.92 calls/sec
estimated O(1.38e-08 * N ^ 1.121)<jupyter_text>combinatorial sort<jupyter_code>n_range = [10, 50, 100, 500, 1000]
timeit(combinatorial_sort, get_array, n_range)<jupyter_output>[timeit] 5 seconds per N
[N=10] 49694.04 calls/sec
[N=50] 2011.77 calls/sec
[N=100] 515.40 calls/sec
[N=500] 19.56 calls/sec
[N=1000] 4.74 calls/sec
estimated O(1.92e-07 * N ^ 2.010)
{'fraction_non_alphanumeric': 0.1576402321083172, 'fraction_numerical': 0.11992263056092843, 'mean_word_length': 3.691609977324263, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '107035', 'license': 'MIT', 'n_tokens_mistral': 1028, 'n_tokens_neox': 823, 'n_words': 178, 'path': '100days/day 31 - timeit.ipynb', 'repo_name': 'gopala-kr/ds-notebooks', 'size': '2068'}