Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с постоянным хранилищем .

В вычислениях , A постоянная структура данных является структурой данных , которая всегда сохраняет предыдущую версию себя , когда он изменяется. Такие структуры данных фактически неизменяемы , поскольку их операции (явно) не обновляют структуру на месте, а вместо этого всегда создают новую обновленную структуру. Этот термин был введен в статье Дрисколла, Сарнака, Слеатора и Тарьянса 1986 года. [1]

Структура данных является частично постоянной, если доступны все версии, но можно изменять только самую новую версию. Структура данных полностью постоянна, если к каждой версии можно получить доступ и изменить ее. Если существует также операция слияния или слияния, которая может создать новую версию из двух предыдущих версий, структура данных называется конфлюентно-постоянной . Структуры, которые не являются постоянными, называются эфемерными . [2]

Эти типы структур данных особенно распространены в логическом и функциональном программировании , [2] , как языки в этих парадигмах препятствовать (или полностью запретить) использование изменяемых данных.

Частичное или полное сохранение [ править ]

В модели частичной сохраняемости программист может запрашивать любую предыдущую версию структуры данных, но может обновлять только последнюю версию. Это подразумевает линейный порядок среди каждой версии структуры данных. [3] В полностью персистентной модели и обновления, и запросы разрешены для любой версии структуры данных. В некоторых случаях характеристики производительности при запросе или обновлении более старых версий структуры данных могут ухудшиться, как это справедливо для структуры данных Rope . [4]Кроме того, структура данных может называться конфлюентно-постоянной, если, помимо того, что она полностью постоянна, две версии одной и той же структуры данных могут быть объединены для формирования новой версии, которая остается полностью постоянной. [5]

Способы сохранения предыдущих версий [ править ]

Копирование при записи [ править ]

Одним из методов создания постоянной структуры данных является использование предоставленной платформой эфемерной структуры данных, такой как массив, для хранения данных в структуре данных и копирование всей этой структуры данных с использованием семантики копирования при записи для любых обновлений данных. структура. Это неэффективный метод, потому что вся структура данных резервного копирования должна копироваться для каждой записи, что приводит к худшему случаю O (n · m) характеристик производительности для m модификаций массива размера n. [ необходима цитата ]

Толстый узел [ править ]

Метод толстого узла состоит в том, чтобы записывать все изменения, внесенные в поля узлов в самих узлах, без удаления старых значений полей. Для этого требуется, чтобы узлы были произвольно «толстыми». Другими словами, каждый толстый узел содержит одну и ту же информацию и указатель.fields как эфемерный узел, а также пространство для произвольного количества дополнительных значений поля. Каждое дополнительное значение поля имеет связанное имя поля и отметку версии, которая указывает версию, в которой названное поле было изменено на указанное значение. Кроме того, каждый толстый узел имеет свой штамп версии, указывающий версию, в которой узел был создан. Единственная цель узлов, имеющих отметки версии, - убедиться, что каждый узел содержит только одно значение для каждого имени поля для каждой версии. Для навигации по структуре каждое исходное значение поля в узле имеет отметку версии, равную нулю.

Сложность жирового узла [ править ]

При использовании метода толстого узла для каждой модификации требуется O (1) места: просто сохраните новые данные. Каждая модификация занимает O (1) дополнительного времени, чтобы сохранить модификацию в конце истории модификаций. Это амортизированный временной интервал, предполагающий, что история изменений хранится в растущем массиве . Во время доступа должна быть найдена правильная версия на каждом узле по мере прохождения структуры. Если бы необходимо было сделать «m» модификаций, то каждая операция доступа имела бы замедление на O (log m) из-за затрат на поиск ближайшей модификации в массиве.

Копирование пути [ править ]

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

Сложность копирования пути [ править ]

При m модификациях это требует дополнительного времени поиска O (log m) . Время и пространство модификации ограничены размером самого длинного пути в структуре данных и стоимостью обновления в эфемерной структуре данных. В сбалансированном двоичном дереве поиска без родительских указателей сложность времени модификации наихудшего случая равна O (log n + стоимость обновления). Однако в связанном списке сложность времени модификации наихудшего случая составляет O (n + стоимость обновления).

Комбинация [ править ]

Дрисколл, Сарнак, Слеатор , Тарджан [1] придумали способ объединить методы толстых узлов и копирования пути, достигнув O (1) замедления доступа и O (1) пространственной и временной сложности модификации.

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

При каждом доступе к узлу флажок модификации устанавливается, и его временная метка сравнивается со временем доступа. (Время доступа указывает версию рассматриваемой структуры данных.) Если поле модификации пусто или время доступа предшествует времени модификации, то поле модификации игнорируется и учитывается только нормальная часть узла. С другой стороны, если время доступа превышает время модификации, то используется значение в поле модификации, переопределяя это значение в узле.

Изменение узла работает следующим образом. (Предполагается, что каждая модификация касается одного указателя или подобного поля.) Если поле модификации узла пусто, то оно заполняется модификацией. В противном случае поле модификации заполнено. Создается копия узла, но с использованием только последних значений. Модификация выполняется непосредственно на новом узле, без использования окна модификации. (Одно из полей нового узла перезаписывается, а поле его модификации остается пустым.) Наконец, это изменение каскадно передается родительскому узлу, точно так же, как копирование пути. (Это может включать заполнение поля модификации родителя или рекурсивное создание копии родителя. Если у узла нет родителя - это корень, - новый корень добавляется к отсортированному массиву корней.)

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

Сложность комбинации [ править ]

Время и место для модификаций требуют амортизированного анализа. Модификация занимает O (1) амортизированного пространства и O (1) амортизированного времени. Чтобы понять, почему, используйте потенциальную функцию ϕ, где ϕ (T) - количество полных активных узлов в T. Активные узлы T - это просто узлы, которые доступны из текущего корня в текущее время (то есть после последней модификации). Полные активные узлы - это активные узлы, чьи поля модификации заполнены.

Каждая модификация включает в себя некоторое количество копий, скажем k, за которым следует одно изменение в поле модификации. Рассмотрим каждую из k копий. Каждый стоит O (1) пространства и времени, но уменьшает потенциальную функцию на единицу. (Во-первых, копируемый узел должен быть полным и активным, чтобы он вносил свой вклад в потенциальную функцию. Однако потенциальная функция будет отключена только в том случае, если старый узел недоступен в новом дереве. Но известно, что он недоступен в новом дереве - следующим шагом в алгоритме будет изменение родительского узла, чтобы он указывал на копию. Наконец, известно, что поле модификации копии пусто. Таким образом, заменен полный рабочий узел заменяется пустым живым узлом, и ϕ уменьшается на единицу.) Последний шаг заполняет поле модификации, которое стоит O (1) времени и увеличивает ϕ на единицу.

Суммируя все вместе, изменение ϕ равно ∆ϕ = 1− k. Таким образом, алгоритм занимает O (k + Δϕ) = O (1) пространства и O (k + Δϕ +1) = O (1) раз

Примеры постоянных структур данных [ править ]

Возможно, самая простая постоянная структура данных - это односвязный список или список на основе cons , простой список объектов, каждый из которых содержит ссылку на следующий в списке. Это повторяется , потому что хвост списка может быть принято, то есть последние K элементов для некоторых к , и новых узлы могут быть добавлены перед ним. Хвост не будет дублироваться, вместо этого он станет общим для старого и нового списков. Пока содержимое хвоста неизменяемо, это совместное использование будет невидимым для программы.

Многие распространенные структуры данных на основе ссылок, такие как красно-черные деревья , [6] стеки , [7] и treaps , [8], могут быть легко адаптированы для создания постоянной версии. Некоторым другим требуется немного больше усилий, например: очереди , очереди и расширения, включая min-deques (которые имеют дополнительную операцию O (1) min, возвращающую минимальный элемент) и deques с произвольным доступом (которые имеют дополнительную операцию произвольного доступа с сублинейная, чаще всего логарифмическая, сложность).

Существуют также постоянные структуры данных, которые используют деструктивные [ требующие разъяснения ] операции, что делает невозможным их эффективную реализацию на чисто функциональных языках (например, Haskell вне специализированных монад, таких как состояние или ввод-вывод), но возможно на таких языках, как C или Java. Этих типов структур данных часто можно избежать с помощью другого дизайна. Одним из основных преимуществ использования чисто постоянных структур данных является то, что они часто лучше работают в многопоточных средах.

Связанные списки [ править ]

Односвязные списки - это простая структура данных в функциональных языках. [9] Некоторые языки, унаследованные от ML , такие как Haskell , являются чисто функциональными, потому что после того, как узел в списке был выделен, он не может быть изменен, а только скопирован, указан или уничтожен сборщиком мусора, когда на него ничего не ссылается. (Обратите внимание , что сам по себе ML является не чисто функциональным, но поддерживает неразрушающий список операции подмножества, которое также верно в Лиспе (Лисп) функциональных диалекты языка как Scheme и рэкет .)

Рассмотрим два списка:

xs = [0, 1, 2]ys = [3, 4, 5]

Они будут представлены в памяти следующим образом:

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

Теперь объединим два списка:

zs = xs ++ ys

приводит к следующей структуре памяти:

Обратите внимание, что узлы в списке xsбыли скопированы, но узлы ysявляются общими. В результате исходные списки ( xsи ys) сохраняются и не изменяются.

Причина копирования заключается в том, что последний узел в xs(узел, содержащий исходное значение 2) нельзя изменить так, чтобы он указывал на начало ys, потому что это изменило бы значение xs.

Деревья [ править ]

Рассмотрят бинарное дерево поиска , [9] , где каждый узел в дереве имеет рекурсивный инвариант , что все подузлы , содержащиеся в леве поддерева , имеют значение, которое меньше или равно значению , сохраненные в узле, и подузлы содержатся в правом поддерево имеет значение, превышающее значение, хранящееся в узле.

Например, набор данных

xs = [a, b, c, d, f, g, h]

может быть представлено следующим двоичным деревом поиска:

Функция, которая вставляет данные в двоичное дерево и поддерживает инвариант:

 забавная  вставка  ( x ,  E )  =  T  ( E ,  x ,  E )  |  insert  ( x ,  s  as  T  ( a ,  y ,  b ))  =  if  x  <  y  then  T  ( insert  ( x ,  a ),  y ,  b )  else  if  x  >  y  then  T  ( a , y ,  вставить  ( x ,  b ))  иначе  s

После выполнения

ys = insert ("e", xs)

Производится следующая конфигурация:

Обратите внимание на два момента: во-первых, xsсохраняется исходное tree ( ). Во-вторых, старое и новое дерево разделяют многие общие узлы. С такой сохраняемостью и совместным использованием трудно справиться без какой-либо формы сборки мусора (GC) для автоматического освобождения узлов, которые не имеют живых ссылок, и именно поэтому GC - это функция, обычно встречающаяся в языках функционального программирования .

Постоянный массив хешей сопоставлен с деревом [ править ]

Отображенное дерево с постоянным хэш-массивом - это специализированный вариант сопоставленного дерева хэш-массива , который сохраняет предыдущие версии самого себя при любых обновлениях. Он часто используется для реализации постоянной структуры данных карты общего назначения. [10]

Попытки сопоставления хэш-массива были первоначально описаны в статье Фила Багвелла 2001 года, озаглавленной «Идеальные хеш-деревья». В этом документе представлена ​​изменяемая хеш-таблица, в которой «времена вставки, поиска и удаления малы и постоянны, независимо от размера набора ключей, операции - O (1). Небольшие наихудшие времена для операций вставки, поиска и удаления могут быть гарантированы и пропуски обходятся дешевле, чем успешные поиски ». [11] Эта структура данных была затем изменена Ричем Хикки, чтобы сделать ее полностью устойчивой для использования в языке программирования Clojure . [12]

Концептуально попытки сопоставления хэш-массива работают аналогично любому общему дереву в том, что они хранят узлы иерархически и извлекают их, следуя пути вниз к определенному элементу. Ключевое отличие состоит в том, что попытки сопоставления хэш-массива сначала используют хеш-функцию для преобразования своего ключа поиска в целое число (обычно 32- или 64-разрядное). Затем определяется путь вниз по дереву с использованием срезов двоичного представления этого целого числа для индексации в разреженный массив на каждом уровне дерева. Листовые узлы дерева ведут себя аналогично сегментам, используемым для построения хеш-таблиц, и могут содержать или не содержать несколько кандидатов в зависимости от хеш-коллизий . [10]

В большинстве реализаций попыток сопоставления постоянного хеш-массива используется коэффициент ветвления 32. Это означает, что на практике, хотя вставки, удаления и поиск в постоянном хэш-массиве, сопоставленном trie, имеют вычислительную сложность O (log n ), для большинства приложений они фактически являются постоянным временем, так как для этого потребуется чрезвычайно большое количество записей. сделать любую операцию более десятка шагов. [13]

Использование в языках программирования [ править ]

Haskell [ править ]

Haskell - это чисто функциональный язык, поэтому он не допускает изменений. Следовательно, все структуры данных в языке являются постоянными, поскольку невозможно не сохранить предыдущее состояние структуры данных с функциональной семантикой. [14] Это связано с тем, что любое изменение структуры данных, которое сделало бы предыдущие версии структуры данных недействительными, нарушило бы ссылочную прозрачность .

В своей стандартной библиотеке Haskell имеет эффективные постоянные реализации для связанных списков, [15] Maps (реализованных в виде деревьев со сбалансированным размером), [16] и Sets [17] среди других. [18]

Clojure [ править ]

Как и многие языки программирования в семействе Lisp , Clojure содержит реализацию связанного списка, но, в отличие от других диалектов, его реализация связанного списка обеспечивает постоянство, а не постоянство по соглашению. [19] Clojure также имеет эффективные реализации постоянных векторов, отображений и наборов, основанных на попытках сопоставления постоянного хэш-массива. Эти структуры данных реализуют обязательные части структуры коллекций Java, доступные только для чтения . [20]

Разработчики языка Clojure отстаивают использование постоянных структур данных вместо изменяемых структур данных, потому что они имеют семантику значений, которая дает преимущество, позволяющее свободно обмениваться ими между потоками с дешевыми псевдонимами, простыми в изготовлении и независимыми от языка. [21]

Эти структуры данных составляют основу поддержки параллельных вычислений в Clojure, поскольку они позволяют легко повторять операции, чтобы обойти гонку данных и семантику атомарного сравнения и обмена . [22]

Вяз [ править ]

Язык программирования Elm является чисто функциональным, как Haskell, что делает все его структуры данных постоянными по необходимости. Он содержит постоянные реализации связанных списков, а также постоянные массивы, словари и наборы. [23]

Elm использует настраиваемую виртуальную реализацию DOM, которая использует постоянный характер данных Elm. В 2016 году разработчики Elm сообщили, что этот виртуальный DOM позволяет языку Elm отображать HTML быстрее, чем популярные JavaScript- фреймворки React , Ember и Angular . [24]

Java [ править ]

Язык программирования Java не особо функциональный. Несмотря на это, основной пакет JDK java.util.concurrent включает CopyOnWriteArrayList и CopyOnWriteArraySet, которые представляют собой постоянные структуры, реализованные с использованием методов копирования при записи. Однако обычная реализация параллельной карты в Java, ConcurrentHashMap, не является постоянной. Полностью постоянные коллекции доступны в сторонних библиотеках или на других языках JVM.

JavaScript [ править ]

Популярная база интерфейса JavaScript React часто используются вместе с системой управления государственной , которая реализует архитектура Flux , [25] [26] популярная реализацией которых является JavaScript библиотека Redux . Библиотека Redux основана на шаблоне управления состоянием, используемом в языке программирования Elm, что означает, что она требует, чтобы пользователи обрабатывали все данные как постоянные. [27] В результате проект Redux рекомендует, чтобы в определенных случаях пользователи использовали библиотеки для принудительных и эффективных устойчивых структур данных. Сообщается, что это обеспечивает более высокую производительность, чем при сравнении или создании копий обычных объектов JavaScript. [28]

Одна из таких библиотек постоянных структур данных Immutable.js основана на структурах данных, сделанных доступными и популяризованными Clojure и Scala. [29] В документации Redux он упоминается как одна из возможных библиотек, которые могут обеспечить принудительную неизменяемость. [28] Mori.js переносит в JavaScript структуры данных, аналогичные тем, что есть в Clojure. [30] Immer.js предлагает интересный подход, при котором «создается следующее неизменяемое состояние, изменяя текущее». [31]

Scala [ править ]

Язык программирования Scala способствует использованию постоянных структур данных для реализации программ с использованием «объектно-функционального стиля». [32] Scala содержит реализации многих постоянных структур данных, включая связанные списки, красно-черные деревья , а также попытки сопоставления постоянных хэш-массивов, представленные в Clojure. [33]

Сборка мусора [ править ]

Поскольку постоянные структуры данных часто реализуются таким образом, что последовательные версии структуры данных совместно используют базовую память [34], эргономичное использование таких структур данных обычно требует некоторой формы автоматической системы сбора мусора, такой как подсчет ссылок или метка и очистка . [35] На некоторых платформах, где используются постоянные структуры данных, можно не использовать сборку мусора, что, хотя и может привести к утечкам памяти , в некоторых случаях может положительно повлиять на общую производительность приложения. [36]

См. Также [ править ]

  • Копирование при записи
  • Навигационная база данных
  • Постоянные данные
  • Ретроактивные структуры данных
  • Чисто функциональная структура данных

Ссылки [ править ]

  1. ^ a b Дрисколл JR, Sarnak N, Sleator DD, Tarjan RE (1986). Обеспечение постоянства структур данных . Судебный процесс STOC '86. Материалы восемнадцатого ежегодного симпозиума ACM по теории вычислений . С. 109–121. CiteSeerX  10.1.1.133.4630 . DOI : 10.1145 / 12130.12142 . ISBN 978-0-89791-193-1.
  2. ^ a b Каплан, Хаим (2001). «Постоянные структуры данных» . Справочник по структурам данных и приложениям .
  3. ^ Кончон, Сильвен; Filliâtre, Жан-Кристоф (2008), "Semi-стойкие структуры данных", Языки и системы программирования , Lecture Notes в области компьютерных наук, 4960 , Springer Berlin Heidelberg, стр 322-336,. Дои : 10.1007 / 978-3-540- 78739-6_25 , ISBN 9783540787389
  4. ^ Tiark, Bagwell, Филипп Rompf (2011). RRB-деревья: эффективные неизменяемые векторы . OCLC 820379112 . 
  5. ^ Бродал, Герт Стёльтинг; Макрис, Христос; Цихлас, Костас (2006), «Чисто функциональные отсортированные списки с постоянным временем наихудшего случая», конспект лекций по информатике , Springer Berlin Heidelberg, стр. 172–183, CiteSeerX 10.1.1.70.1493 , doi : 10.1007 / 11841036_18 , ISBN  9783540388753
  6. ^ Нил Сарнак; Роберт Э. Тарджан (1986). «Расположение плоских точек с использованием постоянных деревьев поиска» (PDF) . Коммуникации ACM . 29 (7): 669–679. DOI : 10.1145 / 6138.6151 . Архивировано из оригинального (PDF) 10.10.2015 . Проверено 6 апреля 2011 .
  7. ^ Крис Окасаки. «Чисто функциональные структуры данных (тезис)» (PDF) . Цитировать журнал требует |journal=( помощь )
  8. ^ Liljenzin, Олл (2013). «Конфлюэнтно постоянные множества и карты». arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L . Цитировать журнал требует |journal=( помощь )
  9. ^ a b Этот пример взят из Окасаки. См. Библиографию.
  10. ^ a b BoostCon (13 июня 2017 г. ), C ++ Now 2017: Фил Нэш «Святой Грааль !? Постоянное Trie- хранилище с отображением хеш-массива для C ++» , получено 22 октября 2018 г.
  11. ^ Фил, Багвелл (2001). «Идеальные хеш-деревья» . Цитировать журнал требует |journal=( помощь )
  12. ^ "Мы еще там?" . InfoQ . Проверено 22 октября 2018 .
  13. ^ Steindorfer, Майкл Дж .; Винью, Юрген Дж. (2015-10-23). «Оптимизация попыток сопоставления хэш-массива для быстрых и компактных неизменяемых коллекций JVM» . Уведомления ACM SIGPLAN . 50 (10): 783–800. DOI : 10.1145 / 2814270.2814312 . ISSN 0362-1340 . 
  14. ^ "Язык Haskell" . www.haskell.org . Проверено 22 октября 2018 .
  15. ^ "Data.List" . hackage.haskell.org . Проверено 23 октября 2018 .
  16. ^ "Data.Map.Strict" . hackage.haskell.org . Проверено 23 октября 2018 .
  17. ^ "Data.Set" . hackage.haskell.org . Проверено 23 октября 2018 .
  18. ^ "Производительность / Массивы - HaskellWiki" . wiki.haskell.org . Проверено 23 октября 2018 .
  19. ^ «Clojure - Отличия от других Лиспов» . clojure.org . Проверено 23 октября 2018 .
  20. ^ «Clojure - структуры данных» . clojure.org . Проверено 23 октября 2018 .
  21. ^ «Основной доклад: Ценность ценностей» . InfoQ . Проверено 23 октября 2018 .
  22. ^ "Clojure - Атомы" . clojure.org . Проверено 30 ноября 2018 .
  23. ^ "ядро 1.0.0" . package.elm-lang.org . Проверено 23 октября 2018 .
  24. ^ "blog / blazing-fast-html-round-two" . elm-lang.org . Проверено 23 октября 2018 .
  25. ^ "Flux | Архитектура приложений для создания пользовательских интерфейсов" . facebook.github.io . Проверено 23 октября 2018 .
  26. ^ Mora, Osmel (2016-07-18). «Как работать с состоянием в React» . Экосистема React . Проверено 23 октября 2018 .
  27. ^ "Прочтите меня - Redux" . redux.js.org . Проверено 23 октября 2018 .
  28. ^ a b «Неизменяемые данные - Redux» . redux.js.org . Проверено 23 октября 2018 .
  29. ^ "Immutable.js" . facebook.github.io . Архивировано из оригинала на 2015-08-09 . Проверено 23 октября 2018 .
  30. ^ https://swannodette.github.io/mori/
  31. ^ https://github.com/immerjs/immer
  32. ^ «Сущность объектно-функционального программирования и практический потенциал Scala - блог Codecentric AG» . Блог codecentric AG . 2015-08-31 . Проверено 23 октября 2018 .
  33. ^ ClojureTV (2013-01-07), Extreme Cleverness: Functional Data Structures in Scala - Daniel Spiewak , получено 23.10.2018
  34. ^ "Владимир Костюков - Сообщения / Слайды" . kostyukov.net . Проверено 30 ноября 2018 .
  35. ^ "http://wiki.c2.com/?ImmutableObjectsAndGarbageCollection" . wiki.c2.com . Проверено 30 ноября 2018 . Внешняя ссылка в |title=( помощь )
  36. ^ «Последний рубеж в производительности Java: удаление сборщика мусора» . InfoQ . Проверено 30 ноября 2018 .


Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

  • Облегченная реализация устойчивых красно-черных деревьев на Java
  • Эффективные постоянные структуры в C #