Эффективный алгоритм согласования для тройок на основе множеств

Question

Я ищу эффективный способ решения следующей проблемы.

Список 1 представляет собой список записей, которые идентифицируются примитивной триплетом:

X | Y | Z

Список 2 - это список записей, которые идентифицируются тремя наборами. Один X, один Ys, один Zs. X, Y, Z имеют тот же тип, что и в первом списке, поэтому они напрямую сопоставимы друг с другом.

Set(X) | Set(Y) | Set(Z)

Для элемента в списке 1 мне нужно найти все элементы в списке 2, где все X, Y, Z из списка 1 встречаются в соответствующих наборах в списке 2. Это лучше всего демонстрируется на примере:

Список 1:

X1, Y1, Z1

Список 2:

(X1, X2) | (Y1) | (Z1, Z3)

(X1) | (Y1, Y2) | (Z1, Z2, Z3)

(X3) | (Y1, Y3) | (Z2, Z3)

Как указано выше, элемент в списке 1 будет соответствовать первым двум элементам в списке 2. Третий элемент не будет сопоставлен, поскольку X1 не встречается в наборе X, а Z1 не встречается в наборе Z.

Я написал функционально правильную версию алгоритма, но обеспокоен производительностью больших наборов данных. Оба списка очень большие, поэтому итерация по списку 1 и последующая итерация по списку 2 для каждого элемента будет очень неэффективной.

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

Может кто-нибудь предложить мне оптимальный способ решения этой проблемы. Я рад рассмотреть оптимальные решения как для памяти, так и для процессора, но было бы неплохо найти баланс!

Answer 1

Будет много способов приблизиться к этому. Что правильно, зависит от данных и от того, сколько памяти доступно.

Один простой способ - создать таблицу из списка list2 для ускорения запросов, поступающих из списка 1.

from collections import defaultdict

# Build "hits".  hits[0] is a table of, for each x,
# which items in list2 contain it. Likewise hits[1]
# is for y and hits[2] is for z.
hits = [defaultdict(set) for i in range(3)]
for rowid, row in enumerate(list2):
    for i in range(3):
        for v in row[i]:
            hits[i][v].add(rowid)

# For each row, query the database to find which
# items in list2 contain all three values.
for x, y, z in list1:
    print hits[0][x].intersection(hits[1][y], hits[2][z])

Answer 2

Есть довольно эффективный способ сделать это с однократным проходом по списку2 . Вы начинаете с создания индекса предметов в списке 1.

from collections import defaultdict

# index is HashMap<X, HashMap<Y, HashMap<Z, Integer>>>
index = defaultdict(lambda: defaultdict(dict))
for rowid, (x, y, z) in enumerate(list1):
    index[x][y][z] = rowid

for rowid2, (xs, ys, zs) in enumerate(list2):
    xhits = defaultdict(list)
    for x in xs:
        if x in index:
            for y, zmap in index[x].iteritems():
                xhits[y].append(zmap)

    yhits = defaultdict(list)
    for y in ys:
        if y in xhits:
            for z, rowid1 in xhits[y].iteritems():
                yhits[z].append(rowid1)

    for z in zs:
        if z in yhits:
            for rowid1 in yhits[z]:
                print "list1[%d] matches list2[%d]" % (hit[z], rowid2)

Дополнительная бухгалтерия здесь , вероятно, сделает ее медленнее, чем индексирование списка2. Но так как в вашем случае list1 обычно намного меньше, чем list2, это будет использовать гораздо меньше памяти. Если вы читаете list2 с диска, с этим алгоритмом вам никогда не нужно хранить какую-либо его часть в памяти.

Доступ к памяти может иметь большое значение, поэтому я не могу точно сказать, что будет быстрее на практике. Приходится измерять. Наихудшая временная сложность в обоих случаях, за исключением сбоев хеш-таблицы, составляет O (len (list1) * len (list2)).

Answer 3

Вы можете построить дерево из List2; первый уровень дерева - это первый из (X1..Xn), который появляется в множестве X. Второй уровень - это значения для второго элемента плюс листовой узел, содержащий набор списков, которые содержат только X1. Следующий уровень содержит следующее возможное значение и т. Д.

Root --+--X1--+--EOF--> List of pointers to list2 lines containing only "X1"
       |      |
       |      +--X2---+--EOF--> List of pointers to list2 lines containing only "X1,X2"
       |      |       |
       |      |       +--X3--+--etc--
       |      |       
       |      +--X3---+--EOF--> "X1,X3"
       |             
       +--X2--+--EOF--> "X2"
       |      |
       |      +--X3---+--EOF--> "X2,X3"
       |      |       |
       ...

Это дорого потребляет память (N ^ 2 log K, я думаю? Где N = значения для X, K = строки в List2), но приводит к быстрому поиску. Если число возможных X большое, тогда этот подход потерпит неудачу ...

Очевидно, что вы можете построить этот индекс для всех 3 частей кортежа, а затем И вместе с результатами поиска по каждому дереву.

Answer 4

Если общий размер Наборов не слишком велик, вы можете попытаться смоделировать Список 2 как битовые поля.Хотя структура, вероятно, будет довольно фрагментированной - возможно, структуры, на которые ссылаются в статье Википедии Битовые массивы (массивы Джуди, попытки, фильтр Блума), могут помочь решить проблемы с памятью, связанные с подходом нормализации.

Answer 5

Если вы используете Гуава , существует высокоуровневый способ сделать это, который не обязательно оптимальный , но не делает ничего сумасшедшего:

List<SomeType> list1 = ...;
List<Set<SomeType>> candidateFromList2 = ...;
if (Sets.cartesianProduct(candidateFromList2).contains(list1)) { ... }

Но не так сложно проверить и эту "длинную строчку".

Answer 6

Как насчет использования HashSet (или HashSet с) для Список 2 ? Таким образом, вам нужно будет только перебрать Список 1