Compare time performance of recursive vs. generator powerset versions. http://stackoverflow.com/q/16731561/

reporttime.py

# -*- coding: utf-8 -*-
import inspect
import sys
import timeit
from functools import partial, wraps
from timeit import default_timer as timer

__version__ = "0.3.0"


def measure_func(func, args):
    """Measure how long `func(*args)` takes in seconds."""
    n = 1
    f = partial(func, *args)  # pylint: disable=W0142
    while True:
        start = timer()
        r = timeit.repeat(f, number=n, repeat=1)
        if timer() - start > 1:  # at least 1 second per measurement
            break
        n *= 2
    return min(r + timeit.repeat(f, number=n, repeat=2)) / n


def accept_funcs(func):
    """Add function names if necessary.

    Decorator for functions that accept either a sequence of functions
    or (name, function) pairs.
    """
    @wraps(func)
    def wrapper(funcs, *args, **kwargs):
        if hasattr(funcs[0], '__name__'):
            funcs = [(f.__name__, f) for f in funcs]
        return func(funcs, *args, **kwargs)
    return wrapper


def human_seconds(seconds, fmt="%.3g %s"):
    """Return human-readable string that represents given seconds."""
    t = 1e6 * seconds  # start with µsec
    for suff in "usec msec".split():
        if t < 1000:
            return fmt % (t, suff)
        t /= 1000
    return fmt % (t, " sec")


@accept_funcs
def measure(funcs, args, comment='', verbose=False):
    """Report how long `f(*args)` takes for each f in funcs."""
    if not comment:
        comment = repr(args)

    # measure performance
    results = []
    w = max(len(name) for name, _ in funcs)
    for name, f in funcs:
        results.append((measure_func(f, args), name))
        if verbose:
            print("{:{}s} {:>9s} {}".format(
                    name, w, human_seconds(results[-1][0]), comment))

    # print sorted results
    results.sort()
    mint = results[0][0]  # minimal time
    ratios = ["%5.2f" % (t / mint,) for t, _ in results]
    maxratio_width = max(len(r) for r in ratios)
    #  header
    print("{:{}s} {:>9s} {:>{}s} {}".format(
            "name", w, "time", "ratio", maxratio_width, "comment"))
    ratios = [s.rjust(maxratio_width) for s in ratios]
    for (t, name), ratio in zip(results, ratios):
        print("{:{}s} {:>9s} {} {}".format(
                name, w, human_seconds(t), ratio, comment))
    return results


def get_functions_with_prefix(prefix, module=None):
    if module is None:  # use caller's module
        modname = inspect.currentframe().f_back.f_globals['__name__']
        module = sys.modules[modname]
    all_funcs = inspect.getmembers(module, inspect.isfunction)
    return [f for name, f in all_funcs if name.startswith(prefix)]

time-subsets.py

#!/usr/bin/env python
"""See http://stackoverflow.com/q/16731561/
"""
import functools
import sys
from copy import deepcopy
from itertools import combinations

from reporttime import accept_funcs, get_functions_with_prefix, measure

def subsets_rec(seq):
    # adapt rec_subsets() to return result
    def rec_subsets(ms, i=0, s=[]):
        if i == len(ms):
            result.append(s)
            return
        rec_subsets(ms, i+1, s)
        rec_subsets(ms, i+1, s + [ms[i]])
    result = []
    rec_subsets(seq)
    return result


def subsets_gen(ms, i=0, s=[]):
    if i == len(ms):
        yield s
        return
    for a in subsets_gen(ms, i+1, s): yield a
    for a in subsets_gen(ms, i+1, s + [ms[i]]): yield a

if sys.version_info[0] > 2:
    exec("""def subsets_gen_pep380(ms, i=0, s=[]):
        if i == len(ms):
            yield s
        else:
            yield from subsets_gen_pep380(ms, i+1, s)
            yield from subsets_gen_pep380(ms, i+1, s + [ms[i]])""")

def subsets_ipowerset(lst):
    if not lst: # empty list
        yield ()
    else:
        for subset in subsets_ipowerset(lst[1:]):
            yield subset
            yield (lst[0],) + subset

def subsets_comb(lst):
    return (comb for r in range(len(lst)+1) for comb in combinations(lst, r))


def consume_result(func):
    @functools.wraps(func)
    def wrapper(*args):
        return list(func(*args))
    return wrapper

@accept_funcs
def test_funcs(funcs, args, normalize=lambda L: sorted(list(x) for x in L)):
    """Check that all functions produce the same result.

    Each function should accept a readonly sequence as an argument
    """
    orig_args = deepcopy(args)
    expected = normalize(funcs[0][1](*args))
    for name, f in funcs:
        r = normalize(f(*args))
        assert r == expected, (name, args, r, expected)
        assert orig_args == args, name


if __name__ == "__main__":
    funcs = list(map(consume_result, get_functions_with_prefix('subsets_')))
    for f in funcs[:]:
        try:
            f(range(3))
        except Exception:
            funcs.remove(f) # exclude from comparison
    test_funcs(funcs, [range(10)])
    measure(funcs, args=[range(20)])
"""
Python 3.3:
name                    time ratio comment
subsets_comb        224 msec  1.00
subsets_ipowerset   483 msec  2.16
subsets_rec         967 msec  4.32
subsets_gen_pep380 2.27  sec 10.13
subsets_gen        2.62  sec 11.71

Python 2.7:
name                   time ratio comment
subsets_comb       172 msec  1.00
subsets_ipowerset  294 msec  1.71
subsets_rec        789 msec  4.59
subsets_gen       1.77  sec 10.31
"""