# The Next Palindrome - reducing total execution time

I tried to solve one SPOJ problem. I wrote one program in Python, however, it got accepted by the SPOJ judges, but its total execution time is 2.88s. The same algorithm used in C language having execution time 0.15s.

Please offer suggestions on improving this approach.

def tempPalindrome(inputString):
""" Code for finding out temporary palindrome. used by nextPalindrome function"""
inputList = list(inputString)
length = len(inputList)
halfL = inputList[:length/2]
halfL.reverse()

if (length % 2) == 0:
inputList = inputList[:length>>1] + halfL
else:
inputList = inputList[:(length>>1)+1] + halfL

#if new palindrome is greater than given number then return otherwise increment it
if ''.join(inputList) > inputString.zfill(length):
return inputList
else:

position  = length >> 1
if length %2 == 0:
position-=1
for i in range(position,  -1,  -1):
if inputList[i] == '9':
inputList[i] = '0'
else:
inputList[i] = chr(ord(inputList[i]) + 1)
break

if (i == 0) and (inputList[i] == '0'):
inputList = ['1'] + inputList
length += 1

halfL = inputList[:length/2]
halfL.reverse()
if (length % 2) == 0:
inputList = inputList[:length>>1] + halfL
else:
inputList = inputList[:(length>>1)+1] + halfL
return inputList
return None

def nextPalindrome():
""" Take an input from user and find next palindrome"""
inputs = list()
noOfCases = int(raw_input())
for i in range(noOfCases):
inputs.append(raw_input())
for inputString in inputs:
inputList = tempPalindrome(inputString)
print ''.join(inputList)
return None

if __name__ == '__main__':
nextPalindrome()


By profiling this code using cProfile profiler, I get the following output:

    >>> 1
99
101
119 function calls in 3.111 CPU seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    3.111    3.111 <string>:1(<module>)
2    0.000    0.000    0.000    0.000 AsyncFile.py:107(flush)
4    0.000    0.000    0.000    0.000 AsyncFile.py:121(fileno)
4    0.000    0.000    0.000    0.000 AsyncFile.py:16(AsyncPendingWrite)
2    0.000    0.000    0.000    0.000 AsyncFile.py:160(readline_p)
4    0.000    0.000    0.000    0.000 AsyncFile.py:261(write)
6    0.000    0.000    0.000    0.000 AsyncFile.py:55(__checkMode)
6    0.000    0.000    0.000    0.000 AsyncFile.py:67(__nWrite)
8    0.000    0.000    0.000    0.000 AsyncFile.py:88(pendingWrite)
2    0.000    0.000    3.111    1.555 DebugClientBase.py:318(raw_input)
2    0.000    0.000    3.111    1.555 DebugClientBase.py:34(DebugClientRawInput)
2    0.000    0.000    0.000    0.000 DebugClientBase.py:374(handleLine)
2    0.000    0.000    0.000    0.000 DebugClientBase.py:965(write)
2    0.000    0.000    3.110    1.555 DebugClientBase.py:987(eventLoop)
1    0.000    0.000    0.000    0.000 nextPalindrome.py:24(tempPalindrome)
1    0.000    0.000    3.111    3.111 nextPalindrome.py:65(nextPalindrome)
7    0.000    0.000    0.000    0.000 socket.py:223(meth)
2    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
2    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
7    0.000    0.000    0.000    0.000 {getattr}
7    0.000    0.000    0.000    0.000 {len}
1    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
2    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
1    0.000    0.000    0.000    0.000 {method 'encode' of 'str' objects}
2    0.000    0.000    0.000    0.000 {method 'encode' of 'unicode' objects}
4    0.000    0.000    0.000    0.000 {method 'fileno' of '_socket.socket' objects}
2    0.000    0.000    0.000    0.000 {method 'find' of 'str' objects}
6    0.000    0.000    0.000    0.000 {method 'find' of 'unicode' objects}
2    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
4    0.000    0.000    0.000    0.000 {method 'recv' of '_socket.socket' objects}
2    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
2    0.000    0.000    0.000    0.000 {method 'rfind' of 'str' objects}
6    0.000    0.000    0.000    0.000 {method 'rfind' of 'unicode' objects}
3    0.000    0.000    0.000    0.000 {method 'sendall' of '_socket.socket' objects}
1    0.000    0.000    0.000    0.000 {method 'zfill' of 'unicode' objects}
2    0.000    0.000    0.000    0.000 {range}
2    3.110    1.555    3.110    1.555 {select.select}

• Could you also provide the timing enviroment? Otherwise we'll have to set it up on our own, it could give different result, we're lazy, etc... etc... :) – Rik Poggi Mar 6 '12 at 17:52
• Actually when I submitted on spoj then it is showing total execution time as 2.88s. Do you need profiled environment or something else. – Sushant Jain Mar 6 '12 at 18:03
• I tried to time tempPalindrome building a random number with num = ''.join(random.choice('0123456789') for _ in xrange(1000000)) and the ipython timeit I got ~ 680ms. Sorry, but I'm not able to reproduce that 2.88s. – Rik Poggi Mar 6 '12 at 18:53
• @RikPoggi The SPOJ machines are very old and slow. – Daniel Fischer Mar 6 '12 at 19:26

Here are a few thoughts:

1. Don't bother to store the inputs in a list, just convert and print as you go. (This saves memory, but not processing time)

2. Converting strings to lists and back again is costing you a lot of time.

3. Looping over all characters is slow, better to use a built-in function if possible. Your main loop seems to be discarding lots of '9' characters so in this case you can use rstrip to do this much faster.

4. I suspect a string functions will be faster than list functions (e.g. I would expect reversing a string to be faster than reversing a list of characters)

In this case, the main optimisation is therefore to keep the processing based on strings rather than lists of characters.

Testing with a million character strings containing all 9s in Python 2.7, the code below is 28 times faster:

def tempPalindrome(inputString):
inputList = inputString
length = len(inputList)
halfL = inputList[:length/2][::-1]
inputList = inputList[:(length+1)>>1] + halfL

if inputList > inputString.zfill(length):
return inputList

position  = (length-1) >> 1
i = len(inputList[:position+1].rstrip('9'))-1
num9s = position-i
if i>=0:
inputList = inputList[:i]+chr(ord(inputList[i]) + 1)+'0'*num9s+inputList[position+1:]
else:
inputList = '1' + '0'*num9s+inputList[position+1:]
length += 1

halfL = inputList[:length/2][::-1]
return inputList[:(length+1)>>1] + halfL

def nextPalindrome():
noOfCases = int(raw_input())
for i in xrange(noOfCases):
print tempPalindrome(raw_input())

• Good answer. I was going to post an answer, but I don't think there's much I can add to this. – Weeble Mar 6 '12 at 22:40
• @Peter Thanks, your approach will be quite helpful for enhancing my programming skills. Only one problem is with point 1, here i have to take all inputs first then print output as a string so any good approach you can suggest so i need not have to store it first in list. – Sushant Jain Mar 7 '12 at 15:03
def tempPalindrome(inputString):


    """ Code for finding out temporary palindrome. used by nextPalindrome function"""
inputList = list(inputString)


Don't use lists. You shouldn't need to convert into lists, and it'll be faster if you avoid that.

    length = len(inputList)
halfL = inputList[:length/2]
halfL.reverse()


You can reverse a string by using string[::-1].

    if (length % 2) == 0:
inputList = inputList[:length>>1] + halfL
else:
inputList = inputList[:(length>>1)+1] + halfL


I suggest not using >> 1 to divide the length in half. Its not going to give you a speed advantage in python, and makes it difficult to read.

    #if new palindrome is greater than given number then return otherwise increment it
if ''.join(inputList) > inputString.zfill(length):


Since you derived length from the length of inputString, why are you zfilling it? Also, not the extra work required to convert back from the list to a string

        return inputList
else:

position  = length >> 1
if length %2 == 0:
position-=1
for i in range(position,  -1,  -1):
if inputList[i] == '9':
inputList[i] = '0'
else:
inputList[i] = chr(ord(inputList[i]) + 1)
break


You are basically reimplementing the process of incrementing a number. Instead, convert your string an actual integer, and then add one to it. EDIT I was wrong. If your numbers are very large converting back and between integers and strings of the numbers will be expensive. For that reason you shouldn't do it. But this for loop is a bad plan because its depends on python's loop mechanism not a c loop.

        if (i == 0) and (inputList[i] == '0'):


You don't need any of those parens.

            inputList = ['1'] + inputList
length += 1

halfL = inputList[:length/2]
halfL.reverse()
if (length % 2) == 0:
inputList = inputList[:length>>1] + halfL
else:
inputList = inputList[:(length>>1)+1] + halfL
return inputList


You've done this before. Write a function that handles the logic.

    return None


Seeing as you should never reach this, why have you included it?

def nextPalindrome():
""" Take an input from user and find next palindrome"""
inputs = list()
noOfCases = int(raw_input())
for i in range(noOfCases):
inputs.append(raw_input())
for inputString in inputs:
inputList = tempPalindrome(inputString)
print ''.join(inputList)


I'm not sure why you are storing the data in a list, and then process it in another loop. Just process the data as you read it.

    return None

if __name__ == '__main__':
nextPalindrome()


Here is my reworking of your code

def make_palindrome(number, odd):
text = str(number)
if odd:
return text + text[::-1][1:]
else:
return text + text[::-1]

def palindrome(inputString):
""" Code for finding out temporary palindrome. used by nextPalindrome function"""

# handle the case that increases the input length as a special case
if inputString.count('9') == len(inputString):
return '1' + '0' * (len(inputString) - 1) + '1'

if len(inputString) % 2 == 0:
odd = False
number = int(inputString[:len(inputString)/2])
else:
odd = True
number = int(inputString[:len(inputString)/2 + 1])

current = make_palindrome(number, odd)
if current > inputString:
return current
else:
return make_palindrome(number + 1, odd)

def main():
""" Take an input from user and find next palindrome"""
noOfCases = int(raw_input())
for i in range(noOfCases):
print palindrome(raw_input())
return None

if __name__ == '__main__':
main()


I've managed to make it simpler, mostly by using appropriate data types i.e. strings and ints rather then lists. Because it does less, it should also be faster. I haven't done extensive testing, so it may not handle all cases correctly.

EDIT

Better version stealing from Rok Poggi

def make_palindrome(text, odd):
return text + text[- odd - 1::-1]

def upped(match):
content = match.group(0)
return chr( ord(content[0]) + 1 ) + '0' * (len(content) - 1)

def palindrome2(inputString, extract = re.compile(r'[^9]9*$')): """ Code for finding out temporary palindrome. used by nextPalindrome function""" # handle the case that increases the input length as a special case if all(letter == '9' for letter in inputString): return '1' + '0' * (len(inputString) - 1) + '1' length = len(inputString) odd = length % 2 number = inputString[:length/2 + odd] current = make_palindrome(number, odd) if current > inputString: return current else: number = extract.sub(upped, number) return make_palindrome(number, odd)  • thanks for explaining stepwise, i got your point. it's working fine with quite less execution time. – Sushant Jain Mar 7 '12 at 16:58 • I don't think it was a bad idea to reimplement the process of incrementing a number, mainly because he'll be working on long integers and the convertion back and forth will take some time. I explained that better in my answer. I've also borrowed the barebone of your rewrite to write my solution, I hope it's ok :) – Rik Poggi Mar 7 '12 at 20:14 • It does look nicer :) From a quick timing it seems though that extract.sub is 19:1 slower than extract.search. In the other scenario I got the same performances. Without the middle charachter you're also bound to to check for 9 in the whole string, and all() is almost 44 times slower than .count(), but again the odds are 1 to ∞ – Rik Poggi Mar 8 '12 at 9:07 • @RikPoggi, I'm not sure that comparing extract.sub and extract.search is fair because extract.sub does a lot more work then extract.search. I'm not following you on the middle character. I'm sure that I could optimize the 9999999 check, but since, as you mention, its highly unlikely to check more then a few characters I didn't bother. My own performance testing shows very similiar timings between the two functions. – Winston Ewert Mar 8 '12 at 17:28 • @Win: I didn't compare them directly. I compared the whole funcions, if I used a 1000000 digits random number that executes those else sentences (in both mine and yours) and I got 19.5 ms with yours against 1.1 ms with mine. That's why I said that search seems to be better than sub. I don't know either what's that middle nonsense ;) Anyway except for that case, I got similar performances too. – Rik Poggi Mar 9 '12 at 9:09 You're copying a lot of lists. This is probably the root of your problem. Learn about the difference between +, += and append, and consider that this may be implemented more efficiently either by working with list indices or slice objects, or by using generator sequences (see itertools). Also, your implementation looks really complex. Try something like this: from itertools import ifilter, count def ispalindrome(num): strnum = str(num) return strnum[::-1] == strnum def nextpalindrome(num): return next(ifilter(ispalindrome, count(num+1)))  • there is a need to change in string frequently so i am changing it to list. And I have tried all the possible list elimination from my side but got failed. Is there another way to do this efficiently. And here how can I use itertools. – Sushant Jain Mar 6 '12 at 17:55 • @SushantJain You have clearly not understood a word I wrote. Learn about the things I have told you to learn about. – Marcin Mar 6 '12 at 18:11 • Here i can't use this code because input number can be 10,000 digits long as specified in problem. So it will take so much time. – Sushant Jain Mar 6 '12 at 18:13 • @SushantJain Good. Understand the things I wrote in my answer. – Marcin Mar 6 '12 at 18:20 • This recommended implementation is inadequate for the specified range of inputs. With a million digit input this could end up going through 10^500000 iterations to find the next palindrome. This computation will not complete with all the resources in the universe. – Weeble Mar 6 '12 at 22:30 ## Review I'm not going in details, since @Winston Ewert already coverd pretty much everything (but I disagree on one point): • There's no need to use lists, strings are iterable too. • There's no need for bitwise operations >>, just divide by two ig that's what you need. • Explicitly call the floor division // (see PEP238), this will give you compatibility with Python 3. • Follow PEP8 and its naming convention. • It was a good idea to reimplement the incrementing process. The reason is that you have long integers, and a whole conversion would be slower. • But you definetly need to do that better! ## all instead of count This: if inputString.count('9') == len(inputString):  aside than the fact that it could work on the first half of the string (moving the check a little later in the work-flow): if half.count('9') == len(half):  has its advantage: for a given length will always took the same amount of time. But what are the odds of having a very very long string of '9' only? Very small, so I think it would be better a different approach: if all(digit == '9' for digit in half):  This will take considerably more for special cases full of '9', but at the meantime considerably less in all the other (that are more). Furthermore if you have a special case the execution is going to end the very next line, so it's alreay a "fast" case. I think the code should be improved for all the others. ## The full power of % There shouldn't be need for True and False booleans, there's already: odd = length % 2  That will be 1 or 0. Also this 1 or 0 will very useful later. ## Odd and even should be more similar The algorithm should be improved to treat odd and even string length at the same way, or in a very similar way. This can be done with: def rik_make_palindrome(half, middle, odd): return (middle*(2-odd)).join((half,half[::-1]))  ## Building the palindrome If the first palindrome was too small, all you need to is to: if middle != '9': middle = str(int(middle) + 1)  increment the middle value (if the middle value is not 9). Otherwise: sub = re.search(r'[^9]9*$', half)
sub = str(int(sub.group()[0]) + 1) + '0' * (len(sub.group()) -1)
half,middle = half[:-len(sub)] + sub, '0'


sub will always match, since you'll get here only if you passed the all check. And this would be the "wiser" way to increment of one a very very long number.

Note: I don't know if regex are allowed, otherwise you'll have to extract parse the string from the end and find the first non-9 digit. It wouldn't be hard to write in "pure" Python, just slower to run.

## Final code

Let's put everything together:

def rik_make_palindrome(half, middle, odd):
return (middle*(2-odd)).join((half,half[::-1]))

def rik_palindrome(input_string, extract=re.compile(r'[^9]9*$')): length = len(input_string) odd = length % 2 half,middle = input_string[:length // 2 + odd -1], input_string[length // 2] temp = rik_make_palindrome(half, middle, odd) if temp > input_string: result = temp elif middle == '9' and all(digit == '9' for digit in half): result = '1' + '0' * (length - 1) + '1' else: if middle != '9': middle = str(int(middle) + 1) else: sub = extract.search(half) sub = str(int(sub.group()[0]) + 1) + '0' * (len(sub.group()) -1) half,middle = half[:-len(sub)] + sub, '0' result = rik_make_palindrome(half, middle, odd) return result  ## Timing This is get_num(): def get_num(digits=1000000): return ''.join(random.choice('0123456789') for _ in xrange(digits))  Where 1000000 is the maximum number of digits (from the spoj site). Small number of random digits: *** n = get_num(digits=1000) *** 6.59 us -- rik_palindrome(n) 17.1 us -- palindrome(n) 51.4 us -- sus_palindrome(n) *** n = get_num(digits=1000-1) *** 3.94 us -- rik_palindrome(n) 17.3 us -- palindrome(n) 51.4 us -- sus_palindrome(n)  Maximum number of randomr digits: *** n = get_num(digits=1000000) *** 1.99 ms -- rik_palindrome(n) 68.2 ms -- sus_palindrome(n) 7.63 s -- palindrome(n) *** n = get_num(digits=1000000-1) *** 1.98 ms -- rik_palindrome(n) 80.2 ms -- sus_palindrome(n) 13.2 s -- palindrome(n)  Any further test or improvement is more than welcome! • It seems to me that you are incorrect for "9992" – Winston Ewert Mar 7 '12 at 20:22 • @WinstonEwert: Good call, Thanks! I was wondering if I had to move the all-9-check later, and it seems I should've. I just edited my answer and fixed it :) – Rik Poggi Mar 7 '12 at 20:42 • This answer reads more like a review of my answer then a review of the original code. You do make good points, and your technique for implementing the increment is very nice. But overall your version seems messier then it needs to be. See my updated post for a new version which steals your good ideas. – Winston Ewert Mar 8 '12 at 1:14 I won't give you the full answer of how to make your code faster, but this helpful stackoverflow post shows a nice tool to visualize your code (that has been profiled). In order to profile I made the following change: noOfCases = 10 inputs = ['50','20','100','20','30','40','50','80','10','1004'] #for i in range(noOfCases): # inputs.append(raw_input())  The command I used to profile was: python -m cProfile -o output.pstats ./yourScript  And then created ( I renamed your script foobar.py ): with the following command(assuming you have download gprof2dot.py from here: gprof2dot.py -f pstats output.pstats | dot -Tpng -o output.png  From this visualization you can see which calls take up the most time, so you can focus your efforts there. Then you can compare new results with old results, slow refining your calculation times! Profiling is a keep step in analyzing were to focus attention when redesigning (with respect to execution time) - hope this helps. • -1, I'm sorry but this is code review. Not tell people how to profile their code. (Nice use of graphs though) – Winston Ewert Mar 7 '12 at 0:56 • @MarmOt Good, This approach helped me quite a lot. thanks – Sushant Jain Mar 7 '12 at 17:28 • @WinstonEwert That's a bit unfair. The question was posted to Stack Overflow. This answer was posted there was and was directly relevant to the question as asked. The question only migrated to Code Review 16 hours ago. Perhaps the question should not have been migrated, but this remains a helpful answer that I would not like to see deleted for fear of downvotes. (That said, it would be more helpful if it profiled with representative data, i.e. with tens of thousands of digits.) – Weeble Mar 8 '12 at 13:10 • @Weeble I won't delete it (maybe someone else will) - I responded here ( for some reason this site doesn't get the 'migrated from' date correct... this was posted a while ago ) it is possibly not enough to qualify as a code review - when I have time I'll update it to show some specific things he can change to improve the execution time – Marm0t Mar 8 '12 at 13:30 • Ah, sorry, I read the question before it was migrated and then when I came back I assumed the timestamps were accurate. – Weeble Mar 8 '12 at 14:33 Generally the approach to finding out why code is so is to profile it. There's a module in the standard library called profile, which is easy to use. I've applied it to your code and I'm not sure why you're getting such slow speeds: daenyth@Bragi tmp$ python2 palindrome.py
1
racecar
racfcar
17 function calls in 2.796 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    2.796    2.796 <string>:1(<module>)
1    0.000    0.000    0.000    0.000 palindrome.py:1(tempPalindrome)
1    0.000    0.000    2.796    2.796 palindrome.py:42(nextPalindrome)
1    0.000    0.000    0.000    0.000 {chr}
1    0.000    0.000    0.000    0.000 {len}
1    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
2    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
2    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'zfill' of 'str' objects}
1    0.000    0.000    0.000    0.000 {ord}
2    0.000    0.000    0.000    0.000 {range}
2    2.796    1.398    2.796    1.398 {raw_input}

daenyth@Bragi tmp \$ echo -e "2\nracecar\nfoobarbazzabrabfoo" | python2 palindrome.py
racfcar
foobarbazzabraboof
25 function calls in 0.000 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1    0.000    0.000    0.000    0.000 <string>:1(<module>)
2    0.000    0.000    0.000    0.000 palindrome.py:1(tempPalindrome)
1    0.000    0.000    0.000    0.000 palindrome.py:42(nextPalindrome)
1    0.000    0.000    0.000    0.000 {chr}
2    0.000    0.000    0.000    0.000 {len}
2    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
4    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
3    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
2    0.000    0.000    0.000    0.000 {method 'zfill' of 'str' objects}
1    0.000    0.000    0.000    0.000 {ord}
2    0.000    0.000    0.000    0.000 {range}
3    0.000    0.000    0.000    0.000 {raw_input}

• Have u changed anything in my code because i am getting quite different profiler(cProfile) output shown in my edited question. – Sushant Jain Mar 6 '12 at 18:10
• @SushantJain: I only ran it on a small number since I didn't have a data set handy. That's probably why. – Daenyth Mar 6 '12 at 18:12