当我解决以下示例算法问题时，我很想了解字符串比较在 python 中的工作原理：
给定两个字符串，返回最长公共前缀的长度
解决方案 1：charByChar
我的直觉告诉我，最佳解决方案是从两个单词开头的一个光标开始，然后向前迭代，直到前缀不再匹配。就像是
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)
为了简化代码，该函数假定第一个字符串的长度smaller始终小于或等于第二个字符串的长度bigger。
解决方案 2：binarySearch
另一种方法是将两个字符串平分以创建两个前缀子字符串。如果前缀相等，我们知道公共前缀点至少和中点一样长。否则，公共前缀点至少不大于中点。然后我们可以递归找到前缀长度。
又称二分查找。
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
上面显示了随着前缀长度的增加，性能如何受到影响。后缀长度保持不变，为 50 个字符。
这张图显示了两件事：
- 正如预期的那样，随着前缀长度的增加，两种算法的线性表现都会变差。
- 性能以
charByChar更快的速度下降。
为什么binarySearch好多了？我认为这是因为
- 中的字符串比较
binarySearch大概是由幕后的解释器/CPU优化的。charByChar实际上为每个访问的字符创建新字符串，这会产生很大的开销。
为了验证这一点，我对比较和切片字符串的性能进行了基准测试，分别在下面标记cmp和标记。slice
图B
这张图显示了两个重要的事情：
- 正如预期的那样，比较和切片随长度线性增加。
- 相对于算法性能，比较和切片的成本随着长度的增长非常缓慢，图 A。请注意，这两个数字都上升到长度为 10 亿个字符的字符串。因此，比较 1 个字符 10 亿次的成本要比比较 10 亿个字符一次要大得多。但这仍然没有回答为什么......
蟒蛇
为了找出 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
我浏览了 cpython 代码，发现了以下两段代码 ，但我不确定这是发生字符串比较的地方。
问题
- 字符串比较在 cpython 中的哪个位置发生？
- 有CPU优化吗？是否有特殊的 x86 指令可以进行字符串比较？如何查看 cpython 生成了哪些汇编指令？您可能会认为我使用的是最新的 python3、Intel Core i5、OS X 10.11.6。
- 为什么比较长字符串比比较每个字符要快得多？
额外问题：charByChar 什么时候性能更高？
如果前缀与字符串的其余长度相比足够小，则在某些时候创建子字符串的成本charByChar会小于比较 in 的子字符串的成本binarySearch。
为了描述这种关系，我深入研究了运行时分析。
运行时分析
为了简化下面的等式，我们假设smaller和bigger大小相同，我将它们称为s1和s2。
逐字符
charByChar(s1, s2) = costOfOneChar * prefixLen
在哪里
costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)
cmp(1)比较两个长度为 1 字符的字符串的成本在哪里？
slice是访问 char 的成本，相当于charAt(i). Python 具有不可变的字符串，访问 char 实际上会创建一个长度为 1 的新字符串。这是将长度字符串切片为 sizeslice(string_len, slice_len)切片的成本。string_lenslice_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)
所以 big-O 的binarySearch会根据
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
所以O(charByChar(s1, s2)) > O(binarySearch(s1, s2)当
2 ** prefixLen = s1Len
因此，插入上面的公式，我为图 A 重新生成了测试，但字符串的总长度2 ** prefixLen预计两种算法的性能大致相等。
但是，显然charByChar性能要好得多。通过一些试验和错误，两种算法的性能大致相等s1Len = 200 * prefixLen
为什么关系是 200 倍？