快速和pythonic的方式来查找字符串是否是回文 [英] Fast and pythonic way to find out if a string is a palindrome
问题描述
我为一种检查字符串是否为回文的方法编写了三种不同的版本.该方法被实现为"str"类的扩展
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"
这些方法还将字符串转换为小写，并删除所有的守时和空格.哪个更好(更快，更pythonic)?
The methods also convert the string to lowercase, and delete all the punctual and spaces. Which one is the better (faster, pythonic)?
以下是方法:
1)这是我想到的第一个解决方案:
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
我认为这是更快的方法，因为没有字符串的转换或反转，并且for语句在第一个不同的元素处中断，但是我认为这不是一种优雅而pythonic的方式
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)在第二个版本中，我使用此处基于stackoverflow的解决方案进行了转换(使用高级切片字符串[::-1])
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)我想到的第三种解决方案是使用迭代器:
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
推荐答案
因此，我决定只是timeit，然后找出哪一个是最快的.请注意，最后一个功能是您自己的pythonicPalindrome的更干净的版本.定义如下:
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]
方法论
我每个功能运行10个不同的测试.在每次测试运行中，该函数使用参数self="aabccccccbaa", other="aabccccccbaa"被调用10000次.结果可以在下面找到.
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
pythonicPalindrome的较干净版本似乎要快一些，但两个功能显然都优于其他版本.
It would appear that the cleaner version of your pythonicPalindrome is marginally faster, but both functions clearly outclass the alternatives.
这篇关于快速和pythonic的方式来查找字符串是否是回文的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
