benchmark results

➜  benchmark  python -m cProfile product.py 
         802 function calls in 0.817 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.817    0.817 product.py:1(<module>)
      100    0.812    0.008    0.816    0.008 product.py:5(table)
      100    0.001    0.000    0.001    0.000 {len}
      300    0.002    0.000    0.002    0.000 {map}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      300    0.002    0.000    0.002    0.000 {reduce}


➜  benchmark  python -m cProfile recursion.py
         2819302 function calls (1422802 primitive calls) in 12.905 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001   12.905   12.905 recursion.py:1(<module>)
2095600/699100    9.503    0.000   11.298    0.000 recursion.py:14(loop)
      100    0.007    0.000   12.904    0.129 recursion.py:7(table)
   361900    0.783    0.000    0.783    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   361500    1.013    0.000    1.013    0.000 {method 'format' of 'str' objects}
      100    1.597    0.016   12.896    0.129 {method 'join' of 'str' objects}
      100    0.001    0.000    0.001    0.000 {range}

product.py

import itertools
import operator


def table(*elements):
    rowspans = [
        reduce(operator.mul, map(len, elements[i+1:]), 1)
        for i in xrange(len(elements))
    ]

    result = '<table border="1" width="50%">'
    for row_i, row in enumerate(itertools.product(*elements)):
        result += '<tr>'
        for col_i, col in enumerate(row):
            if (row_i % rowspans[col_i]) == 0:
                result += '<td rowspan="%d">%s</td>' % (rowspans[col_i], col)
        result += '</tr>'
    result += '</table>'

    return result


some_data = [[123] * 15] * 3

for i in xrange(100):
    table(*some_data)

recursion.py

def table(*xs):
    rowspan = [1] + [len(x) for x in reversed(xs)][:-1]
    for i in range(0, len(rowspan) - 1):
        rowspan[i + 1] = rowspan[i] * rowspan[i + 1]

    prefix = ["<tr> "]
    def loop(prefix, result, *xs):
        for y in result:
            yield "{}<td rowspan='{}'>{}</td>".format(prefix[0], rowspan[len(xs)], y)
            prefix[0] = "<tr> " if not xs else ""
            if not xs: yield "</tr>\n"
            else:
                for y in loop(prefix, *xs): yield y

    return "<table border='1' width='50%'>" + "".join(loop(prefix, *xs)) + "</table>"


some_data = [[123] * 15] * 3

for i in xrange(100):
    table(*some_data)