快速且简洁的判断字符串是否为回文的Python方法

Question

[编辑：正如有人指出我错误地使用了回文概念，现在我已经用正确的函数进行了编辑。我还对第一和第三个示例进行了一些优化，在这两个示例中，for语句执行到字符串的一半位置]

我编写了三种不同版本的方法来检查字符串是否为回文。这些方法被实现为类“str”的扩展。

这些方法还会将字符串转换为小写，并删除所有标点符号和空格。哪个更好（更快，更符合Python规范）？

以下是这些方法：

1) 这是我想到的第一个解决方案：

    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

我认为第一种方法更快，因为它没有字符串的转换或反转，并且for循环语句在遇到第一个不同的元素时就会终止。但我不认为这是一种优雅和pythonic的方式。

第二种方法中，我使用了在stackoverflow上找到的解决方案，即使用高级切片string[::-1]进行转换。

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

但我认为切片和字符串比较会使这个解决方案变慢。

3) 我想到的第三种解决方案是使用迭代器：

# 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

我认为这种解决方案更为优雅，比第一种解决方案更高效，比第二种解决方案更简单。

- Nikaido

---

提示：当您想比较相同功能的不同实现时，timeit模块是您的好帮手。 - bruno desthuilliers

等一下，我有点困惑。为什么一个回文检测函数需要有两个参数？“是回文”这个属性只属于一个字符串，而不是两个字符串的组合。“abcba”是一个回文；但（“abc”，“cba”）就不是了。 - Kevin

关于 Python 风格，将其实现为 str 子类的方法是完全不符合 Python 风格的 - 在这里使用纯函数才是 Pythonic 的方式。 - bruno desthuilliers

@Kevin，我认为Nikaidoh的意思是“other是self的反转版本”（不考虑空格、标点和大小写）。 - bruno desthuilliers

使用迭代器的另一个版本：all(map(operator.eq, lowerself, reversed(other)))。 - GingerPlusPlus

Answer 1

所以，我决定只使用timeit来找出哪个是最快的。请注意，最终函数是您自己的pythonicPalindrome的更干净的版本。它的定义如下：

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

方法

我对每个函数进行了10次不同的测试。在每次测试运行中，该函数被调用了10000次，并传递参数self="aabccccccbaa"，other="aabccccccbaa"。下面是结果。

            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

看起来，您的pythonicPalindrome的简化版速度略快，但两个函数显然都优于其他替代方案。

- Nelewout

---

回文的重点在于比较自身，为什么你要将两个字符串传递到你的函数中？ - Mark Ransom

在OP编辑之前，@MarkRansom也做了同样的事情。我也觉得这很不寻常，但我还是接受了。 - Nelewout

抱歉，我的错，我已将该函数重写为回文函数。 - Nikaido

我将函数修改为回文函数。在第一个和第三个示例中，我还进行了一些优化，其中for语句执行到字符串的一半。 - Nikaido

Answer 2

看起来你想知道代码块的执行时间并进行比较。

你可以使用timeit模块。

以下是一个快速的方法：

import timeit

start = timeit.default_timer()

#Your code here

stop = timeit.default_timer()

print stop - start 

阅读更多：

选项 1

选项 2

- dot.Py

---

除了分辨率之外，datetime.datetime.now()和timeit.default_timer()有什么区别？ - BAE

使用 timeit 的规范方式是直接使用它或使用它的 Timer 类... 它会重复执行代码多次，以便得到有意义的平均值。 - bruno desthuilliers

Answer 3

你也可以使用itertools而不是re来计时这个一行代码：

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 " ,.;:?!")))

或者，更详细地解释一下：

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

---

注意，您也可以这样做：(i for i in self.lower() if i not in " ,.;:?!") - DainDwarf

Answer 4

回想一下，filter在字符串上起作用：

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

所以你的测试可以是一个明显的一行代码：

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

或者，如果您要使用正则表达式，只需使用惯用的 str[::-1] 反转结果：

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

最快的方法可能是使用 string.tranlate 来删除字符：

>>> import string
>>> string.translate(st, None, " ,.;:?!")
'OnestringwithpuncThatalsoneedslowercase'
>>> string.translate(st, None, " ,.;:?!")==string.translate(str, None, " ,.;:?!")[::-1]
True

- dawg

Answer 5

当我们传递一个单词时，它会检查它是否可以被反转，如果可以被反转，它会打印出"This is a Palindrome"，否则打印出"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

---

虽然这段代码可能会帮助原帖作者，但最好详细说明您的代码，以便未来的读者也能受益。 - Uwe Plonus

Answer 6

为什么不使用更符合Python风格的方式呢！

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

- user6573621