如何以不同的顺序有效地读取 Python 中的大文本文件行：a）每次随机行，b）从中间开始......？

Question

我有一个大文本文件（500 万到 1000 万行）。每行有 10 到 5,000 个字母数字项，它们之间用 space 或逗号分隔。 每行以换行符结束。行数在运行时间之前已知，并且文本文件在运行时间期间不会更改。

每次代码为运行，将传递50-200个搜索列表，每个包含2-10个项目（词）。对于这些搜索列表中的每一个，我想 在文本文件中找到 x 行 行，其中 至少包含该列表中的一项。行数x范围为5-10行，设置在运行时。匹配不区分大小写，并且必须精确匹配单词边界（例如，"foo" 匹配“,foo”但不匹配“foobar”）。

每个搜索列表都有三种搜索顺序策略之一:

正常。从第一行开始逐行查找连续排序，直到找到 x 行数或到达最后一个行.
随机。从文本文件中随机选择行。继续前进，直到找到 x 行或完成对每一行的搜索。
桶范围。首先搜索最高优先级范围的行，然后是下一个最高优先级范围的行，然后是下一个等等。例如，搜索范围优先级可能是首先查看 1,000,000 到 1,499,999 行，然后是 0 到 999,999 行，然后是行1,500,000 到 2,199,999 等。可以有 3 到 20 个桶，每个桶覆盖 100,000 到 5,000,000 行的范围。桶数和行号范围在运行时给出。在每个范围内，连续搜索。搜索直到找到 x 行或到达最后一个桶的末尾。

这是我为 "normal search" 写的 [此测试代码检查所有行到文件末尾，在 x 行之后不停止；在最终版本中，在找到 x 个搜索列表匹配项后，它将停止并转到下一个搜索列表]:

import re
textFile = "bigTextFile.txt"
searchItems = ["foo","bar","anotherfoo","anotherbar","etc"]
searchStrategy = "normal" #could be "normal", "random", "bucket"; this code is just for "normal"
results = []
with open(textFile) as inFile:
    for line in inFile:
        regex = re.compile('(' + '|'.join('\b'+item+'\b' for item in searchItems) +')', re.IGNORECASE)
        match = regex.search(line)  
        if match is not None:
            analysisResult = analyze_the_match(line)
            results.append(analysisResult)

此代码适用于 "normal search"。在我尝试过的方法中，它似乎是最快的，但我是 Python 的新手，我想一定有更好的方法 (speed/efficiency) 来做到这一点。

[更新评论以更好地解释不同搜索策略的原因]这些项目高度偏斜。研究数据，我发现大约一半的搜索将在 10,000 行之前完成，40% 可能需要几百万行才能找到足够的匹配项，而 10% 的搜索将无法在整个文本文件中找到足够的匹配项。每行中的项目与其所在的行无关，但行的范围相似（即第 100,000-500,000 行相关，1,500,000-1,750,000 行相关，等等）。对于给定的搜索列表，代码可能运行多次，并且对于每个运行，优先级可能是关注不同范围的行。如果整个文本文件只有 x 行包含特定搜索列表中的项目，则结果将始终是那些 x 行。但是对于许多搜索列表，有 2x、10x 或 100,000x 行匹配，并且在不同的时间，我想选择不同的台词。在某些时候，一个特定的范围可能是优先考虑的，在其他时候随机抽样是最好的，有时从头开始找到第一个 x 行就可以了，因此 "normal"、"random" 和 "bucket" 搜索策略。

我非常感谢任何关于 "random" 和 "bucket" 的想法，因为我不确定如何最有效地处理它们。我玩弄了 linecache, itertools islice, readlines (per @Martin Thoma in this answer， readlines 出奇的快），也修改了上面的代码，但是我在 "random" 和 "bucket" 上的尝试都是笨拙的，低效的，并且我知道我还不知道什么是最好的 :)。

有什么建议吗？谢谢。

Answer 1

对于随机搜索和桶搜索，您可以对文件进行线性扫描并构建候选结果列表，如果列表已满并且出现更好的候选结果，则替换列表中的候选结果。

对于随机选择，您只需计算候选人出现在列表中的几率，然后使用随机数来确定候选人是否被列入列表。

对于桶选择，如果候选的桶排名优于现有项目的排名，则候选人将替换现有列表成员。

随机选择：

import random
candidates = []
n = 0
with open(textFile) as inFile:
    for line in inFile:
        if valid_candidate(line): # use regex here
            n += 1
            if n <= x:
                candidates.append(line)
            else:
                i = random.randrange(n)
                if i < x:
                    candidates[i] = line
results = []
for line in candidates:
    analysisResult = analyze_the_match(line)
    results.append(analysisResult)

桶选择：

import bisect
candidates = []
n = 0
with open(textFile) as inFile:
    for line in inFile:
        n += 1
        if valid_candidate(line): # use regex here
            rank = get_rank(n) # use n to determine the bucket and assign a rank, lower numbers are higher rank
            bisect.insort(candidates, (rank, n, line))
results = []
for rank, n, line in candidates[:x]:
    analysisResult = analyze_the_match(line)
    results.append(analysisResult)

如何以不同的顺序有效地读取 Python 中的大文本文件行：a）每次随机行，b）从中间开始......？

How to efficiently read lines of large text file in Python in different orders: a) random line each time, b) starting in middle...?

python

regex

line

python-2.7

linecache