LINUX.ORG.RU

Пересечение множеств


0

0

Привет!

Предположим, что есть два множества.
A : |A| = n
B : |B| = m

Элементы данных множеств - целые положительные числа.
Задача заключается в нахождении пересечения данных множеств.

Очевидный подход - реализовать множества как списки, поддерживать 
их отсортированными и искать пересечение одним проходом по обоим
спискам.

Получаем алгоритм со сложностью O(n+m).

Можно ли найти пересечение быстрее?

Спасибо!

Re: Пересечение множеств

> Можно ли найти пересечение быстрее?

Поддерживать список с пересечением? При изменении множеств делать актуализацию.

mv ★★★★★ ()

Re: Пересечение множеств

сперва ты должен четко понять какой диапазон у чисел, какие операции и как часто будут проводиться с множествами.

dilmah ★★★★★ ()
Ответ на: Re: Пересечение множеств от dilmah

Re: Пересечение множеств

+1

Эту задачу нельзя рассматривать в отрыве от того, как эти множества будут создаваться и использоваться. Решений может быть множество :) Сама же по себе задача в сформулированном виде имеет лишь академический интерес.

Хранение чисел отсортированными является хорошей идеей, но здесь не будет общих решений, пока задача не конкретизирована и не определены более четко use cases.

dave ★★★★★ ()

Re: Пересечение множеств

Видимо, dilmah имел ввиду использование битовых масок для представления множеств. Так реализованы множества в Pascal/Ada/Modula etc. Это было бы действительно самым быстрым способом, но там есть жесткое ограничение на диапазон чисел (точнее на мощность их диапазона).

dave ★★★★★ ()

Re: Пересечение множеств

Если вариант с битовыми масками не подойдёт, лучше использовать дерево, храня в каждом узле, помимо значения, 2 бита. 0-й устанавливать, если число пришло из первого множества, 1-й устанавливать, если число пришло из второго множества. Тогда пересечение, в отсортированном виде, находится обходом в глубину.

А вариант со списками, это O(n^2) + O(m^2) в худшем случае.

Legioner ★★★★★ ()

Re: Пересечение множеств

Согласен с предыдущими ораторами -- телепаты нынче в отпуске :-)

Решений масса -- битовые маски, деревья (двоичные, B, префиксные), хэши; их комбинации...

Die-Hard ★★★★★ ()

Re: Пересечение множеств

Для произвольных множеств - думаю невозможно быстрее чем за m+n. Собственно, для этого тебе надо знать об элементах множеств что-то такое, что даст возможность смотреть не на все элементы. Ибо просто пройтись по ним - m+n

ratatosk ()

Re: Пересечение множеств

Сделать хеш размером max(m,n). Если возникает коллизия, значит что-то уже есть в этом хеше. Значит, возникло пересечение. Итого, вместо O(m+n) получается O(max(m,n))

anonymous ()

Re: Пересечение множеств

A = set((1, 2, 3))
B = set((0, 2, 4, 5))
print A.intersection(B)

rei3er ()
Ответ на: Re: Пересечение множеств от annoynymous

Re: Пересечение множеств

>> Сортировка твоё O(n) убивает напрочь.

Учи матчасть. Все задачи доступа к множеству в виде упорядоченного списка имеют сложность O(n). Твое предложение ничем не лучше чем хранить множество в виде неупорядоченного списка, на пересечении получишь O(n^2) минимум, плюс сложность сортировки.

cathode ()
Ответ на: Re: Пересечение множеств от anonymous

Re: Пересечение множеств

>> Сделать хеш размером max(m,n). Если возникает коллизия, значит что-то уже есть в этом хеше. Значит, возникло пересечение. Итого, вместо O(m+n) получается O(max(m,n))

В упорядоченном списке сложность и так O(max(m,n)), что равно O(m+n) кстати. А вот хештаблица может дать тебе O(1) (опять же смотря как хранить хеши).

cathode ()
Ответ на: Re: Пересечение множеств от Legioner

Re: Пересечение множеств

>> Если вариант с битовыми масками не подойдёт, лучше использовать дерево, храня в каждом узле, помимо значения, 2 бита. 0-й устанавливать, если число пришло из первого множества, 1-й устанавливать, если число пришло из второго множества. Тогда пересечение, в отсортированном виде, находится обходом в глубину.

И что? Сложность O(n), т.к. надо просмотреть все дерево. Та же самая сложность получается при пересечении двух бинарных деревьев (не обязательно даже сбалансированных).

cathode ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.