1

我有一个包含 800 个元素的列表，我在大约 50k 个文件中查找，每个文件大约 50 行。（这些是带有非通用名称的 xml 标签 - 搜索很简单，所以我没有使用 Beautiful soup。）

每次找到一个时，都会缩短 800 个元素的列表。

遍历文件，

我首先检查每一行是否有关系（检查“spot”、“rover”、“fido”等的行）还是一次检查一个元素的所有行（例如，检查文件中的所有行是否有“spot”，然后检查所有行是否有“rover”等...）？

或者这一切都是低效的？（这是使用python。）我在想：

for line in somefile:
        for element in somelist:
              if re.search(element, line):
                  ....

或者：

for element in somelist:
        for line in somefile:
              if re.search(element, line):
                  ....
4

3 回答 3

4

您通常将较大的数据集保留为按顺序访问的数据集，并将您感兴趣的值保留在内存中或作为较大数据集的索引。所以是的，这确实很重要，在您的示例中，您希望多次扫描文件，这要慢得多。

让我们举个例子，这些文件中的每一个都是 50 行，并且您要查找 800 个“单词”。

for filename in filenames:
    for line in open(filename):
        if any(word in line for word in words):
            pass # do something

由于words它在内存中且易于扫描，因此比打开每个文件 800 次要好得多——这是一项昂贵的操作。

所以，我想我应该说你应该尝试顺序扫描“最昂贵”的数据集（可能不是最长的）。

于 2012-10-20T14:43:39.357 回答
3

描述算法复杂性的 big-O 表示法在任何一种方式中都是相同的，但是如果您的一个可迭代对象（例如文件）的访问速度要慢很多并且可能比另一个更大，您应该采取尽可能少地迭代它，即一次。

除此之外，该算法可能更容易以一种或另一种方式编写或理解。例如，如果您想要一个列表中与任何正则表达式匹配的所有字符串的列表，则首先迭代字符串列表并针对每一行检查每个正则表达式会更容易，当一个匹配时打破内部循环。

实际上，当您以这种方式迭代时，整个任务可以是单行的：

foundlines = [line for line in inputlines if any(r.search(line) for r in regexes)]

作为奖励，您将获得 Python 能够通过使用列表理解/生成器表达式实现的最快迭代，并且any().

首先迭代正则表达式，最自然的做法是创建一个与每个正则表达式匹配的行列表列表，或者一个与任何正则表达式匹配的行的大列表（带有重复项），包括多个。如果您想得到最多匹配一个正则表达式的行列表，那么您将需要以某种方式消除重复项（在迭代期间或之后），这将影响算法的复杂性。结果也可能以不同的顺序出现，这可能是一个问题。

简而言之，当迭代的性能相同时，选择最适合您尝试解决的问题的方法。

于 2012-10-20T14:58:11.547 回答
1

复杂性的顺序是O(n*m)，其中 n 和 m 可以表示您的列表和文件中的条目数，因此您先执行哪种方式并不重要。

于 2012-10-20T14:45:23.637 回答