Быстрого членства в срезах списков

Question

У меня есть очень большой список под названием «данные», и я должен отвечать на запросы, эквивалентные

if (x in data[a:b]): 

для различных значений а, Ь, х.

Можно ли предварительные обработка данных, чтобы сделать эти запросы быстро

Answer 1

идее

вы можете создать dict. Для каждого элемента хранится отсортированный список позиций, где он встречается.

Чтобы ответить на запрос: бинарный поиск первый элемент, который больше или равен a, проверьте, если он существует, и меньше, чем b

ПСЕВДОКОД

Preprocessing:

from collections import defaultdict 

byvalue = defaultdict(list) 

for i, x in enumerate(data): 
    byvalue[x].append(i) 

Запрос:

def has_index_in_slice(indices, a, b): 
    r = bisect.bisect_left(indices, a) 

    return r < len(indices) and indices[r] < b 

def check(byvalue, x, a, b): 
    indices = byvalue.get(x, None) 
    if not indices: return False 

    return has_index_in_slice(indices, a, b) 

Сложность O(log N) за запрос здесь, если мы предположим, что list и dict имеют сложность «получить по индексу» O (1).

Answer 2

Да, вы могли бы эти ломтики предварительную обработку в наборы, тем самым делая членство поиск O(1) вместо O(n):

check = set(data[a:b]) 
if x in check: 
    # do something 
if y in check: 
    # do something else 

Answer 3

Поместите список в базу данных и воспользоваться встроенными в индексации, оптимизации и кэширования. Например, из руководства PostgreSQL:

После того, как индекс создан, не требуется никакого вмешательства: система будет обновлять индекс, если таблица изменяется, и он будет использовать индекс в запросах, когда он думает, что это будет больше , чем сканирование последовательной таблицы.

Но вы также можете использовать sqlite для простоты (и доступности в стандартной библиотеке Python). От Python's documentation, regarding indexing:

экземпляр подряд служит высоко оптимизированной row_factory для подключения объектов. Он пытается имитировать кортеж в большинстве своих функций.

Он поддерживает сопоставление доступа по имени столбца и индексу, итерации, представлению, проверке равенства и len().

И в другом месте на этой странице:

Row обеспечивает как индекс на основе и без учета регистра доступа, основанных на имена столбцы практически без накладных расходов памяти. Вероятно, это будет лучше , чем ваш собственный подход на основе словаря или даже решение на основе db_row .