Ответ 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).

Ответ 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]]

Ответ 3

Один грубый ответ на эту проблему, если только по какой-либо другой причине, кроме как для подтверждения какого-либо решения, предоставляется:

[(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: этот метод может быть дополнительно ускорен с использованием наборов, а не списков, чтобы удерживать позиции, если изменения в упорядочении не будут вредными. Это изменение остается в качестве упражнения для читателя.

Ответ 4

Использование 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()))

Ответ 5

Вот простой подход с 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).