1
\$\begingroup\$

Here's a link to the problem. Is there any way I could optimize/speed up this code, perhaps make it more Pythonic?

"""How many distinct terms are in the sequence
generated by a^b for 2 <= a <= 100
and 2 <= b <= 100?"""

import math
from timeit import default_timer as timer

def distinctPowers(a_max, b_max):
    products = []
    for a in range(2, a_max + 1):
        for b in range(2, b_max + 1):
            if a ** b not in products:
                products.append(a ** b)
    return len(products)

start = timer()
ans = distinctPowers(100, 100)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %r in %r ms." % (ans, elapsed_time)
\$\endgroup\$
  • 1
    \$\begingroup\$ What would you like to know about your code? It appears correct to me. Are you trying to speed it up? \$\endgroup\$ – clutton Apr 19 '14 at 16:42
  • \$\begingroup\$ On a styling note, mixedCase is almost never used in Python. "mixedCase is allowed only in contexts where that's already the prevailing style (e.g. threading.py), to retain backwards compatibility." See legacy.python.org/dev/peps/pep-0008 \$\endgroup\$ – Sahand Apr 19 '14 at 20:33
3
\$\begingroup\$

You should check the data structure that you use. You are currently using a list, checking if the power exists, and then doing it again when you append unique entries.

If you use a set then you can skip the check and do an add of the power. This is significantly faster... about 50 times if I calculated correctly. Your function would then look like this:

def distinctPowers(a_max, b_max):
    products = set()
    for a in range(2, a_max + 1):
        for b in range(2, b_max + 1):
            products.add(a ** b)
    return len(products)
\$\endgroup\$
  • \$\begingroup\$ Using a list comprehension to create an iterator may also imrove runtime. \$\endgroup\$ – Cu3PO42 Apr 19 '14 at 19:39
3
\$\begingroup\$

You can append all of the items to list without checking for uniqueness and in the end get unique elements by converting the list to the set. With this you can write a one-liner:

def distinctPowers(a_max, b_max):
    return len(set([a**b for a in range(2, a_max + 1) for b in range(2, b_max + 1)]))
\$\endgroup\$
  • \$\begingroup\$ List comprehesions always doing magic... \$\endgroup\$ – matheussilvapb Apr 21 '14 at 18:31

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.