Эффективная структура данных объектов в python для поиска на основе любой переменной-члена объекта
Мне нужно хранить объекты с числом (> 2) целочисленных переменных-членов и выполнять быстрые поиски с использованием любых переменных-членов в качестве ключа поиска.
Для более простой иллюстрации предположим, что объекты представляют собой кортежи из 3 целых чисел, и мне нужно делать быстрые поисковые запросы, используя любой элемент кортежа в качестве ключа в списке таких наборов:
- Как Python хранит списки внутри?
- Лучшая структура данных для трехмерных данных?
- Закрепление неравных списков в python в список, который не отбрасывает ни один элемент из более длинного списка,
- Создание дерева / глубоко вложенного dict со списками из текстового файла с отступом
- Python Индекс структуры данных Начните с 1 вместо 0?
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 в памяти с тремя столбцами для трех элементов кортежа и индексами для всех трех столбцов.
Дерево поиска также будет работать, но у них есть один ключ для поиска, и я не вижу, как я мог выполнять поиск на основе нескольких ключей. Как бы вы это сделали?
3 Solutions collect form web for “Эффективная структура данных объектов в python для поиска на основе любой переменной-члена объекта”
Использование 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'
Это простое решение. Вы можете легко поместить это в класс и обеспечить более чистый интерфейс.
>>> 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
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