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

第二个要快得多，下面是一些测量数据：

def get_mother_of_all_strings():
    return "abcdefg\nhijklmnopqr\nstuvwxyz\naatargetbb"

first: 2.00
second: 0.26

Answer 2

如果只匹配一次以查看子字符串是否在字符串中，则这两种方法几乎相同，并且将其拆分为单独的逐行搜索将获得更多开销；因此，大字符串搜索要快一些。

如果您必须进行多个匹配，那么我将标记字符串并将它们放入字典或集合并存储在内存中。

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

Answer 3

可能是当然是第二个，我认为在大字符串中搜索和在小字符串中搜索没有任何区别。由于行较短，您可能会跳过一些字符，但拆分操作也有其成本（搜索\n，创建n个不同的字符串，创建列表），循环是在python中完成的。

string__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

txt文件实际上是圣经，我在这里找到的：http://patriot.net/~bmcgin/kjvpage.html（文本版本）