Я всегда думал: "А зачем нужно писать свой 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) при каждом вызове изменения недопустимы.
Есть два пути, которые помогают решить эту проблему. Первый - избегать копирования, когда у узлов только один владелец.
В стандартной библиотеке 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 не является чем-то далеким и подкапотным. А вполне управляемым и понятным.
