Эффективная структура данных объектов в 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)]

Обновление :

Для того, чтобы это стоило, вышеупомянутое намного быстрее, чем numpy решение для поиска:

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

Answer 2

senderle прав (я проголосовал), но я хочу уточнить (и больше, чем просто в комментарии).

Поиск в словаре O (1) и действительно быстрый (в основном ваш ключ превращается вхеш, который обращается к конкретному месту в памяти, чтобы немедленно получить ваши данные).

В отличие от этого, поиск значения путем поиска в массиве медленен, по крайней мере, O (N), поэтому для больших массивов потребуется больше времени, чтобы найти правильное значение.(Например, вы должны просеять все N ключей, найти правильный и затем вернуть кортеж.)

Так что, если ваши ключи уникальны, как вы говорите, имеет смысл просто создать большой словарьон индексируется на основе каждого ключа, который вы можете использовать для поиска.Конечно, вам придется представлять каждый кортеж из m элементов (m = 3 в вашем случае), m раз в словаре, в то время как с одним массивом его нужно было представить только один раз в массиве.

Таким образом, выхотите определить класс Collection

class Collection(object):
    def __init__(self, collection):
        self.collection_dict = dict()
        for tup in collection:
            for i, v in enumerate(tup):
                self.collection_dict[(i, v)] = tup
    def lookup_by_first_element(self, e):
        return self.collection_dict.get((0, e), None)
    def lookup_by_second_element(self, e):
        return self.collection_dict.get((1, e), None)
    def lookup_by_third_element(self, e):
        return self.collection_dict.get((2, e), None)


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

Внутренний c.collection_dict:

{(0, 1): (1, 200, 9),
 (0, 2): (2, 300, 8),
 (0, 3): (3, 400, 7),
 (1, 200): (1, 200, 9),
 (1, 300): (2, 300, 8),
 (1, 400): (3, 400, 7),
 (2, 7): (3, 400, 7),
 (2, 8): (2, 300, 8),
 (2, 9): (1, 200, 9)}

И ваши поиски работают так, как вы просили

>>> c.lookup_by_first_element(1) == (1, 200, 9)
True
>>> c.lookup_by_second_element(300) == (2, 300, 8)
True
>>> c.lookup_by_third_element(250) is None
True

Answer 3

Используя numpy:

>>> import numpy as np
>>> collection = [(1, 200, 9),
...               (2, 300, 8),
...               (3, 400, 7)]
>>> collection = np.array(collection)
>>> def f(d, c, v):
...     # d: collection, c: column, v: value
...     if np.any(d[:, c]==v): return d[d[:, c]==v]
...     return 'None'
...
>>> f(collection, 0, 1)
array([[  1, 200,   9]])
>>> f(collection, 1, 300)
array([[  2, 300,   8]])
>>> f(collection, 2, 250)
'None'