1
\$\begingroup\$

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)
\$\endgroup\$
2
  • \$\begingroup\$ I don't mean to be an ass, but it is Project Euler's policy that you should not publish solutions to their problems online, see here. A policy you seem to be making a habit of breaking. If your code works and you got the solution right, then you have access to a protected discussion forum on Project Euler where others have posted their solutions, that's the right place to look for optimizations or ask questions. The first problems are trivial enough so it really doesn't matter, but you are starting to push the limits. Please, don't spoil the fun for others! \$\endgroup\$ – Jaime Apr 30 '14 at 13:26
  • 2
    \$\begingroup\$ @Jaime All these questions have "Project Euler" in the title. One has to take responsibility of ones's own fun and not click on a question that is likely to spoil it. Also, I'm not sure how good a code review you can get on the protected threads on the Euler site. What I've seen is people posting their solution and moving on. \$\endgroup\$ – Janne Karila Apr 30 '14 at 16:19
5
\$\begingroup\$

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))).

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ On your last note: we don't need to feed all the strings. Just construct the palindromes. Another 500x speedup. \$\endgroup\$ – vnp Apr 30 '14 at 20:55
  • \$\begingroup\$ No time for benchmark right now but this is might be worth an answer on its own. \$\endgroup\$ – SylvainD Apr 30 '14 at 21:29
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ For goodness sake, it's a boolean expression, just do return str(n) == str(n)[::-1]. Obscuring the code by adding lots of noise makes it less explicit. \$\endgroup\$ – Adam May 1 '14 at 0:35
  • \$\begingroup\$ The rest of the review is really good though. \$\endgroup\$ – Adam May 1 '14 at 4:03

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.