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 0.000 0.000 AsyncIO.py:44(readReady) 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}
tempPalindrome
building a random number withnum = ''.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. \$\endgroup\$ – Rik Poggi Mar 6 '12 at 18:53