6

[Edit: as someone pointed out I have used improperly the palindrom concept, now I have edited with the correct functions. I have done also some optimizations in the first and third example, in which the for statement goes until it reach half of the string]

I have coded three different versions for a method which checks if a string is a palindrome. The method are implemented as extensions for the class "str"

The methods also convert the string to lowercase, and delete all the punctual and spaces. Which one is the better (faster, pythonic)?

Here are the methods:

1) This one is the first solution that I thought of:

    def palindrom(self):
        lowerself = re.sub("[ ,.;:?!]", "", self.lower())
        n = len(lowerself)
        for i in range(n//2):
            if lowerself[i] != lowerself[n-(i+1)]:
               return False
        return True

I think that this one is the more faster because there aren't transformations or reversing of the string, and the for statement breaks at the first different element, but I don't think it's an elegant and pythonic way to do so

2) In the second version I do a transformation with the solution founded here on stackoverflow (using advanced slicing string[::-1])

# more compact
def pythonicPalindrom(self):
    lowerself = re.sub("[ ,.;:?!]", "", self.lower())
    lowerReversed = lowerself[::-1]
    if lowerself == lowerReversed:
        return True
    else:
        return False

But I think that the slicing and the comparision between the strings make this solution slower.

3) The thirds solution that I thought of, use an iterator:

# with iterator
def iteratorPalindrom(self):
    lowerself = re.sub("[ ,.;:?!]", "", self.lower())
    iteratorReverse = reversed(lowerself)
    for char in lowerself[0:len(lowerself)//2]:
        if next(iteratorReverse) != char:
            return False
    return True

which I think is way more elegant of the first solution, and more efficient of the second solution

Nikaido
  • 4,443
  • 5
  • 30
  • 47
  • 5
    hint : the `timeit` module is your friend when you want to compare differents implementations of a same feature. – bruno desthuilliers Jan 06 '16 at 15:42
  • 7
    Wait, I'm confused. Why would a palindrome-detecting function take two parameters? "is a palindrome" is a property of a single string, not of a pair of strings. "abcba" is a palindrome; ("abc", "cba") is not. – Kevin Jan 06 '16 at 15:42
  • 1
    wrt/ pythonicity, implementing this as a method on `str` subclass is totally unpythonic - the pythonic way here would be to use a plain function. – bruno desthuilliers Jan 06 '16 at 15:46
  • @Kevin yeps I think what Nikaidoh means is "other is a reversed version of self" (spaces, punctuations and capitalization set aside). – bruno desthuilliers Jan 06 '16 at 15:47
  • Yes, @kevin, is as bruno says, now I'm going to edit – Nikaido Jan 06 '16 at 15:49
  • Another version with iterators: `all(map(operator.eq, lowerself, reversed(other)))` – GingerPlusPlus Jan 06 '16 at 16:04
  • I modified the functions as palindrome functions. I have done also some optimizations in the first and third example, in which the for statement goes until it reach half of the string – Nikaido Jan 06 '16 at 16:38

6 Answers6

5

So, I decided to just timeit, and find which one was the fastest. Note that the final function is a cleaner version of your own pythonicPalindrome. It is defined as follows:

def palindrome(s, o):
    return re.sub("[ ,.;:?!]", "", s.lower()) == re.sub("[ ,.;:?!]", "", o.lower())[::-1]

Methodology

I ran 10 distinct tests per function. In each test run, the function was called 10000 times, with arguments self="aabccccccbaa", other="aabccccccbaa". The results can be found below.

            palindrom       iteratorPalindrome      pythonicPalindrome      palindrome  
1           0.131656638            0.108762937             0.071676536      0.072031984
2           0.140950052            0.109713793             0.073781851      0.071860462
3           0.126966087            0.109586756             0.072349792      0.073776719
4           0.125113136            0.108729573             0.094633969      0.071474645
5           0.130878159            0.108602964             0.075770395      0.072455015
6           0.133569472            0.110276694             0.072811747      0.071764222
7           0.128642812            0.111065438             0.072170571      0.072285204
8           0.124896702            0.110218949             0.071898959      0.071841214
9           0.123841905            0.109278358             0.077430437      0.071747112
10          0.124083576            0.108184210             0.080211147      0.077391086

AVG         0.129059854            0.109441967             0.076273540      0.072662766
STDDEV      0.005387429            0.000901370             0.007030835      0.001781309

It would appear that the cleaner version of your pythonicPalindrome is marginally faster, but both functions clearly outclass the alternatives.

Nelewout
  • 6,281
  • 3
  • 29
  • 39
  • The whole point of a palindrome is that it compares to itself, why do you pass two strings into your function? – Mark Ransom Jan 06 '16 at 16:20
  • @MarkRansom before OP's edit, he did the exact same thing. I considered it.. unusual also, but I just rolled with it. – Nelewout Jan 06 '16 at 16:21
  • Sorry, my bad, I have rewritten the function as palindrome function – Nikaido Jan 06 '16 at 16:22
  • I modified the functions as palindrome functions. I have done also some optimizations in the first and third example, in which the for statement goes until it reach half of the string – Nikaido Jan 06 '16 at 16:39
1

It seems that you want to know the execution time of your blocks of code and compare them.

You can use the timeit module.

Here's a quick way:

import timeit

start = timeit.default_timer()

#Your code here

stop = timeit.default_timer()

print stop - start

Read more:

Option 1

Option 2

Community
  • 1
  • 1
dot.Py
  • 5,007
  • 5
  • 31
  • 52
  • what is the difference between datetime.datetime.now() and timeit.default_timer() besides resolution – BAE Jan 06 '16 at 15:50
  • The canonical way to use `timeit` is to either use it directly or to use it's `Timer` class... It repeats the code quite a few times so you get a meaningful average. – bruno desthuilliers Jan 06 '16 at 15:54
1

You could also time this one-liner that does not use re, but itertools instead:

def isPalindrom(self):
    return all(i==j for i, j in itertools.zip_longest((i.lower() for i in self if i not in " ,.;:?!"), (j.lower() for j in self[::-1] if j not in " ,.;:?!")))

Or, explained in more details:

def isPalindrom(self):
    #using generators to not use memory
    stripped_self = (i.lower() for i in self if i not in " ,.;:?!")
    reversed_stripped_self = (j.lower() for j in self[::-1] if j not in " ,.;:?!")
    return all(self_char==reversed_char for self_char, reversed_char in itertools.zip_longest(stripped_self, reversed_stripped_self))
DainDwarf
  • 1,651
  • 10
  • 19
1

Recall that filter works on strings:

>>> st="One string, with punc. That also needs lowercase!"
>>> filter(lambda c: c not in " ,.;:?!", st.lower())
'onestringwithpuncthatalsoneedslowercase'

So your test can be a one liner that is obvious in function:

>>> str
'!esacrewol sdeen osla tahT .cnup htiw ,gnirts enO'
>>> filter(lambda c: c not in " ,.;:?!", st.lower())==filter(lambda c: c not in " ,.;:?!", str.lower()[::-1])
True

Or, if you are going to use a regex, just reverse the result with the idiomatic str[::-1]:

>>> "123"[::-1]
'321'
>>> re.sub(r'[ ,.;:?!]', '', st.lower())==re.sub(r'[ ,.;:?!]', '', str.lower())[::-1]
True

The fastest may be to use string.tranlate to delete the characters:

>>> import string
>>> string.translate(st, None, " ,.;:?!")
'OnestringwithpuncThatalsoneedslowercase'
>>> string.translate(st, None, " ,.;:?!")==string.translate(str, None, " ,.;:?!")[::-1]
True
dawg
  • 98,345
  • 23
  • 131
  • 206
0

When we pass a word it checks if it can be reversed,If it can be reversed it prints "This is a Palindrome". or "This is NOT a Palindrome"

def reverse(word):
    x = ''
    for i in range(len(word)):
        x += word[len(word)-1-i]
        return x

word = input('give me a word:\n')
x = reverse(word)
if x == word:
    print('This is a Palindrome')
else:
    print('This is NOT a Palindrome')
Madhusudhan R
  • 301
  • 1
  • 5
  • 17
  • While this code may help the original poster it would be nice to elaborate your code so that it may be of help for future readers also. – Uwe Plonus Mar 01 '18 at 11:46
0

Why not using a more pythonic way!

def palindrome_checker(string):
     string = string.lower()
     return string == string[::-1] # returns a boolean