The Next Palindrome - reducing total execution time

Question

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}

Answer 1

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

Answer 2

def tempPalindrome(inputString):

Python convention is to name function lowercase_with_underscores. Also what is temporary about this palindrome?

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

Answer 3

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

Answer 4

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!

Answer 5

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.

Answer 6

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}