Какова хорошая структура данных для построения классов эквивалентности на узлах дерева?
Я ищу хорошую структуру данных для построения классов эквивалентности на узлах дерева. В идеальной структуре следующие операции должны быть быстрыми (O(1)/O(n) в зависимости от ситуации) и простыми (без абзацев загадочного кода):
- (A) пройтись по дереву от корня; на каждом узле -> дочерний переход перечисляет все эквивалентные версии дочернего узла
- (B) Объединить два класса эквивалентности
- (C) Создать новые узлы из списка существующих узлов (дочерних) и других данных
- (D) Найти любые узлы, структурно эквивалентные узлу (то есть они имеют одинаковое количество дочерних элементов, соответствующие дочерние элементы принадлежат к одному и тому же классу эквивалентности, и их "другие данные" равны), так что могут быть помещены новые (или недавно модифицированные) узлы в правильном классе эквивалентности (через слияние)
До сих пор я рассмотрел (некоторые из них могут быть использованы в комбинации):
- Parfait, где дочерние элементы являются ссылками на коллекции узлов, а не на узлы. (A) быстро, (B) требует обхода дерева и обновления узлов для указания на объединенную коллекцию, (C) требует поиска коллекции, содержащей каждого дочернего элемента нового узла, (D) требует обхода дерева
- Поддержание хэша узлов по их характеристикам. Это делает (D) намного быстрее, но (B) медленнее (так как хеш должен был бы быть обновлен, когда классы эквивалентности были объединены)
- Объедините узлы в круговой связанный список. (A) быстро, (B) было бы быстро, но для того факта, что "объединение" части кругового списка с самим собой фактически разделяет список (C) было бы быстро, (D) потребовало бы обхода дерева
- Как и выше, но с дополнительным указателем "вверх" в каждом узле, который можно использовать для поиска канонического члена циклического списка.
Я скучаю по сладкой альтернативе?
3 ответа
Похоже, у вас есть две формы эквивалентности. Простая эквивалентность (A), отслеживаемая как классы эквивалентности, которые поддерживаются в актуальном состоянии, и структурная эквивалентность (D), для которой вы иногда создаете один класс эквивалентности, а затем выбрасываете его.
Мне кажется, что проблема была бы концептуально проще, если бы вы поддерживали классы эквивалентности для простой и структурной эквивалентности. Если это вводит слишком много оттока для структурной эквивалентности, вы можете поддерживать классы эквивалентности для некоторых аспектов структурной эквивалентности. Тогда вы могли бы найти баланс, при котором вы можете позволить себе поддерживать эти классы эквивалентности, но при этом значительно сократить количество узлов, которые нужно исследовать при построении списка структурно эквивалентных узлов.
Я не думаю, что какая-то одна структура решит ваши проблемы, но вы могли бы взглянуть на структуру данных с несвязанными множествами. В конце концов, класс эквивалентности - это то же самое, что и разбиение множества. Он должен быть в состоянии справиться с некоторыми из этих операций быстро.
Отступив на мгновение, я бы предложил вообще не использовать дерево. В прошлый раз, когда мне приходилось сталкиваться с подобной проблемой, я начал с дерева, но позже перешел на массив.
Причин было много, но причиной номер один была производительность. Мои классы с количеством детей до 100 или около того, на самом деле лучше работали бы, манипулируя ими как массивом, чем через узлы дерева, в основном из-за аппаратной локализации, логики предварительной выборки ЦП и ЦП. конвейерная.
Таким образом, хотя алгоритмически структура массива требует большего N операций, чем дерева, выполнение этих десятков операций, вероятно, быстрее, чем погоня за указателями в памяти.