Скопирована ли вся карта, когда вставлена новая привязка?

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

Я хотел бы понять, как это достигается. Компилятор в конечном итоге реализует это путем копирования всей структуры данных, например. миллионы привязок? Можно ли вообще сказать, что изменяемые структуры данных/массивы (например, Data.Judy) или императивные языки программирования лучше работают в таких случаях? Имеют ли неизменяемые данные какие-либо преимущества, когда речь заходит о словарях/хранилищах значений ключа?

Ответ 1

Map построен на структуре данных дерева. В принципе, создается новое значение Map, но оно будет полностью заполнено указателями на старую структуру. Поскольку значения никогда не изменяются в Haskell, это безопасная и очень важная оптимизация, известная как совместное использование.

Это означает, что у вас может быть много похожих версий той же структуры данных, которая висит вокруг, но только ветки дерева, которые отличаются, будут храниться заново; остальные будут просто указателями на оригинальную копию ветки. И, конечно, если вы выбросите старый Map, ветки, которые вы изменили, будут утилизированы сборщиком мусора.

Обмен ключами является ключом к производительности неизменяемых структур данных. Вы можете найти эту статью в Википедии. у него есть некоторые просветительские графики, показывающие, как измененные данные передаются с общим доступом.

Ответ 2

Нет. В документации для Data.Map.insert указано, что вставка занимает время O (log n). Было бы невозможно удовлетворить эту привязку, если бы ей пришлось скопировать всю структуру.

Ответ 3

Data.Map не копирует старую карту; он (лениво) выделяет O (log N) новые узлы, которые указывают (и тем самым совместно) большую часть старой карты.

Поскольку "обновление" карты не разрушает старые версии, такая структура данных дает вам большую свободу в построении параллельных алгоритмов.