Optimizing Project Euler 36 - double-base palindromes

Question

This one was quick and simple. Any optimizations?

from timeit import default_timer as timer

def sum_double_base_palindromes_under(limit):
    def is_palindrome(n):
        if str(n) == str(n)[::-1]:
            return True
        return False
    sum = 0
    for n in range(limit):
        if is_palindrome(n) and is_palindrome(int(bin(n)[2:])):
            sum += n
    return sum

start = timer()
ans = sum_double_base_palindromes_under(1000000)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

Followup to the last Josay comment. There are million numbers in the range, and only 2000 of them are palindromes (abccba covers all even-length palindromes, and abcba covers all odd-length ones). Traversing just them reduces the number of iterations by 500( a perk benefit is that a test on a decimal string disappears). I'd expect a 500x to 1000x speedup.

So, construct decimal palindromes as a string, trim trailing zeroes, and call is_palindrome(bin(int(s))).

Answer 2

In any programming language, I'd consider (assuming c is a condition with a boolean value):

if c:
    return True
else:
    return False

or it's equivalent :

if c:
    return True
return False

to be an anti-pattern that should be written:

return c

---

Your for loop can easily be rewritten into a more concise (and more efficient according to my benchmarks) way using sum :

return sum(n for n in range(limit) if is_palindrome(n) and is_palindrome(int(bin(n)[2:])))

---

An easy optimisation is not to compute str(n) more than needed :

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

Also, it might even be faster to feed strings to your functions :

def is_palindrome(s):
    return s == s[::-1]
return sum(n for n in range(limit) if is_palindrome(str(n)) and is_palindrome(bin(n)[2:]))

On my machine, running your function 10 times, the running time went from 470 ms to 310 ms per iterations.

Answer 3

Some quick comments:

• I don’t know why you’re defining is_palindrome() within your sum_double_base_palindromes_under() function.

  Since is_palindrome() is a fairly simple function, and you only call the sum function once, the performance hit is negligible. But if the inner function was very complicated, and you called the outer function multiple times, things might slow down.

  It's also worth noting that a function inside a closure can't be used elsewhere. Here's a really trivial example:

  >>> def f(x):
  ...     def g(x):
  ...         return 2 * x
  ...     return x * g(x)
  ...
  >>> f(3)
  18
  >>> g(3)
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  NameError: name 'g' is not defined
  

  I'm not overly familiar with Project Euler, but a palindrome-checker seems like it would be useful elsewhere. You should really only define functions inside another function if you're sure that the inner function will never be used by anything inside the outer function. So pull it out.

• Working on the principle that explicit is better than implicity, I would make a separate else branch for the case where you don't find a palindrome.

  def is_palindrome(n):
      if str(n) == str(n)[::-1]:
          return True
      else:
          return False
  

  I know that seems like a trivial change, but I think it makes the code easier to read.

• Since you're using Python 2, for very large ranges you should probably use xrange() over range(). It makes a significant difference as you start to test with larger arguments.

• Don't use the variable name sum; this is the name of a built-in function. Pick a more specific name that doesn't clash with an existing name; say palindrome_sum.