Какие структуры данных вы можете использовать для удаления и замены O (1)? Или как избежать ситуаций, когда вам нужны упомянутые конструкции?
22
Какие структуры данных вы можете использовать для удаления и замены O (1)? Или как избежать ситуаций, когда вам нужны упомянутые конструкции?
ST
Монады в Haskell делает это превосходно.Ответы:
Существует огромное количество структур данных, использующих лень и другие приемы для достижения амортизированного постоянного времени или даже (в некоторых ограниченных случаях, таких как очереди ) обновлений постоянного времени для многих видов проблем. Кандидатская диссертация Криса Окасаки «Чисто функциональные структуры данных» и одноименная книга являются ярким примером (возможно, первым основным), но с тех пор эта область продвинулась вперед . Эти структуры данных, как правило, не только чисто функциональны в интерфейсе, но также могут быть реализованы на чистом языке Haskell и аналогичных языках и являются полностью постоянными.
Даже без какого-либо из этих расширенных инструментов простые сбалансированные бинарные деревья поиска обеспечивают обновления в логарифмическом времени, поэтому изменяемая память может быть смоделирована с наихудшим логарифмическим замедлением.
Существуют и другие варианты, которые можно считать мошенничеством, но они очень эффективны в отношении усилий по внедрению и реальной производительности. Например, линейные типы или типы уникальности позволяют обновлять на месте в качестве стратегии реализации концептуально чистого языка, предотвращая сохранение программой предыдущего значения (памяти, которая будет видоизменяться). Это менее общее, чем постоянные структуры данных: например, вы не можете легко создать журнал отмены, сохранив все предыдущие версии состояния. Это все еще мощный инструмент, хотя AFAIK еще не доступен на основных функциональных языках.
Другой вариант безопасного введения изменяемого состояния в функциональную настройку - это
ST
монада в Haskell. Он может быть реализован без мутаций и, кромеunsafe*
функций запрета , ведет себя так, как если бы он был просто модной оболочкой для неявной передачи постоянной структуры данных (ср.State
). Но из-за некоторой хитрости системы типов, которая обеспечивает порядок оценки и предотвращает экранирование, ее можно безопасно реализовать с помощью мутации на месте со всеми преимуществами производительности.источник
Одна дешевая изменяемая структура - стек аргументов.
Взгляните на типичный факторный расчет в стиле SICP:
Как видите, второй аргумент to
fac
используется как изменяемый аккумулятор для хранения быстро меняющегося продуктаn * (n-1) * (n-2) * ...
. Однако в поле зрения нет изменяемой переменной, и нет способа непреднамеренно изменить аккумулятор, например, из другого потока.Это, конечно, ограниченный пример.
Вы можете получить неизменяемые связанные списки с дешевой заменой головного узла (и, соответственно, любой части, начинающейся с головки): вы просто указываете новую головку на тот же следующий узел, что и старая головка. Это хорошо работает со многими алгоритмами обработки списков (на
fold
основе чего угодно ).Вы можете получить довольно хорошую производительность от ассоциативных массивов, основанных, например, на HAMT . Логически вы получаете новый ассоциативный массив с измененными парами ключ-значение. Реализация может делиться большей частью общих данных между старыми и вновь созданными объектами. Это не O (1), хотя; обычно вы получаете что-то логарифмическое, по крайней мере, в худшем случае. С другой стороны, неизменяемые деревья обычно не страдают от снижения производительности по сравнению с изменчивыми деревьями. Конечно, это требует некоторых накладных расходов памяти, обычно далеко не запретительных.
Другой подход основан на идее, что если дерево падает в лес и никто его не слышит, ему не нужно издавать звук. То есть, если вы можете доказать, что немного видоизмененного состояния никогда не покидает какую-то локальную область, вы можете безопасно изменять данные в нем.
Clojure имеет переходные процессы, которые являются изменчивыми «тенями» неизменяемых структур данных, которые не просачиваются за пределы локальной области видимости. Clean использует Unique для достижения чего-то похожего (если я правильно помню). Rust помогает делать подобные вещи со статически проверенными уникальными указателями.
источник
ref
и связывания их в определенной области. СмотритеIORef
илиSTRef
. И затем, конечно, естьTVar
s иMVar
s, которые похожи, но со здравой параллельной семантикой (stm дляTVar
s и мьютекс, основанный дляMVar
s)То, что вы спрашиваете, слишком широкое. O (1) удаление и замена из какой позиции? Глава последовательности? Хвост? Произвольная позиция? Используемая структура данных зависит от этих деталей. Тем не менее, 2-3 Finger Trees кажутся одной из самых универсальных постоянных структур данных:
Обычно постоянные структуры данных имеют логарифмическую производительность при изменении произвольных позиций. Это может быть или не быть проблемой, поскольку константа в алгоритме O (1) может быть высокой, а логарифмическое замедление может быть «поглощено» в более медленном общем алгоритме.
Что еще более важно, постоянные структуры данных облегчают рассуждения о вашей программе, и это всегда должно быть режимом работы по умолчанию. По возможности следует отдавать предпочтение постоянным структурам данных и использовать изменяемую структуру данных только после того, как вы профилировали и определили, что постоянная структура данных является узким местом в производительности. Все остальное - преждевременная оптимизация.
источник