Что такое структура данных для быстрого поиска непустых пересечений списка множеств?

Question

У меня есть набор из N элементов, которые являются наборами целых чисел, предположим, что он заказан и называет его I[1..N]. Учитывая набор candidate, мне нужно найти подмножество I, у которых есть непустые перекрестки с candidate.

Так, например, если:

I = [{1,2}, {2,3}, {4,5}] 

Я ищу, чтобы определить valid_items(items, candidate), такие, что:

valid_items(I, {1}) == {1} 
valid_items(I, {2}) == {1, 2} 
valid_items(I, {3,4}) == {2, 3} 

Я пытаюсь оптимизировать для одного заданного множества I и переменную candidate наборы. В настоящее время я делаю это путем кэширования items_containing[n] = {the sets which contain n}. В приведенном выше примере, который был бы:

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}] 

То есть, 0, содержится в каких-либо предметов, 1 содержится в пункте 1, 2 содержится в Itmes 1 и 2, 2 содержится в пункте 2, 3 содержится в пункте 2, а 4 и 5 содержатся в пункте 3.

Таким образом, я могу определить valid_items(I, candidate) = union(items_containing[n] for n in candidate).

Есть ли более эффективная структура данных (разумного размера) для кэширования результата этого объединения? Очевидный пример пространства 2^N неприемлем, но N или N*log(N) будет.

Answer 1

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

т.е. хранить items_containing как это:

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100] 

и ваши valid_items могут использовать побитовое ИЛИ слиться, как это:

int valid_items(Set I, Set candidate) { 
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing 
    int valid = 0x0000; 
    for (int item : candidate) { 
     // bit-wise OR 
     valid |= items_containing[item]; 
    } 
    return valid; 
} 

, но они на самом деле не изменить Big-O представление.

Answer 2

Одним из представлений, которые могут помочь, является сохранение наборов I в виде векторов V размера n, чьи записи V (i) равны 0, когда i не находится в V, а положительное в противном случае. Затем, чтобы взять пересечение двух векторов, вы умножаете термины, и, чтобы принять союз, вы добавляете термины.