4
\$\begingroup\$

I'd be interested to see who can come up with the fastest function to produce multiplication tables, in the following format:

   1   2   3   4   5   6   7   8   9  10  11  12
   2   4   6   8  10  12  14  16  18  20  22  24
   3   6   9  12  15  18  21  24  27  30  33  36
   4   8  12  16  20  24  28  32  36  40  44  48
   5  10  15  20  25  30  35  40  45  50  55  60
   6  12  18  24  30  36  42  48  54  60  66  72
   7  14  21  28  35  42  49  56  63  70  77  84
   8  16  24  32  40  48  56  64  72  80  88  96
   9  18  27  36  45  54  63  72  81  90  99 108
  10  20  30  40  50  60  70  80  90 100 110 120
  11  22  33  44  55  66  77  88  99 110 121 132
  12  24  36  48  60  72  84  96 108 120 132 144

Use the following template to benchmark your code using a 12-width table, and post your code and the resulting time here.

#!/usr/bin/python
import timeit
cycles = 100000

referencecode = r'''

def multable(width):
  '\n'.join(''.join('{0:4}'.format(x*y) for x in range(1,width+1)) for y in range(1,width+1))

'''

yourcode = r'''

def multable(width):
  pass # Your function here

'''

referencetime = timeit.Timer('multable(12)', setup=referencecode).timeit(number=cycles)
yourtime = timeit.Timer('multable(12)', setup=yourcode).timeit(number=cycles)

print 'Your code completed', referencetime / yourtime, 'times faster than the reference implementation'
\$\endgroup\$
1
  • \$\begingroup\$ In the template, your multable() is missing a return. Also it might be a good idea to have the template check if the two multable()s return the same output. \$\endgroup\$
    – marinus
    Nov 23, 2011 at 3:18

3 Answers 3

2
\$\begingroup\$

About 352 times faster, according to the benchmark code

(on my machine)
Python 2.7

Exactly how much faster it is will vary widely between machines. I tested it on my web server also and there it was only 288 times as fast.

import itertools as i, operator as o

def multable(width, m={}):
   if not width in m.keys():
      m[width] = '\n'.join(['%4d'*width]*width)%tuple(i.starmap(o.mul,i.product(range(1,width+1),repeat=2)))
   return m[width]

The actual algorithm is only about 1.25 times as fast as the reference one, but if you have a function which is called often, caching the result saves a lot of time.

\$\endgroup\$
1
\$\begingroup\$
def multable(width):
  R=range(1,width+1)
  M=[i*j for i in R for j in R]
  return(('%4d'*width+'\n')*width)%tuple(M)

about 3.3x faster than the reference implementation.

\$\endgroup\$
5
  • \$\begingroup\$ Should that be 1.3x? \$\endgroup\$
    – bluepnume
    Nov 22, 2011 at 22:43
  • \$\begingroup\$ @bluepnume: well, it is 3.3x with python 3.2 and 1.3x with python 2.7. \$\endgroup\$ Nov 22, 2011 at 23:20
  • 1
    \$\begingroup\$ Oh wow, that's impressive -- didn't realise 3.2 had sped things up so much! \$\endgroup\$
    – bluepnume
    Nov 22, 2011 at 23:32
  • \$\begingroup\$ tweaking your code, I could go up to 3.58x on Python 3.2 \$\endgroup\$
    – JBernardo
    Nov 24, 2011 at 2:25
  • \$\begingroup\$ transform R into a list and do the comprehension inside the tuple \$\endgroup\$
    – JBernardo
    Nov 24, 2011 at 2:26
0
\$\begingroup\$

My approach (python2.7):

1.63x Faster

from itertools import imap, izip, starmap, product
from operator import mul

def multable(width):
  return '\n'.join(imap(''.join, izip(*((imap('{:4}'.format, starmap(mul, product(xrange(1,13), repeat=2))),) * 12))))

2.32x Faster

from itertools import starmap, product
from operator import mul

def multable(width):
  return (('{:4}' * width + '\n') * width).format(*starmap(mul, product(xrange(1,13), repeat=2)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.