Операции с самыми быстрыми сетами на Западе

Question

Мне не удалось найти удовлетворительного освещения этой темы в одном месте, поэтому мне было интересно: Каковы наиболее быстрые алгоритмы пересечения, объединения и разъединения?
Есть ли интересные с ограниченными доменами?
Может ли кто-нибудь победить O (Z), где Z - фактический размер пересечения?

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

Некоторые известные мне алгоритмы основаны на побитовых операциях, выходящих за рамки простого, поэтому вы можете предполагать наличие SSE4 и доступ к внутренним компонентам, таким как popcount. Обратите внимание на это предположение.

Интересы: Реализация пересечения B-Y

Обновление
У нас есть несколько действительно хороших частичных ответов, но я все еще надеюсь на несколько более полных атак на проблему. Мне особенно интересно увидеть более четко сформулированное использование фильтров Блума для решения проблемы.

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

Answer 1

Если вы хотите рассмотреть структуры, подобные множеству, тогда фильтры Блума имеют тривиальные операции объединения и пересечения.

Answer 2

Для достаточно плотных наборов интервальные списки могут опережать O (n) для указанных вами операций, где n - количество элементов в наборе.

Список интервалов по сути является строго возрастающим списком чисел, [a1, b1, a2, b2, ..., an, bn], где каждая пара ai, bi обозначает интервал [ai, bi).Строго возрастающее ограничение гарантирует, что каждое описываемое множество имеет уникальное представление.Представление набора в виде упорядоченной коллекции интервалов позволяет вашим операциям над множеством обрабатывать несколько последовательных элементов на каждой итерации.

Answer 3

В следующей статье представлены алгоритмы объединения, пересечения и разности в упорядоченных множествах, которые бьют O (Z), если пересечение больше разности (Z> n / 2):

Конфликтующие постоянные наборы и карты

Answer 4

Если набор на самом деле является хэшированным набором, и оба набора имеют одинаковую хэш-функцию и размер таблицы, то мы можем пропустить все сегменты, которые существуют только в одном наборе.Это может немного сузить поиск.

Answer 5

нет оптимального решения, чем O (Z), потому что, если вы думаете о проблеме логически, каждый из алгоритмов пересечения, объединения и разъединения должен по крайней мере прочитать все входные элементы один раз, поэтому чтение Z является обязательным.Кроме того, так как набор не отсортирован по умолчанию, никакие дальнейшие оптимизации не смогут превзойти O (Z)

Answer 6

Абстрактно, набор является чем-то, что поддерживает операцию, "является ли X членом?".Вы можете определить эту операцию на пересечении A n B с точки зрения ее на A и B.Реализация будет выглядеть примерно так:

interface Set { bool isMember(Object X); };

class Intersection {
    Set a, b;
    public Intersection(Set A, Set B) { this.a = A; this.b = B; }

    public isMember(Object X) {
        return a.isMember(X) and b.isMember(Y);
    }
}

A и B могут быть реализованы с использованием явного типа набора, такого как HashSet.Стоимость этой операции для каждой из них довольно дешевая, давайте приблизим ее с помощью O (1);поэтому стоимость на пересечении всего 2 O ( n ).; -)

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