Я работаю над двумя большими наборами данных, и мой вопрос заключается в следующем.
Предположим, у меня есть два списка:
list1 = [A,B,C,D]
list2 = [B,D,A,G]
Как я могу эффективно найти соответствующий индекс, используя Python, кроме O (n 2) поиска? Результат должен выглядеть так:
matching_index(list1,list2) → [(0,2),(1,0),(3,1)]
Если ваши объекты хешируются, а ваши списки не имеют дубликатов, вы можете создать инвертированный индекс первого списка, а затем пройти второй список. Это перемещает каждый список только один раз и, следовательно, O(n).
def find_matching_index(list1, list2):
inverse_index = { element: index for index, element in enumerate(list1) }
return [(index, inverse_index[element])
for index, element in enumerate(list2) if element in inverse_index]
find_matching_index([1,2,3], [3,2,1]) # [(0, 2), (1, 1), (2, 0)]
Вы можете расширить предыдущее решение на учетную запись для дубликатов. Вы можете отслеживать несколько индексов с помощью set.
def find_matching_index(list1, list2):
# Create an inverse index which keys are now sets
inverse_index = {}
for index, element in enumerate(list1):
if element not in inverse_index:
inverse_index[element] = {index}
else:
inverse_index[element].add(index)
# Traverse the second list
matching_index = []
for index, element in enumerate(list2):
# We have to create one pair by element in the set of the inverse index
if element in inverse_index:
matching_index.extend([(x, index) for x in inverse_index[element]])
return matching_index
find_matching_index([1, 1, 2], [2, 2, 1]) # [(2, 0), (2, 1), (0, 2), (1, 2)]
К сожалению, это уже не O (n). Рассмотрим случай, когда вы вводите [1, 1] и [1, 1], выход - [(0, 0), (0, 1), (1, 0), (1, 1)]. Таким образом, по размеру выхода наихудший случай не может быть лучше O(n^2).
Хотя это решение все еще O(n) если нет дубликатов.
Теперь идет случай, когда ваши объекты не хешируются, но сопоставимы. Идея здесь заключается в сортировке ваших списков таким образом, чтобы сохранить индекс начала каждого элемента. Затем мы можем группировать последовательности элементов, которые равны для получения совпадающих индексов.
Поскольку мы используем groupby и product в следующем коде, я заставил find_matching_index вернуть генератор для эффективности памяти в длинных списках.
from itertools import groupby, product
def find_matching_index(list1, list2):
sorted_list1 = sorted((element, index) for index, element in enumerate(list1))
sorted_list2 = sorted((element, index) for index, element in enumerate(list2))
list1_groups = groupby(sorted_list1, key=lambda pair: pair[0])
list2_groups = groupby(sorted_list2, key=lambda pair: pair[0])
for element1, group1 in list1_groups:
try:
element2, group2 = next(list2_groups)
while element1 > element2:
(element2, _), group2 = next(list2_groups)
except StopIteration:
break
if element2 > element1:
continue
indices_product = product((i for _, i in group1), (i for _, i in group2), repeat=1)
yield from indices_product
# In version prior to 3.3, the above line must be
# for x in indices_product:
# yield x
list1 = [[], [1, 2], []]
list2 = [[1, 2], []]
list(find_matching_index(list1, list2)) # [(0, 1), (2, 1), (1, 0)]
Оказывается, сложность времени не так сильно страдает. Сортировка курса занимает O(n log(n)), но затем groupby предоставляет генераторы, которые могут восстанавливать все элементы, перемещая наши списки только дважды. Вывод состоит в том, что наша сложность в первую очередь связана с размером выпуска product. Таким образом, наилучший случай, когда алгоритм O(n log(n)) и худший случай, который снова O(n^2).
Если ваши объекты не являются хешируемыми, но все же упорядочиваемыми, вы можете захотеть использовать sorted для соответствия обоим спискам
Вы можете сортировать индексы списков и сопоставлять результаты
indexes1 = sorted(range(len(list1)), key=lambda x: list1[x])
indexes2 = sorted(range(len(list2)), key=lambda x: list2[x])
matches = zip(indexes1, indexes2)
Вы можете сортировать оба одновременно и сохранять индексы во время сортировки. Затем, если вы поймаете какие-либо последовательные дубликаты, вы знаете, что они из разных списков
biglist = list(enumerate(list1)) + list(enumerate(list2))
biglist.sort(key=lambda x: x[1])
matches = [(biglist[i][0], biglist[i + 1][0]) for i in range(len(biglist) - 1) if biglist[i][1] == biglist[i + 1][1]]
Один грубый ответ на эту проблему, если только по какой-либо другой причине, кроме как для подтверждения какого-либо решения, предоставляется:
[(xi, xp) for (xi, x) in enumerate(list1) for (xp, y) in enumerate(list2) if x==y]
Как вам придется оптимизировать это, во многом зависит от объемов данных и объема памяти, поэтому может быть полезно некоторое представление о том, насколько велики эти списки. Я бы предположил, что метод, который я обсуждаю ниже, будет полезен для списков с миллионами значений, по крайней мере.
Поскольку доступ к словарю равен O (1), казалось бы, стоит попытаться сопоставить элементы во втором списке с их позициями. Предполагая, что один и тот же элемент можно повторить, collections.defaultdict легко позволит нам построить необходимый dict.
l2_pos = defaultdict(list)
for (p, k) in enumerate(list2):
l2_pos[k].append(p)
Выражение l2_pos[k] теперь является списком позиций в list2 в котором происходит элемент k. Остается только соединить каждый из них с позициями соответствующих клавиш в list1. Результат в форме списка
[(p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k]]
Однако, если эти структуры велики, вам может быть лучше подано выражение генератора. Чтобы связать имя с выражением внутри понимания списка выше, вы должны написать
values = ((p1, p2) for (p1, k) in enumerate(list1) for p2 in l2_pos[k])
Если вы затем перебираете values вы избегаете накладных расходов на создание списка, содержащего все значения, тем самым уменьшая нагрузку на управление памятью Python и сборку мусора, что в значительной степени связано с большими проблемами при решении вашей проблемы.
Когда вы начинаете разбираться с большими объемами данных, понимание генераторов может означать разницу между наличием достаточного объема памяти для решения вашей проблемы или нет. Во многих случаях они имеют явное преимущество перед пониманием списков.
EDIT: этот метод может быть дополнительно ускорен с использованием наборов, а не списков, чтобы удерживать позиции, если изменения в упорядочении не будут вредными. Это изменение остается в качестве упражнения для читателя.
Использование dict уменьшает время поиска, и специализация collections.defaultdict может помочь в бухгалтерии. Цель - это dict, значения которого представляют собой пары индексирования, которые вы после. Повторяющиеся значения перезаписывают более ранние из списка.
import collections
# make a test list
list1 = list('ABCDEFGHIJKLMNOP')
list2 = list1[len(list1)//2:] + list1[:len(list1)//2]
# Map list items to positions as in: [list1_index, list2_index]
# by creating a defaultdict that fills in items not in list1,
# then adding list1 items and updating with with list2 items.
list_indexer = collections.defaultdict(lambda: [None, None],
((item, [i, None]) for i, item in enumerate(list1)))
for i, val in enumerate(list2):
list_indexer[val][1] = i
print(list(list_indexer.values()))
Вот простой подход с defaultdict.
Дано
import collections as ct
lst1 = list("ABCD")
lst2 = list("BDAG")
lst3 = list("EAB")
str1 = "ABCD"
Код
def find_matching_indices(*iterables, pred=None):
"""Return a list of matched indices across 'm' iterables."""
if pred is None:
pred = lambda x: x[0]
# Dict insertion
dd = ct.defaultdict(list)
for lst in iterables: # O(m)
for i, x in enumerate(lst): # O(n)
dd[x].append(i) # O(1)
# Filter + sort
vals = (x for x in dd.values() if len(x) > 1) # O(n)
return sorted(vals, key=pred) # O(n log n)
демонстрация
Найти совпадения в двух списках (для каждого OP):
find_matching_indices(lst1, lst2)
# [[0, 2], [1, 0], [3, 1]]
Сортировка по другому результату:
find_matching_indices(lst1, lst2, pred=lambda x: x[1])
# [[1, 0], [3, 1], [0, 2]]
Сопоставьте элементы в более чем двух итерациях (необязательно переменной длины):
find_matching_indices(lst1, lst2, lst3, str1)
# [[0, 2, 1, 0], [1, 0, 2, 1], [2, 2], [3, 1, 3]]
подробности
Вставка словаря
Каждый элемент добавляется к спискам defaultdict. Результат выглядит примерно так, что позже фильтруется:
defaultdict(list, {'A': [0, 2], 'B': [1, 0], 'C': [2], 'D': [3, 1], 'G': [3]})
На первый взгляд, с двойной for петель может возникнуть соблазн сказать время сложность O (n²). Однако список контейнеров во внешнем цикле имеет длину m. Внутренняя петля обрабатывает элементы каждого контейнера длиной n. Я не уверен, что такое окончательная сложность, но на основании этого ответа я подозреваю, что это O (n * m) или, по крайней мере, ниже O (n²).
фильтрация
Non-matches (списки длины 1) отфильтровываются, и результаты сортируются (в основном для неупорядоченных dicts в Python <3.6).
Используя алгоритм timsort с помощью sorted для сортировки значений (списков) по некоторым индексам, худшим случаем является O (n log n). Поскольку вставка ключа ключа сохраняется в Python 3. 6+, предварительно отсортированные элементы уменьшают сложность O (n).
В целом, наилучшая временная сложность - O (n); худшим случаем является O (n log n), если использовать sorted в Python <3.6, в противном случае O (n * m).