4 ms·
For comparison, I translated it pretty directly to Python: import sys from math import sqrt def string_palindrome(num): s = str(num)
by bajsejohannes 14y ago
For comparison, I translated it pretty directly to Python:
import sys
from math import sqrt
def string_palindrome(num):
s = str(num)
return s == s[::-1]
sys.stdin.readline() # throw away first line (number of cases)
for count, line in enumerate(sys.stdin):
found = 0
start, finish = [int(num) for num in line.split(" ")]
sqrt_start = int(sqrt(start ))
sqrt_finish = int(sqrt(finish))
for x in xrange(sqrt_start, sqrt_finish+1):
if string_palindrome(x):
square = x * x
if string_palindrome(square) and start <= square <= finish:
found += 1
print("Case #%d: %d" % (count, found))
For the first 15 test cases I get the following run times:
pypy 2.0-beta2: 1.6 seconds
pypy 1.9: 2.1 seconds
ruby 1.9.3p194: 3.7 seconds
python 3.3.0: 5.9 seconds
python 2.7.1: 6.2 seconds
The integer version for checking palindromes was also much slower in python.
Edit: Even though the interger version of _palindrome is slower in pypy, there's another optimization that works there, but is slow in cpython. It brings the run time down to 0.6 seconds!
def half_string_palindrome(num):
num_str = str(num)
num_len = len(num_str)
for i in xrange(0, num_len // 2):
if num_str[i] != num_str[num_len - i - 1]:
return False
return True
- raverbashing 14y agoCheck with PyPy if you can
- afeezaziz 14y agoI have tested PyPy and think that it is good that I would be able to use Python to write faster loops.
- TillE 14y agoI just tested, and it should be about 6x faster than Python 2.7. About 1.0 second for the first fifteen cases.
- bajsejohannes 14y agoGood idea! Updated results.
- deleted 14y ago[deleted]
- berdario 14y agowhat does "ruby 1.9.3p194: 3.7 seconds" mean?
- tr4656 14y agoIt means using Ruby 1.9.3 patch level 194 took 3.7 seconds.
- berdario 14y agook, but on which code? he only posted the python implentation which btw is a straight port of the original ruby script, that takes 53 minutes to run so: 3.7seconds seems quite impossible
- bajsejohannes 14y agoI'm using the ruby code from the blog post. I'm also just running the 15 first test cases out of the 10001 he uses.
- majke 14y agoI quickly checked my naive solution against cpython 2.7 and pypy-2.0-beta1 and it seems to be at least as fast as your code: ispalindrome = lambda a: a[::-1] == a
- d0mine 14y agoTo improve CPython performance slightly, put the code into a function (global vs. local lookup).
- codygman 14y agoDone a bit hastily, let me know if I got something wrong. But here's a racket (formerly plt scheme) solution: #lang racket (define (palindrome? lst) (equal? lst (foldl cons empty lst))) (define ITERATIONS 10000000) (for ([i (in-range ITERATIONS)]) (palindrome? '(i))) time racket palindrome.rkt real 0m0.893s user 0m0.864s sys 0m0.024s Here are some other solutions done in racket for those that are interested: http://www.go-hero.net/jam/13/solutions/0/3/Racket http://www.go-hero.net/jam/13/solutions/0/3/Racket
- stevepike 14y agoI don't think you can just pass '(i) to palindrome? here - doesn't the number need to be converted to a list of digits first? I got #t for everything using your code. I took some code off SO and it bumped up the runtime substantially: #lang racket (require srfi/1 srfi/26) (define (digits->list num (base 10)) (unfold-right zero? (cut remainder <> base) (cut quotient <> base) num)) (define (palindrome? lst) (equal? lst (foldl cons empty lst))) (define ITERATIONS 10000000) (for ([i (in-range ITERATIONS)]) (palindrome? (digits->list i))) racket palindrome.rkt 11.66s user 0.55s system 99% cpu 12.293 total I'm a racket beginner so I'd be interested in better answers to this.