remove_all benchmark

remove_all.py

import collections
import random
import time


def elapsed_time(f):
    start = time.time()
    result = f()
    finish = time.time()
    return result, finish - start


def pair_to_int(n, m):
    d = n + m
    return d * (d + 1) / 2 + m


def test(n, k, m):
    r = random.Random(pair_to_int(n, k))

    fs = (
        (remove_all_1, False),
        (remove_all_2, False),
        (remove_all_3, False),
        (remove_all_4, True )
    )

    elapsed = [0] * len(fs)
    for _ in range(m):
        a = tuple(r.randrange(k) for _ in range(n))
        vv = r.randrange(k + 1)
        answer = None
        for i, (ra, shuffled) in enumerate(fs):
            if shuffled and vv not in a:
                continue
            aa = list(a)
            _, t = elapsed_time(lambda: ra(aa, vv))
            if answer is None:
                assert not shuffled
                answer = aa
            else:
                try:
                    if shuffled:
                        assert collections.Counter(aa) == collections.Counter(answer)
                    else:
                        assert aa == answer
                except AssertionError:
                    print(a)
                    print(ra.__name__, shuffled)
                    print(answer)
                    print(aa)
                    raise
            elapsed[i] += t

    print()
    print(n, k, '' if len(a) > 20 else a)
    for (ra, _), et in zip(fs, elapsed):
        print(ra.__name__, '{:10d}'.format(n), '{:9.6f}'.format(et / m))


def remove_all_1(a, vv):
    a[:] = [v for v in a if v != vv]


def remove_all_2(a, vv):
    i = 0
    for v in a:
        if v != vv:
            a[i] = v
            i += 1
    del a[i:]


def remove_all_3(a, vv):
    try:
        i = a.index(vv)
    except ValueError:
        return
    k = 0
    while i < len(a):
        try:
            ii = a.index(vv, i + 1)
        except ValueError:
            ii = len(a)
        a[i - k:ii - 1 - k] = a[i + 1:ii]
        k += 1
        i = ii
    del a[-k:]


def remove_all_4(a, vv):
    i = 0
    k = len(a) - 1
    while True:
        i = a.index(vv, i)
        if i > k:
            break
        a[i], a[k] = a[k], a[i]
        k -= 1
    del a[k + 1:]


for n in range(0, 100):
    for k in range(1, 100):
        test(n, k, 10)


for p in range(1, 8):
    n = 10 ** p
    k = n // 10
    test(n, k, 10)