python - 基于任意对象成员变量查找的python中对象的高效数据结构

Question

我需要存储具有多个 (>2) 个整数成员变量的对象，并使用任何成员变量作为搜索键进行快速查找。

为了便于说明，假设对象是 3 个整数的元组，我需要使用元组的任何元素作为此类元组列表中的键进行快速查找:

collection = [(1, 200, 9), 
              (2, 300, 8), 
              (3, 400, 7)]

查找就像:

collection.lookup_by_first_element(1) # Return (1, 200, 9)
collection.lookup_by_second_element(300) # Return (2, 300, 8)
collection.lookup_by_third_element(250) # Return None

我需要快速/高效的查找。到目前为止，我最好的选择是使用内存中的 sqlite 数据库，其中包含三个元组元素的三列，并在所有三列上放置索引。

搜索树也可以，但它们只有一个键用于查找，我看不出如何根据多个键进行查找。你会怎么做？

Answer 1

这是一个简单的解决方案。您可以轻松地将其放入类中并提供更整洁的界面。

>>> from collections import defaultdict
>>> collection = [(1, 200, 9),
...               (2, 300, 8),
...               (3, 400, 7)]
>>> keyed_dict = defaultdict(list)
>>> for tup in collection:
...     for i, e in enumerate(tup):
...         keyed_dict[(i, e)].append(tup)
... 
>>> keyed_dict[(1, 300)]
[(2, 300, 8)]

更新:

就其值(value)而言，上面的方法比 numpy solution 快得多查找:

from timeit import timeit

setup_code = '''
import numpy

clen = {0}  # use .format() to fill this value
collection = [(n, (n + 1) * 100, clen - n) for n in xrange(clen)]

npcollection = numpy.array(collection)

def numpy_lookup(collection, column, value):
    if numpy.any(collection[:, column] == value): return collection[collection[:, column] == value]
    return 'None'

keyed_dict = dict()
for tup in collection:
    for i, e in enumerate(tup):
        keyed_dict[i, e] = tup
'''

for e in range(5):
    setup = setup_code.format(str(10 ** e))
    kd_stmt = '[keyed_dict[0, n] for n in range({0})]'.format(str(10 ** e))
    np_stmt = '[numpy_lookup(npcollection, 0, n) for n in range({0})]'.format(str(10 ** e))
    print 'using keyed_dict: ',
    print timeit(stmt=kd_stmt, setup=setup, number=10)
    print 'using numpy_lookup: ',
    print timeit(stmt=np_stmt.format(str(10 ** e)), setup=setup, number=10)

输出:

using keyed_dict:  1.09672546387e-05
using numpy_lookup:  0.000250101089478
using keyed_dict:  3.00407409668e-05
using numpy_lookup:  0.00193691253662
using keyed_dict:  0.000190019607544
using numpy_lookup:  0.0199580192566
using keyed_dict:  0.00195384025574
using numpy_lookup:  0.317503929138
using keyed_dict:  0.0319399833679
using numpy_lookup:  15.0127439499