Как сделать кэширование для каждого узла в дереве посетителя
У меня есть приложение, в котором требуется вычислить различные представления (сетка, вокселизация, функция расстояния со знаком, …) дерева примитивов (конечных узлов), которые объединяются с помощью логических операций (внутренние узлы).
Мой первый подход к этому состоял в том, чтобы написать абстрактный базовый класс с виртуальной функцией получения для каждого из различных представлений и кэшировать промежуточные результаты в соответствующих узлах, если не было изменений в их поддереве (что очистило бы их кэш).
Однако я был недоволен уродливой связью древовидной структуры с каждым из разных представлений. Чтобы облегчить это, я удалил абстрактные базовые классы и вместо этого настроил посетителя для каждого из представлений.
Это аккуратно отделило дерево от представлений, но оставило мне проблему с тем, что мне теперь нужно кэшировать промежуточные результаты где-то еще, и именно здесь начинается моя проблема.
TL; DR
Как мне кэшировать (произвольно много разных типов) промежуточные значения во внутренних узлах дерева, не делая дерево зависимым от типа значения?
Мои подходы
Требования предлагают два варианта:
- хранить данные в дереве, но с типом стирания
- хранить данные вне дерева и как-то «подключать» их к узлу
Первый оставляет меня озадаченным некоторой проблемой эффективности: я мог бы легко добавить контейнер boost::any (или что-то эквивалентное) в узлах, но тогда каждому посетителю придется искать во всем контейнере свои собственные данные.
Разделение во втором вводит проблему поддержания актуальности кэша в текущем дереве. Если в дереве есть изменения (удаления, изменения узлов), кэшированные значения должны быть по меньшей мере недействительными. Моя интуиция состояла в том, чтобы использовать некоторую хэш-функцию и unordered_map но я также столкнулся с некоторыми проблемами:
- Я не могу использовать сами триоды в качестве ключа, поэтому мне нужно представить другой класс, который просто ссылается на узлы дерева и представляет их в дереве
- ссылаясь на значения из
unordered_mapключи требует стереть все записи, ссылки на которые удалены, или у нас есть свисающая ссылка (/ указатель) вunordered_mapкоторый может быть вызван на перефразировке - изменения в дереве потребуют реконструкции
unordered_mapпотому что ключи могли измениться
Я пропускаю какое-то очевидное решение этого?
Какой подход вы бы предпочли (и почему)?
Решение
Однажды у меня была похожая проблема, и мое решение было следующим:
- Пусть каждый узел имеет уникальный идентификатор.
- Пусть каждый узел имеет номер версии. Модификации, которые делают недействительными вычисленные значения для узла, просто увеличивают номер версии.
- Пусть у каждого посетителя есть карта кэширования, где пара идентификаторов — это ключ, сопоставленный с парой версия / значение.
- Когда (пере) ходите по дереву, ищите запись узла на карте. Если версия верна, используйте кэшированное значение. Если оно устарело, рассчитайте новое значение и замените старую пару версия / значение.
Сначала я использовал адрес узла в качестве идентификатора, но по причинам памяти мне пришлось повторно использовать поддеревья и выбрать путь к узлу в качестве идентификатора. Преимущество такого пути состоит в том, что он может быть рассчитан каждым посетителем и не должен храниться в узле. В моем случае каждый узел может иметь не более двух дочерних элементов, поэтому путь — это просто набор левых / правых решений, которые могут быть сохранены в виде простого беззнакового целого с некоторым сдвигом битов (мои деревья никогда не достигали глубины 32). 32-битное без знака было более чем достаточно в качестве ключа).
Другие решения