我在解决以下算法问题时变得好奇了，想要理解 Python 中字符串比较的内部工作原理：
给定两个字符串，返回最长公共前缀的长度。
解法1：逐字符比较
我的直觉告诉我，最优解法应该是从两个单词的开头开始用一个光标迭代向前，直到前缀不再匹配。大概像这样：
为了简化代码，该函数假设第一个字符串的长度总是小于或等于第二个字符串的长度。
一开始我以为
出乎意料的是，在进行了一些初步基准测试后，
这张图表展示了以下两点：
1. 预期之中，随着前缀长度的增加，两种算法的性能都呈线性恶化。 2. charByChar算法的性能下降速度要快得多。
为什么binarySearch算法要好得多呢？ 我认为原因如下：
我在cpthon代码中找到了以下两个 片段，但我不确定这是字符串比较发生的地方。
这句话的意思是：“在哪里”。
“cmp（1）”是比较长度为1个字符的两个字符串的成本。
“slice”是访问一个字符的成本，相当于“charAt（i）”。Python具有不可变字符串，访问一个字符实际上会创建一个新的长度为1的字符串。“slice（string_len，slice_len）”是将长度为“string_len”的字符串切片到大小为“slice_len”的切片的成本。
因此，
"log_2" 是将字符串对半分割直到长度为1的次数。
所以
如果我们假设
如果我们将它们等同起来
所以当s1和s2被逐个字符比较时，O(charByChar(s1, s2)) > O(binarySearch(s1, s2))。
给定两个字符串，返回最长公共前缀的长度。
解法1：逐字符比较
我的直觉告诉我，最优解法应该是从两个单词的开头开始用一个光标迭代向前，直到前缀不再匹配。大概像这样：
def charByChar(smaller, bigger):
assert len(smaller) <= len(bigger)
for p in range(len(smaller)):
if smaller[p] != bigger[p]:
return p
return len(smaller)
为了简化代码，该函数假设第一个字符串的长度总是小于或等于第二个字符串的长度。
解决方法2：二分查找
另一种方法是将两个字符串分割成两个前缀子字符串。如果前缀相等，则我们知道公共前缀点至少与中点一样长。否则，公共前缀点至少不大于中点。然后我们可以递归查找前缀长度。
也称为二分查找。
def binarySearch(smaller, bigger):
assert len(smaller) <= len(bigger)
lo = 0
hi = len(smaller)
# binary search for prefix
while lo < hi:
# +1 for even lengths
mid = ((hi - lo + 1) // 2) + lo
if smaller[:mid] == bigger[:mid]:
# prefixes equal
lo = mid
else:
# prefixes not equal
hi = mid - 1
return lo
一开始我以为
binarySearch 会更慢，因为字符串比较会比 charByChar 多次比较所有字符而不仅仅是前缀字符。出乎意料的是，在进行了一些初步基准测试后，
binarySearch 的速度要快得多。
图 A
这张图表展示了以下两点：
1. 预期之中，随着前缀长度的增加，两种算法的性能都呈线性恶化。 2. charByChar算法的性能下降速度要快得多。
为什么binarySearch算法要好得多呢？ 我认为原因如下：
为了验证这一点，我对比了字符串比较和切片操作的性能，分别标记为cmp和slice如下所示： 图B
- 二分查找算法中字符串比较是由解释器/CPU在幕后进行优化的。
- charByChar实际上会为每个访问的字符创建新的字符串，这会产生显着的开销。
- 如预期所示，比较和切片随着长度呈线性增长。
- 与算法性能相比，比较和切片的成本随着长度的增加增长得非常缓慢，如图A所示。请注意，这两个图形都展示了长度为10亿个字符的字符串。因此，将一个字符进行10亿次比较和切片的成本远远大于一次比较1亿个字符。但这仍然没有回答为什么...
Cpython
为了找出cpython解释器如何优化字符串比较，我生成了以下函数的字节码。
In [9]: def slice_cmp(a, b): return a[0] == b[0]
In [10]: dis.dis(slice_cmp)
0 LOAD_FAST 0 (a)
2 LOAD_CONST 1 (0)
4 BINARY_SUBSCR
6 LOAD_FAST 1 (b)
8 LOAD_CONST 1 (0)
10 BINARY_SUBSCR
12 COMPARE_OP 2 (==)
14 RETURN_VALUE
我在cpthon代码中找到了以下两个 片段，但我不确定这是字符串比较发生的地方。
问题
- 在cpython的哪里进行字符串比较？
- 是否有CPU优化？是否有一种特殊的x86指令可以进行字符串比较？如何查看cpython生成的汇编指令？您可以假设我正在使用最新的python3、Intel Core i5、OS X 10.11.6。
- 为什么比较长字符串要比比较每个字符快得多？
奖励问题：何时charByChar更高效？
如果与字符串的其余部分相比，前缀足够小，则在某些情况下，在 charByChar 中创建子字符串的成本会变得小于在 binarySearch 中比较子字符串的成本。
为了描述这种关系，我深入研究了运行时分析。
运行时分析
为了简化以下方程，让我们假设 smaller 和 bigger 大小相同，并将它们称为 s1 和 s2 。
charByChar
charByChar(s1, s2) = costOfOneChar * prefixLen
这句话的意思是：“在哪里”。
costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)
“cmp（1）”是比较长度为1个字符的两个字符串的成本。
“slice”是访问一个字符的成本，相当于“charAt（i）”。Python具有不可变字符串，访问一个字符实际上会创建一个新的长度为1的字符串。“slice（string_len，slice_len）”是将长度为“string_len”的字符串切片到大小为“slice_len”的切片的成本。
因此，
charByChar(s1, s2) = O((cmp(1) + slice(s1Len, 1)) * prefixLen)
二分查找binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)
"log_2" 是将字符串对半分割直到长度为1的次数。
costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)
所以
binarySearch的大O符号将会随着增长。
基于我们之前对成本的分析，binarySearch(s1, s2) = O((slice(s2Len, s1Len) + cmp(s1Len)) * log_2(s1Len))
如果我们假设
costOfHalfOfEachString大致等于costOfComparingOneChar，那么我们可以将它们都称为x。charByChar(s1, s2) = O(x * prefixLen)
binarySearch(s1, s2) = O(x * log_2(s1Len))
如果我们将它们等同起来
O(charByChar(s1, s2)) = O(binarySearch(s1, s2))
x * prefixLen = x * log_2(s1Len)
prefixLen = log_2(s1Len)
2 ** prefixLen = s1Len
所以当s1和s2被逐个字符比较时，O(charByChar(s1, s2)) > O(binarySearch(s1, s2))。
2 ** prefixLen = s1Len
使用上述公式插入，我重新生成了 Figure A 的测试，但字符串的总长度为 2 ** prefixLen，预期这两个算法的性能大致相等。
charByChar的性能要好得多。经过一些试验，当s1Len = 200 * prefixLen时，这两种算法的性能大致相等。
smaller[:mid] == bigger[:mid]和它如何解释smaller[p] != bigger[p]。 - Hadi Brais