Эффективная массовая модификация постоянных структур данных

Question

Я понимаю, как обычно деревья используются для изменения постоянных структур данных (создания нового узла и замены всех его предков).

Но что, если у меня есть дерево из 10 000 узлов, и мне нужноизменить 1000 из них?Я не хочу проходить и создавать тысячи новых корней, мне нужен только один новый корень, который получается в результате изменения всего сразу.

Например: Давайте возьмем, например, постоянное двоичное дерево.В случае одного узла обновления он выполняет поиск до тех пор, пока не найдет узел, не создаст новый с изменениями и старыми дочерними элементами и не создаст новых предков вплоть до корня.

В случае массового обновления можетмы делаем: вместо того, чтобы просто обновить один узел, вы собираетесь обновить 1000 узлов на нем за один проход.

В корневом узле текущий список является полным списком.Затем вы разделяете этот список между теми, которые соответствуют левому узлу, и теми, которые соответствуют правому.Если ни один из них не подходит ни одному из детей, не спускайтесь к нему.Затем вы спускаетесь к левому узлу (при условии совпадения), разделяете его список поиска между его дочерними узлами и продолжаете.Когда у вас есть один узел и совпадение, вы обновляете его и возвращаетесь обратно, заменяя и обновляя предков и другие ветви в зависимости от ситуации.

Это приведет к появлению только одного нового корня, даже если будет изменено любое количество узлов.

Answer 1

Такого рода операции «массовой модификации» иногда называют массовые обновления . Конечно, детали будут зависеть от того, с какой именно структурой данных вы работаете и какие изменения вы пытаетесь выполнить.

Типичные операции могут включать «удаление всех значений, удовлетворяющих некоторому условию» или «увеличение значений, связанных со всеми ключами в этом списке». Часто эти операции могут выполняться за один проход по всей структуре, что занимает время O (n).

Похоже, вы обеспокоены распределением памяти при создании "1000 новых корней". Типичным распределением для выполнения операций по одному будет O (k log n), где k - количество изменяемых узлов. Типичное распределение для выполнения одного обхода по всей структуре будет O (n). Что лучше, зависит от k и n.

В некоторых случаях вы можете уменьшить объем размещения - за счет более сложного кода - обращая особое внимание на то, когда происходят изменения. Например, если у вас есть рекурсивный алгоритм, который возвращает дерево, вы можете изменить алгоритм так, чтобы он возвращал дерево вместе с логическим значением, указывающим, изменилось ли что-нибудь. Затем алгоритм может проверить эти логические значения перед выделением нового узла, чтобы увидеть, можно ли безопасно использовать старый узел повторно. Тем не менее, люди обычно не беспокоятся об этой дополнительной проверке до тех пор, пока у них нет доказательств того, что дополнительное выделение памяти действительно является проблемой.

Answer 2

Конкретную реализацию того, что вы ищете, можно найти в Clojure (и ClojureScript) переходные процессы .

Короче говоря, учитывая полностью неизменяемую, постоянную структуру данных, временная версия этого будет вносить изменения, используя деструктивную (эффективную для распределения) мутацию, которую вы можете снова вернуться к правильной постоянной структуре данных, когда закончите. с вашими чувствительными к производительности операциями. Только при переходе обратно к постоянной структуре данных создаются новые корни (например), таким образом амортизируется сопутствующая стоимость по сравнению с количеством логических операций, которые вы выполнили над структурой, пока она находилась в ее переходной форме.