Освоение структур данных в Ruby — постоянные списки

В завершение этой серии я хочу ввести понятие постоянные структуры данных , термин, введенный Driscoll et al. в статье 1986 года, что в наши дни он лежит в основе большинства чисто функциональных структур данных.

Впервые я услышал этот термин в докладе Рича Хикки, создателя Clojure, где он показал, как структуры данных Closure внутренне справляются с мутациями (точнее, с их отсутствием).

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

Давайте начнем с рассмотрения того, как работают мутации.

В императивных языках программирования, когда вы хотите изменить структуру данных, вы делаете это таким образом, что текущая версия структуры данных уничтожается и заменяется новой. Например, если у вас есть связанный список, содержащий элемент, и вы добавляете еще один, в итоге вы получите список, содержащий два элемента. Предыдущая версия списка (та, которая содержала один элемент) больше недоступна. Отсюда и не стойкие. (Кстати, именно поэтому такого рода обновления называются « деструктивные задания »).

> list = (1)
> list.insert(2)
> list.print(1, 2)

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

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

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

> list1 = List.new(1)
> list2 = List.insert(list1, 2)
> list1.print(1)
> list2.print(1, 2)

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

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

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

Интерфейс постоянного списка

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

Методы

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

Детали реализации

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

Для хранения значений в постоянном списке мы собираемся использовать самодельную версию «однократной записи узлов» для эмуляции неизменного поведения. Это не идеальное решение, но оно будет достаточно хорошим для области, которую мы пытаемся охватить в этом посте. Что мы собираемся сделать, так это позвонить заморозить метод после того, как данные узла были установлены для предотвращения случайных мутаций.

Как и в обычных связанных списках, каждый узел имеет два атрибута.

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

Пустой

Этот метод создает пустой список. Его сложность O (1).

def self.empty
  list = LinkedList.new
  list.freeze
end

Вставлять

Этот метод вставляет новый элемент в доступную только для чтения копию указанного списка и возвращает эту копию.

Так как мы должны скопировать весь список сложность этого метода O (n).

def self.insert list, data
  ret = self.copy list
  ret.insert data
  ret.freeze
end

Обновлять

Обновляет элемент в доступную только для чтения копию указанного списка и возвращает эту копию.

Обновление — это первый метод, при котором происходит амортизация. Стратегия, которую мы используем:

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

Сложность этого метода O(n) где n — количество элементов от головы до целевого узла.

def self.update list, node, data
  ret = LinkedList.new
  reuse = false
  found = false
  list.each do |nd|
    unless found
      found = (nd.data == node.data)
      if found
        ret.insert(data)
        reuse = true
        next
      end
    end
    unless reuse
      ret.insert(data)
    else # Reuse nodes from target to tail.
      ret.reuse_from_node(nd)
        break
    end
  end
  ret.freeze
end

Удалять

Этот метод удаляет элемент из доступной только для чтения копии указанного списка и возвращает эту копию.

Стратегия, которую мы используем здесь, такая же, как и для обновлений, но вместо создания новой версии целевого узла мы просто пропускаем ее при копировании списка.

Как и в случае с обновлениями, повторное использование как можно большего количества узлов является главным приоритетом.

Сложность этого метода O(n) где n — количество элементов от головы до целевого узла.

def self.remove list, node
  ret = LinkedList.new
  reuse = false
  found = false
  list.each do |nd|
    unless found
      found = (nd.data == node.data)
      if found
        reuse = true
        next # skip the target node.
      end
    end
    unless reuse
      ret.insert(nd.data)
    else # Reuse nodes from target to tail.
      ret.reuse_from_node(nd)
      break
    end
  end
  ret.freeze
end

Кошка

Этот метод создает список только для чтения, который содержит копии всех узлов из LHS (слева) и RHS (справа).

Cat — это еще один метод, в котором происходит амортизация, на этот раз хитрость заключается в том, чтобы скопировать только LHS и сцепить RHS до его конца. Поскольку RHS остается нетронутым, его можно безопасно использовать совместно с остальной частью нашей программы.

Сложность этого метода O(n) где n — длина LHS.

def self.cat lhs, rhs
  ret = self.copy lhs
  ret.cat rhs
  ret.freeze
 end

Лен

Этот метод возвращает длину данного списка.

Поскольку внутренний список имеет атрибут, содержащий эту информацию, сложность этого метода O (1).

def self.len list
  list&.length || 0
end

Найти первым

Этот метод находит первое вхождение данного предиката, примененного к указанному списку.

Сложность этого метода составляет O(n).

def self.find_first list, &predicate
  return nil unless list
  return list.find_first &predicate
end

Каждый

Этот метод проходит по указанному списку, возвращая по одному элементу за раз в данный блок.

Сложность этого метода O(n).

def self.each list, &block
  return nil unless list
  list.each &block
end

Распечатать

Этот метод печатает содержимое указанного списка. Сложность этого метода составляет O(n).

def self.print list
  unless list
    print "empty"
  else
    list.print
  end
end

Копировать

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

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

Сложность этого метода составляет O(n).

private
def self.copy src
  dst = LinkedList.new
  src.each { |node| dst.insert node.data }
  dst
end

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

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

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

Итак, это краткое введение в постоянные структуры данных. Я надеюсь, что вам понравилось!

Как обычно, вы можете получить код от здесь.

Спасибо за чтение! Надеюсь, поможет.

PS: если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии бесплатно на вашем устройстве Kindle.

Структуры данных с нуля — Ruby Edition.