Алгоритм Disjoint Set для больших наборов данных
В настоящее время я работаю над проблемой, которая включает создание непересекающихся наборов из большого набора данных размером 165 ГБ. В настоящее время используется алгоритм объединения по рангам. Однако размер набора данных не позволяет содержать сразу все данные в памяти (часть данных находится в базе данных, а другая часть обрабатывается в памяти).
Но проблема в том, что поиск существования элемента в уже созданных наборах занимает много времени (это занимает время O (n2)).
Цените, если кто-нибудь может предоставить решение вышеуказанной проблемы
@Thomas да, эта проблема действительно проста, когда дело касается небольших наборов данных. но в моем случае он слишком велик, поэтому его часть находится вне памяти. Предположим, что в настоящее время алгоритм создал 100000 наборов (некоторые из этих наборов могут отсутствовать в памяти), и теперь он имеет элемент 5. В этом случае необходимо выполнить поиск 5 в каждом наборе, чтобы определить, существует ли он уже. Это то, что мне нужно оптимизировать.
непересекающаяся структура данных не определяет, как должны храниться узлы. Вы можете поместить их в базу данных, а не в основную память, и это не должно повлиять на эффективность алгоритма. Так что я действительно не понимаю, откуда взялось O (n²).
Вы просто пытаетесь найти связанные компоненты или важно иметь онлайн-использование структуры данных несвязанного набора?
Ответы 1
Есть много способов разделить это на кусочки.
Я предлагаю за один проход присвоить возрастающий индекс каждому элементу большого набора данных. Затем создайте битовый вектор нужного размера, чтобы указать «в объединении всех назначенных в данный момент наборов». Этот битовый вектор должен быть достаточно маленьким, чтобы поместиться в памяти.
Вам нужно будет более подробно объяснить, как выглядит ваша проблема. Я могу очень легко и быстро разбить
{1, 2, 3, ...}на непересекающиеся наборы{{1}, {2}, {3}, ...}, так что я полагаю, что вы не это имели в виду.