Python中在长字符串搜索子串为何比在列表中搜索字符串快很多

基于你提供的测试用例：

str_test = "some string words "*100
def search_in_string():
    if "with" in (str_test):
        return True
    
ls_test = ["some", "string" "words"]*100
def search_in_list():
    if "with" in (ls_test):
        return True

import timeit
print(timeit.timeit(search_in_string))
### 输出：0.3497438999984297   

print(timeit.timeit(search_in_list))
### 输出：2.4319190999995044

测试结果中字符串搜索速度接近列表的7倍，核心原因有以下几点：

• 底层匹配算法的性能差异
  字符串的in操作是子串存在性校验，CPython底层对该操作做了深度优化，采用Boyer-Moore-Horspool这类高效模式匹配算法，只需要对字符串的连续内存块做单次扫描即可完成校验，最坏时间复杂度为O(n)，实际运行时常数项极低，没有额外的对象访问开销。
  而列表的in操作是线性遍历所有元素，每次匹配都需要先做元素类型校验，再执行目标字符串与当前元素的全等匹配，相当于要执行N次独立的字符串比对操作，叠加的开销远高于单轮子串扫描。
• 内存布局与CPU缓存效率差异
  Python字符串是连续存储的字符数组，整块数据可以被CPU一次性加载到高速缓存中，扫描过程中缓存命中率极高，很少出现访问主存的高开销操作。
  而列表存储的是指向独立字符串对象的指针，每个字符串对象分散存储在堆内存中，遍历过程中需要多次随机寻址访问内存，缓存命中率低，额外增加了大量内存访问开销。
• 测试用例的逻辑差异补充
  你当前的测试逻辑本身不对等：字符串的in是判断是否存在子串，而列表的in是判断是否存在与目标完全相等的元素。如果调整为对等逻辑（列表遍历每个元素判断是否包含目标子串），列表的搜索速度会进一步降低。你当前测试中目标字符串"with"在两个容器中都不存在，所以都会执行全量扫描，依然能体现两种操作的基础开销差异。

内容的提问来源于stack exchange，提问作者cLwill