F # Map.add время и пространство сложность

Question

Насколько я знаю, тип данных Map в F # является неизменным (в отличие от массивов).Это поднимает для меня вопрос, что именно выполняет функция Map.add внутри.Копирует ли она всю структуру, чтобы оставить оригинал без изменений (что было бы очень неэффективно), или использует более умную стратегию, которая гарантирует, что временная сложность все еще приблизительно равна log n?К сожалению, в документах Microsoft такие вещи, как сложность, вообще не упоминаются, хотя и важны в некоторых случаях.

Answer 1

На вопрос "что Map.add делает внутренне" вы можете ответить самостоятельно, взглянув на реализацию .

Как правило, F # Map - это постоянная структура данных , основанная на самобалансирующемся дереве поиска.Общая идея использования такой структуры заключается в том, что при обновлении необходимо переписать только часть структуры - и эта часть фактически создается с нуля, тогда как поддеревья, которые не меняются, распределяются между «старым» и «старым».обновленные "версии структуры.

Сложность операций поиска и добавления составляет O (log n), средний регистр (как и следовало ожидать от базовой структуры дерева).

Answer 2

F # Map использует отсортированное сбалансированное дерево под капотом.Во время обновлений обновляются только узлы, участвующие в пути к обновлению.Остальное используется повторно.

К вашему сведению Map исходный код: https://github.com/Microsoft/visualfsharp/blob/master/src/fsharp/FSharp.Core/map.fs