#data-structures #immutability
#структуры данных #неизменяемость
Вопрос:
Я понимаю, как обычно деревья используются для изменения постоянных структур данных (создания нового узла и замены всех его предков).
Но что, если у меня есть дерево из 10000 узлов, и мне нужно изменить 1000 из них? Я не хочу перебирать и создавать 1000 новых корней, мне нужен только один новый корень, который получается в результате изменения всего сразу.
Например: Давайте возьмем, к примеру, постоянное двоичное дерево. В случае с одним узлом обновления выполняется поиск до тех пор, пока не будет найден узел, создается новый с изменениями и старыми дочерними элементами и создаются новые предки вплоть до корня.
В случае массового обновления мы могли бы сделать: вместо простого обновления одного узла вы собираетесь обновить 1000 узлов на нем за один проход.
На корневом узле текущий список является полным списком. Затем вы разделяете этот список между теми, которые соответствуют левому узлу, и теми, которые соответствуют правому. Если ни один из дочерних элементов не соответствует одному, не переходите к нему. Затем вы переходите к левому узлу (предполагая, что совпадения были), разделяете его список поиска между дочерними элементами и продолжаете. Когда у вас есть единственный узел и совпадение, вы обновляете его и возвращаетесь обратно, заменяя и обновляя предков и другие ветви по мере необходимости.
Это привело бы только к одному новому корню, даже если это изменило любое количество узлов.
Ответ №1:
Такого рода операции «массовой модификации» иногда называются массовыми обновлениями. Конечно, детали будут различаться в зависимости от того, с какой именно структурой данных вы работаете и какие модификации пытаетесь выполнить.
Типичные виды операций могут включать «удалить все значения, удовлетворяющие некоторому условию» или «увеличить значения, связанные со всеми ключами в этом списке». Часто эти операции могут быть выполнены за один проход по всей структуре, что занимает O (n) времени.
Вы, кажется, обеспокоены распределением памяти, связанным с созданием «1000 новых корней». Типичным распределением для выполнения операций по очереди было бы O (k log n), где k — количество изменяемых узлов. Типичным распределением для выполнения одиночного обхода всей структуры было бы O (n). Что лучше, зависит от k и n.
В некоторых случаях вы можете уменьшить объем выделения — за счет более сложного кода — уделяя особое внимание тому, когда происходят изменения. Например, если у вас есть рекурсивный алгоритм, который возвращает дерево, вы можете модифицировать алгоритм, чтобы возвращать дерево вместе с логическим значением, указывающим, изменилось ли что-либо. Затем алгоритм мог бы проверить эти логические значения перед выделением нового узла, чтобы увидеть, можно ли безопасно повторно использовать старый узел. Однако люди обычно не утруждают себя этой дополнительной проверкой до тех пор, пока у них не появятся доказательства того, что выделение дополнительной памяти на самом деле является проблемой.
Комментарии:
1. Спасибо за отличную информацию. Я не рассматривал возможность обхода всей структуры. Я добавил пример в вопрос. Мне кажется, что этот пример будет занимать гораздо меньше памяти, чем подход 1 к 1. При разделении списка в каждой ветви это может быть похоже на O (k log n) для поиска, но каждый обновляемый узел (включая узлы-предки) обновляется только один раз. случай 1 на 1: (k log n) для поиска каждого узла, но затем другой (k * средняя глубина) для обновления предков (некоторые повторно). В примере вопроса это не было бы значительно сокращено?
2. Конечно, ваш новый пример с бинарным деревом — это, по сути, то, что я имел в виду как обход всей структуры, потому что в общем случае он будет выполнять рекурсивные вызовы по обе стороны дерева. Конечно, в особых случаях вы можете остановиться раньше и избежать обхода частей дерева. В других случаях вам все равно может потребоваться просмотреть часть дерева только для того, чтобы обнаружить, что в этой части дерева фактически не произошло никаких изменений. Вот тогда дополнительное возвращаемое значение boolean, о котором я упоминал, может оказаться полезным, если вы хотите избежать ненужного выделения.
3. Вы переходите по ветке только в том случае, если есть подлежащие обновлению узлы, соответствующие этой ветке. Поиск выполняется точно так же, как и в случае 1 на 1, но он выполняет все k поисков одновременно. Таким образом, вам никогда не понадобится возвращать логическое значение о том, обновлено оно или нет, потому что вы бы не пошли по этой ветке с самого начала, если бы она не была обновлена.
4. Если вы можете сказать, взглянув на конкретный узел, что вам не нужно ничего делать ни на этом узле, ни на любом из его потомков, тогда вам вообще не нужно заходить в узел. Однако часто вы сможете сказать, что вам не нужно ничего делать на самом узле, но необязательно знать о потомках, и в этом случае вам, вероятно, все равно нужно будет перейти к потомкам.
5. Учитывая, что мы говорили о сравнении со случаем O (k log n), я предполагал, что мы говорим об одном и том же типе операций, что означает, что мы будем точно знать, как выполнять поиск и когда останавливаться. Случай, когда вы не знаете о потомках, обычно требует исчерпывающего поиска, так что это не имеет никакого отношения к моему вопросу. В этом вопросе о массовом обновлении у нас есть список существующих узлов, и мы либо хотим удалить их, либо изменить поле в них, либо каким-либо образом заменить их обновленными значениями.
Ответ №2:
Конкретная реализация того, что вы ищете, может быть найдена в переходных процессах Clojure (и ClojureScript).
Короче говоря, учитывая полностью неизменяемую постоянную структуру данных, ее временная версия будет вносить изменения с использованием деструктивной (эффективной с точки зрения распределения) мутации, которую вы можете снова преобразовать в надлежащую постоянную структуру данных, когда закончите свои чувствительные к производительности операции. Только при обратном переходе к постоянной структуре данных создаются новые корни (например), таким образом амортизируя сопутствующие затраты по сравнению с количеством логических операций, которые вы выполнили над структурой, пока она находилась в своей переходной форме.