Linkedlist

Я всегда думал: "А зачем нужно писать свой copy-on-write? Ведь круто, когда есть структуры и они такие быстрые, что всё делают за тебя."

Но все это не нужно, пока не начинаешь писать свои типы и не подсаживаешься на LinkedList'ы.

Что такое этот связанный список и какие у него преимущества?

Связанный список имеет несколько теоретических преимуществ по сравнению с вариантами непрерывного хранения, такими как Array:

• Связанные списки имеют временную сложность O (1) для вставки первых элементов. Массивы же имеют временную сложность O (n).

• Соответствие протоколам сбора Swift, таким как Sequence и Collection, предлагает множество полезных методов для довольно небольшого количества требований.

Связанный список (Linked List) - это последовательность элементов данных, в которой каждый элемент называется узлом (Node).

Есть два основных типа связанных списков:

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

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

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

Вот так это всё выглядит:

public class Node<Value> {  public var value: Value  public var next: Node?      public init(value: Value, next: Node? = nil) {    self.value = value    self.next = next  }}public struct LinkedList<Value> {  public var head: Node<Value>?  public var tail: Node<Value>?    public init() {}  public var isEmpty: Bool { head == nil }}

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

Так как наша Node'a является классом, а значит и reference type. Это значит, что для многих узлов у нас есть общая ячейка памяти и куча ссылок на них. Они могут расти и с большими размера за ними сложно наблюдать.

Как решить эту проблему? Поскольку LinkedList является структурой и поэтому должен использовать семантику значений. Внедрение своего COW решит эту проблему.

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

private mutating func copyNodes() {  guard var oldNode = head else {      return  }  head = Node(value: oldNode.value)  var newNode = head    while let nextOldNode = oldNode.next {    newNode!.next = Node(value: nextOldNode.value)    newNode = newNode!.next    oldNode = nextOldNode  }  tail = newNode}

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

Оптимизируем COW

Накладные расходы O (n) при каждом вызове изменения недопустимы.

Есть два пути, которые помогают решить эту проблему. Первый - избегать копирования, когда у узлов только один владелец.

isKnownUniquelyReferenced

В стандартной библиотеке Swift существует функция isKnownUniquelyReferenced. Эта функция может использоваться, чтобы определить, имеет ли объект ровно одну ссылку на него.

И если добавить в начало функции copyNodes() код, то копировать дальше не надо:

private mutating func copyNodes(returningCopyOf node:Node<Value>?) -> Node<Value>? {  guard !isKnownUniquelyReferenced(&head) else {return nil  }  guard var oldNode = head else {return nil}  head = Node(value: oldNode.value)  var newNode = head  var nodeCopy: Node<Value>?  while let nextOldNode = oldNode.next {    if oldNode === node {      nodeCopy = newNode    }    newNode!.next = Node(value: nextOldNode.value)    newNode = newNode!.next    oldNode = nextOldNode}  return nodeCopy}

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

Таким образом Copy-on-write не является чем-то далеким и подкапотным. А вполне управляемым и понятным.