2

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

每次运行代码，都会传递 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行或到达最后一个桶的末尾。

这是我为“正常搜索”编写的内容[此测试代码检查文件末尾的所有行，而不会在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)

此“正常搜索”代码有效。在我尝试过的方法中，它似乎是最快的，但我是 Python 新手，我想一定有更好的方法（速度/效率）来做到这一点。

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

我真的很感激任何关于“随机”和“桶”的想法，因为我不确定如何最好地有效地接近它们。我玩弄linecache, itertools islice, readlines（根据@Martin Thoma 在这个答案中，readlines速度非常快），以及修改上面的代码，但我对“随机”和“桶”的尝试都是笨拙、低效的，我知道我不知道什么是最好的:)。

有什么建议么？谢谢。

4

1 回答 1

0

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

对于随机选择，您只需计算候选人在列表中的几率，并使用随机数来确定候选人是否被放置在列表中。

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

对于随机选择：

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)
于 2016-04-21T04:08:12.743 回答