perf.py

class Link:
    """A linked list."""
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '<'
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + '>'

def link_insert_head(r):
    rr = reversed(r)
    link = Link(next(rr))
    for i in rr:
        link = Link(i, link)
    return link

def list_insert_head(r):
    l = []
    for i in reversed(r):
        l.insert(0, i)
    return l

def link_insert_end(r):
    it = iter(r)
    start = Link(next(it))
    for i in it:
        p = start
        while not p.rest == Link.empty:
            p = p.rest
        p.rest = Link(i)
    return start

def list_insert_end(r):
    l = []
    for i in r:
        l.append(i)
    return l

def link_insert_mid(r):
    it = iter(r)
    start = Link(next(it))
    length = 0
    for v in it:
        p = start
        position = length // 2
        i = 0
        while not p.rest == Link.empty and i < position:
            p = p.rest
            i += 1
        p.rest = Link(v, p.rest)
        length += 1
    return start

def list_insert_mid(r):
    l = []
    for i in r:
        l.insert(len(l) // 2, i)
    return l

def link_search(r):
    midpoint = (r.stop - r.start) // 2
    start = link_insert_head(r)
    p = start
    while not p.rest == Link.empty:
        if p.first == midpoint:
            return True
        p = p.rest
    return False

def list_search(r):
    midpoint = (r.stop - r.start) // 2
    l = list(r)
    return midpoint in l

def link_index(r):
    midpoint = (r.stop - r.start) // 2
    start = link_insert_head(r)
    p = start
    i = 0
    while not p.rest == Link.empty and i < midpoint:
        p = p.rest
        i += 1
    return p.first

def list_index(r):
    midpoint = (r.stop - r.start) // 2
    l = list(r)
    return l[midpoint]

def link_len(r):
    start = link_insert_head(r)
    p = start
    i = 0
    while not p.rest == Link.empty:
        p = p.rest
        i += 1
    return i

def list_len(r):
    return len(list(r))

def link_sum(r):
    start = link_insert_head(r)
    acc = 0
    while not start.rest == Link.empty:
        acc += start.first
        start = start.rest
    return acc

def list_sum(r):
    return sum(list(r))

l = locals()
import timeit
from itertools import product
def timings(r = 1000, n = 10):
    timings = {}
    for m, t in product(['insert_head', 'insert_mid', 'insert_end', 'search', 'index', 'len', 'sum'], ['link', 'list']):
        k = f"{t}_{m}"
        f = l[k]
        timings[k] = timeit.timeit(lambda: f(range(r)), number=n)
        print(f"{k}: {timings[k]}")
    return timings