Самые быстрые операции на западе

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

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

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

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

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

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

Ответ 1

Если вы захотите рассмотреть подобные структуры, bloom filters имеют тривиальные операции объединения и пересечения.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Сдерживающие стойки и карты

Ответ 5

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

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