python - 优化 Python 中的列表搜索

Question

问题:

给定 n 个对象的列表(n 的数量级为 10^5)，以最小的时空权衡非常快速地搜索给定项目。当前未经优化的原型(prototype)解决方案需要太长时间并且消耗太多RAM(也就是说，优化不为时过早)。

对象中没有用于排序的主键，但可以进行一定程度的排序，例如下面的示例，其中对第一列进行排序。

o1 => f, g, h
o2 => f, g, i
o3 => f, j, k
o4 => k, j, m

迄今为止，解决方案是嵌套过滤器:

filter(test1, filter(test2, filter(test3, the_list)))

但是这很慢，因为它涉及 n * (n - 1) * (n - 2) 次操作，接近 O(n^3) 速度，并且至少有 n*2 个额外的引用列表。

请注意，最好进行就地搜索。

我还没有找到处理这个问题的标准库。这个问题的典型解决方案是什么？

Answer 1

filter(test1, filter(test2, filter(test3, the_list)))

首先，这是 O(n) 时间，而不是 O(n^3) 时间。时间相加不相乘。唯一可能更糟糕的是，如果 test3/test2/test1 正在做一些奇怪的事情，我们应该看看这些。

是否建议每次测试？函数需要 10 毫秒，那么我们就有 10*3*10^5 毫秒 = 50 分钟。如果是 n^3，那么我们就有 (10*10^5)^3 = 3100 万年。我很确定你只有一个线性时间，你只有大量的数据。

将过滤器替换为itertools.ifilter，它将避免生成列表。相反，Python 会一次从列表中提取一项，让其通过三个测试，当且仅当通过时才将其提供给您。它将避免内存需求，并且可能会更快。

除非您使用一些索引技术，否则您将无法提高 O(n) 时间。然而，索引技术的适用性取决于您在 test1/test2/test3 函数中所做的事情。如果您需要这方面的帮助，请显示这些函数的示例。

正如其他人所指出的，数据库就是为了解决这些问题而设计的。您只能通过糟糕地重新实现数据库已经为您所做的事情来加快速度。