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

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 содержится в пунктах 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_contained с допустимым набором элементов.

т.е. Вы храните элементы, содержащие следующее:

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, и положительны в противном случае.Затем, чтобы взять пересечение двух векторов, вы умножаете термины, а чтобы взять объединение, вы добавляете термины.