У меня есть набор из полумиллиона предметов, хранящихся в базе данных, и мне нужны следующие операции:
union(x, y), как в Union-Find findAll(x) поиск всех y таких, что find(x) == find(y)ununion(x, y) возврат прежней операции объединения
Это практическая проблема, для которой известно следующее
- Обычно разделы будут небольшими (менее 100 элементов), но нет никакой гарантии.
- Скорость работы
union не имеет большого значения. findAll должен быть быстрым и должен быть реализован в SQL (без рекурсии / CONNECT BY). - Иногда мы обнаруживаем, что некоторые
union были действительно неправильными и нужно отменить их,сохраняя все предыдущие и последующие union с.Эта операция достаточно редка, поэтому скорость не имеет значения. - Нет необходимости, чтобы
findAll немедленно видел изменения, сделанные другими операциями.Некоторая постобработка была бы в порядке.
Классический алгоритм Union-Find требует сжатия пути (или варианта) для эффективности и не позволяет удалять ребра (даже без сжатия пути).Мне известно о Динамическое подключение , но оно выглядит неприменимым для моего варианта использования.
Я думаю, мы не можем его использовать, так как скорость findAllсамое важное.Вероятно, нам следует напрямую связать все узлы с корнем.
Что касается ununion, моя единственная идея - хранить все операции union отдельно, а на ununion удалить все ссылки из соответствующего раздела иповторить все связанные union s.
Звучит довольно грубо, как ...
Прежде чем приступить к реализации чего-либо, я спрашиваю, есть ли более умный алгоритм?