Typical example of finding pairs of ints adding to target with a slow and fast algorithm

linear_and_squared.py

from contextlib import contextmanager
import time
import random


def find_two_slow(lst, target):
    result = set()
    for a in lst:
        for b in lst:
            if a + b == target:
                res = (a, b) if a < b else (b, a)
                result.add(res)
    return result


def find_two_fast(lst, target):
    d = {}
    for item in lst:
        d[target - item] = item

    result = set()
    for item in lst:
        if item in d:
            a, b = item, d[item]
            res = (a, b) if a < b else (b, a)
            result.add(res)
    return result


@contextmanager
def timed(n, label):
    start = time.perf_counter()
    yield
    diff = time.perf_counter() - start
    print(f'[{label}] Size of {n} took {diff:.6f} seconds.')


def main():
    # exp=4 takes about ~5 sec for slow
    # adding exp=5 would take about ~500 secs (5-10 minutes) for slow
    # (tested on an older laptop)
    for exp in (1, 2, 3, 4):
        size = 10 ** exp
        lst = list(range(size))
        target = size * 3 // 2  # 1.5 times
        with timed(size, 'slow'):
            a = find_two_slow(lst, target)
        with timed(size, 'fast'):
            b = find_two_fast(lst, target)

        assert a == b
        print(len(a), 'results')


if __name__ == '__main__':
    main()