在Python中优化列表搜索

Question

问题：

给定一个包含 n 个对象的列表（n 的数量级是 10^5），需要快速查找某个特定的项目，同时尽量减少空间和时间的消耗。目前的解决方案还没有优化，原始的方案 耗时太长，且占用内存太多。

这些对象没有主要的排序依据，但可以在一定程度上进行排序，比如下面这个例子，第一列是已经排序的。

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

如果你的数据在一个CSV文件里，你可以试试sql2csv这个工具：https://sourceforge.net/projects/sql2csv/。

补充一下：抱歉我刚才记错了，我其实是想说这个项目：https://github.com/ccoffey/sql4csv/wiki/Examples。

Answer 2

在我看来，一个常见的解决办法是使用数据库查询。可以用SQL（直接写SQL语句或者用某种ORM工具），或者用某种对象数据库，比如MongoDB？

Answer 3

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万年。我很确定你只有线性时间复杂度，只是数据量太大了。

可以把filter替换成itertools.ifilter，这样就不会生成整个列表。Python会一次从列表中取出一个元素，经过三个测试后，如果通过就返回给你。这样可以节省内存，速度也可能更快。

除非你使用一些索引技术，否则你无法在O(n)的时间复杂度上再有所提升。不过，索引技术的适用性取决于你在test1/test2/test3函数中做的事情。如果你需要帮助，可以给出这些函数的示例。

正如其他人提到的，数据库就是为了解决这些问题而设计的。你想要加快速度，只有通过重新实现数据库已经为你做的事情，效果才会好一些。