Переиспользование памяти в персистентных структурах данных за счет структурного шерингаКратко · дайджест за 9 августа
Кратко≈ 1 мин

Переиспользование памяти в персистентных структурах данных за счет структурного шеринга

В неизменяемом (иммутабельном) программировании операции модификации создают новую версию данных. Без оптимизации это приводило бы к копированию массивов и перерасходу памяти.

Персистентные структуры данных решают эту задачу через механизм структурного шеринга (structural sharing). При добавлении элемента в связный список выделяется память под один новый головной узел со ссылкой на существующий список. Обе версии структуры сосуществуют: исходная остаётся неизменной, а новая занимает память только для добавленного узла. В сбалансированных деревьях пересоздаётся лишь путь от корня к листку, а нетронутые ветви переиспользуются.

Этот механизм реализован в языках Clojure и Scala, а также в библиотеках состояния для JavaScript. Условием безопасности является полная неизменяемость узлов: мутация объекта сделает изменения видимыми в прошлых версиях.

Структурный шеринг сочетает изоляцию данных с эффективным расходом памяти. Разбор архитектуры коллекций представлен в документации Clojure Data Structures.

Хочу подробный разборГолоса помогают выбрать, что разобрать подробно. За этот материал 0 голосов.
Источники · 3