поиск индексов общих подмассивов

Question

У меня есть 2 больших несортированных массива (структурированный набор координат xyz), и я пытаюсь найти позиции всех идентичных подмассивов (общие точки, состоящие из 3 координат). Пример:

a = array([[0, 1, 2], [3, 4, 5]])
b = array([[3, 4, 5], [6, 7, 8]])

Здесь правильный подмассив будет [3, 4, 5], но возможно более одного идентичного подмассива. Правильные индексы будут [0,1] для a и [1,0] для b.

Я уже реализовал чистый метод python, перебирая все точки одного массива и сравнивая их с каждой точкой другого массива, но это очень медленно.

У меня вопрос: есть ли эффективный способ найти индексы для обоих массивов (желательно в numpy, потому что мне нужны массивы для дальнейших вычислений)? Может быть, подход "скользящее окно"?

Answer 1

Общее решение для итераций Python (не относится к numpy или массивам), которое работает за линейное среднее время (O (n + m), n - это число подмассивов, а m - количество уникальных подмассивов):

a = [[0, 1, 2], [3, 4, 5]]
b = [[3, 4, 5], [6, 7, 8]]

from collections import defaultdict

indexmap = defaultdict(list)

for row, sublist in enumerate((a, b)):
    for column, item in enumerate(sublist):
        indexmap[tuple(item)].append((row, column))

repeats = dict((key, value) for key, value in indexmap.iteritems() if len(value) > 1)

Придает

{(3, 4, 5): [(0, 1), (1, 0)]}

Если вам не нужны двухрядные индексы (индекс в списке и в сохраненном индексе), вы можете упростить цикл до

for row in (a, b):
    for column, item in enumerate(sublist):
        indexmap[tuple(item)].append(column)

, поскольку a будет обработано до b, любые дубликаты будут автоматически пронумерованы по строкам:

{(3, 4, 5): [1, 0]}

С repeats[key][rownum], возвращающим индекс столбца для этой строки.

Answer 2

Я немного поэкспериментировал и нашел конкретный способ решить эту проблему:

import numpy as np

a = np.arange(24).reshape(2,4,3)
b = np.arange(24, 36).reshape(2,2,3)

Массив b получает 2 записи из:

b[1,0] = a[0,1]
b[0,1] = a[1,1]

Поиск общих записей:

c = np.in1d(a, b).reshape(a.shape)
d = np.in1d(b, a).reshape(b.shape)

Проверка наличия общих записей во всех 3 координатах:

indexesC = np.where(c[:,:,0] & c[:,:,1] & c[:,:,2])
indexesD = np.where(d[:,:,0] & d[:,:,1] & d[:,:,2])

Answer 3

Можете ли вы отобразить каждый вложенный массив на его индекс позиции в хеш-таблице?В общем, вы меняете структуру данных.После этого за линейное время O (n), где n - размер самой большой хеш-таблицы, в одном цикле вы можете O (1) запросить каждую хеш-таблицу и выяснить, есть ли у вас один и тот же подмассив в двух или болеехеш-таблицы.