Простой обход дерева и быстрый доступ к случайным узлам

Question

Отредактировано после замечания Алекса Таггарта ниже.

Я использую молнию, чтобы легко перемещаться и редактировать дерево, которое может вырасти до многих тысяч узлов.Каждый узел является неполным, когда он впервые создан.Данные будут все время добавляться / удаляться в случайных позициях, конечные узлы будут заменяться ветвями и т. Д.

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

Реализация будет состоять в том, чтобы обходить дерево с помощью молнии и создавать хэш-таблицу узлов, проиндексированных по ключу.Излишне говорить, что вышесказанное было бы очень неэффективно, поскольку:

• 2 копии каждого узла необходимо создать
• любые изменения должны последовательно отражаться между 2 структурами данных (дерево иhashmap).

Короче говоря, существует ли эффективный во времени / пространстве способ сочетания простоты перемещения / обновления с помощью молнии и быстрого доступа к хеш-таблице в clojure?

Answer 1

Структуры данных Clojure являются постоянными и используют структурное совместное использование . Это означает, что такие операции, как добавление, удаление или накопление, не так неэффективны, как вы описали. Стоимость памяти будет минимальной, поскольку вы не дублируете то, что уже есть.

По умолчанию структуры данных Clojure являются неизменными. Таким образом, узлы в вашей древовидной структуре не будут обновляться, если вы не используете какой-либо ссылочный тип (например, Var). Я не знаю достаточно о вашем конкретном случае использования, чтобы посоветовать лучший способ доступа к узлам. Одним из способов доступа к узлам во вложенной структуре является функция get-in , в которой вы указываете путь к узлу для возврата его значения.

Надеюсь, это поможет решить вашу проблему.