为什么在“反转”字符串中搜索更大的字符串比切片反转花费更多时间？

Question

当我阅读 here 时，使用 reversed 函数反转字符串比切片符号更有效，string[::-1]。但是当我自己尝试时，我观察到不同的结果。

首先，我尝试制作一个非常大的字符串。然后我试着检查检查一个字符串是否存在于大字符串中需要多少时间。这就是我所做的：

In [1]: large = "abcdefgijklmnopqrstuvwxyz1234567890!@#$%^&*()_=+0}{QWERT"                                                                           

In [2]: large = 1000*large                                                                                                                           

In [3]: large = 1000*large  

In [5]: len(large)                                                                                                                                   
Out[5]: 56000000

In [6]: %time "a" in large[::-1]                                                                                                                     
CPU times: user 63 ms, sys: 43.4 ms, total: 106 ms
Wall time: 106 ms
Out[6]: True

In [7]: %time "a" in reversed(large)                                                                                                                 
CPU times: user 11 µs, sys: 1 µs, total: 12 µs
Wall time: 17.6 µs
Out[7]: True

如果我检查 large 中仅存在 1 个字符，reversed 会快得多，但是当我尝试使用更大的字符串时，结果会发生变化：


In [8]: %time "ab" in large[::-1]                                                                                                                    
CPU times: user 99.2 ms, sys: 44.1 ms, total: 143 ms
Wall time: 143 ms
Out[8]: False

In [9]: %time "ab" in reversed(large)                                                                                                                
CPU times: user 1.73 s, sys: 4.48 ms, total: 1.73 s
Wall time: 1.74 s
Out[9]: False
In [10]: %time "abc" in large[::-1]                                                                                                                  
CPU times: user 125 ms, sys: 20 ms, total: 145 ms
Wall time: 145 ms
Out[10]: False

In [11]: %time "abc" in reversed(large)                                                                                                              
CPU times: user 1.72 s, sys: 6.52 ms, total: 1.73 s
Wall time: 1.74 s
Out[11]: False

引擎盖下发生了什么？

Answer 1

两者并不相同，可能会产生不同的布尔结果。例如：

s = "ab"
print("ba" in s[::-1])  # True
print("ba" in reversed(s))  # False

string 上的 in 运算符具有不同的行为：它查找子字符串匹配。迭代器上的 in 运算符将尝试在单独迭代的值上找到匹配项，即在这种情况下为单个字符。

所以你真的不能那样比较这些。

至于为什么获得 False 结果较慢：迭代器将为每个迭代字符创建单独的字符串，然后从头开始比较针字符串（“ba”）。

在字符串版本中，有一个优化的搜索算法可以在更大的字符串中找到一个子字符串，即一个操作Python。高效的字符串搜索算法是在较低级别的代码中实现的，例如 C.

为什么在“反转”字符串中搜索更大的字符串比切片反转花费更多时间？

Why does searching for larger strings in a `reversed` string take more time than slice reversing?

python

performance

reverse