Я всегда думал: "А зачем нужно писать свой 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 не является чем-то далеким и подкапотным. А вполне управляемым и понятным.
