Python 字符串搜索效率

Question

对于非常大的字符串（跨越多行），使用Python内置的字符串搜索功能是否比将大字符串拆分（可能是按\n来拆分）然后逐个搜索小字符串更快呢？

比如，对于非常大的字符串：

for l in get_mother_of_all_strings().split('\n'):
 if 'target' in l:
   return True
return False

或者

return 'target' in get_mother_of_all_strings()

Answer 1

如果你只是想检查一个子字符串是否在某个字符串里出现过一次，那么这两种方法差不多。不过，把它拆分成逐行搜索会增加一些额外的开销，所以直接在大字符串中搜索会稍微快一点。

如果你需要进行多次匹配，那我建议把字符串分割成小块，放进一个字典或者集合里，并把它们存储在内存中。

s = 'SOME REALLY LONG STRING'
tokens = set(s.split())
return substring in tokens

Answer 2

import timeit

a = #a really long string with multiple lines and target near the end

timeit.timeit(stmt='["target" in x for x in a.split("\\n")]', setup='a = """%s"""'%a)
23.499058284211792
timeit.timeit(stmt='"target" in a', setup='a = """%s"""'%a)
5.2557157624293325

所以，直接在一个大字符串里搜索要比在一堆小字符串里分开搜索快得多。

Answer 3

肯定是第二种方法更好，我觉得在一个大字符串里搜索和在多个小字符串里搜索没什么区别。虽然因为行短可能会跳过一些字符，但分割操作也有它的成本（比如要搜索 \n，创建n个不同的字符串，还要生成列表），而且循环是在Python里进行的。

字符串的 __contain__ 方法是用C语言实现的，所以速度明显更快。

另外要考虑的是，第二种方法在找到第一个匹配项后就会停止，但第一种方法在开始搜索之前会先把整个字符串分割开。

这可以通过一个简单的基准测试很快证明：

import timeit

prepare = """
with open('bible.txt') as fh:
    text = fh.read()
"""

presplit_prepare = """
with open('bible.txt') as fh:
    text = fh.read()
lines = text.split('\\n')
"""

longsearch = """
'hello' in text
"""

splitsearch = """
for line in text.split('\\n'):
    if 'hello' in line:
        break
"""

presplitsearch = """
for line in lines:
    if 'hello' in line:
        break
"""


benchmark = timeit.Timer(longsearch, prepare)
print "IN on big string takes:", benchmark.timeit(1000), "seconds"

benchmark = timeit.Timer(splitsearch, prepare)
print "IN on splitted string takes:", benchmark.timeit(1000), "seconds"

benchmark = timeit.Timer(presplitsearch, presplit_prepare)
print "IN on pre-splitted string takes:", benchmark.timeit(1000), "seconds"

结果是：

IN on big string takes: 4.27126097679 seconds
IN on splitted string takes: 35.9622690678 seconds
IN on pre-splitted string takes: 11.815297842 seconds

bible.txt 文件确实是《圣经》，我在这里找到了它：http://patriot.net/~bmcgin/kjvpage.html（文本版本）