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\$
  • \$\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 '11 at 3:18
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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Should that be 1.3x? \$\endgroup\$ – bluepnume Nov 22 '11 at 22:43
  • \$\begingroup\$ @bluepnume: well, it is 3.3x with python 3.2 and 1.3x with python 2.7. \$\endgroup\$ – Keith Randall Nov 22 '11 at 23:20
  • \$\begingroup\$ Oh wow, that's impressive -- didn't realise 3.2 had sped things up so much! \$\endgroup\$ – bluepnume Nov 22 '11 at 23:32
  • \$\begingroup\$ tweaking your code, I could go up to 3.58x on Python 3.2 \$\endgroup\$ – JBernardo Nov 24 '11 at 2:25
  • \$\begingroup\$ transform R into a list and do the comprehension inside the tuple \$\endgroup\$ – JBernardo Nov 24 '11 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)))
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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