基于lis的Python优化搜索

Question

问题：

给定一个n对象的列表（n的数量级为10^5），以最小的时空折衷非常快速地搜索给定的项。当前，未优化的原型解决方案需要太长时间，并且消耗了太多的RAM（也就是说，优化是不成熟的）。在

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

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

到目前为止，解决方案是嵌套过滤器：

^{pr2}$

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

值得注意的是，最好进行就地搜索。在

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

Answer 1

即使在内存中，10^5也不是很多对象。littletable是我编写的一个小模块，用于模拟查询、数据透视等，只使用Python dicts。littletable查询的一个优点是，任何查询或联接的结果本身都是一个新的littletable表。索引作为keys->；表对象的dict保存，并且可以定义索引键是否唯一。在

我创建了一个有3个单字母键的140K个对象的表，然后查询特定的键。构建表本身的时间最长，索引和查询非常快。在

from itertools import product
from littletable import Table,DataObject

objects = Table()
alphas = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alphas += alphas.lower()
import time

print "building table", time.time()
objects.insert_many(
    DataObject(k1=k1, k2=k2, k3=k3, created=time.time())
        for k1,k2,k3 in product(alphas.upper(),alphas,alphas)
    )
print "table complete", time.time()
print len(objects)

print "indexing table", time.time()
for k in "k1 k2 k3".split():
    objects.create_index(k)
print "index complete", time.time()

print "get specific row", time.time()
matches = objects.query(k1="X", k2="k", k3="W")
for o in matches:
    print o
print time.time()

印刷品：

^{pr2}$

Answer 2

连接每个对象的属性值以生成唯一的键。为了保证唯一性，可能必须将属性填充到相同的长度。构造一个哈希表以返回与键匹配的对象。在

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万年。我很确定你只是一个线性时间，你有大量的数据。在

将过滤器替换为itertools.ifilter，它将避免生成列表。相反，python将一次从列表中拉出一个项，通过三个测试，当且仅当它通过时将其交给您。它可以避免内存需求，而且可能更快。在

除非使用一些索引技术，否则将无法在O（n）时间上改进。但是，索引技术的适用性取决于您在test1/test2/test3函数中执行的操作。如果您需要帮助，请为这些函数演示一个示例。在

正如其他人所指出的，数据库的设计就是为了解决这些问题。你可以让这个更快，只需要糟糕地重新实现数据库已经为你做的事情。在