Я всегда думал: "А зачем нужно писать свой 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 не является чем-то далеким и подкапотным. А вполне управляемым и понятным.
andreyverbin
Непонятно зачем эти приседания. Почему не сделать сам linked list классом?
t-nick
Для коллекций полезно иметь value semantics, чтобы управлять мутабельностью. Немного расширю вопрос. Автор не очень доходчиво описал недостаток реализации через класс:
Почему одна ячейка? Экземпляр узла может быть создан в лубом доступном месте кучи.
Что значит «наблюдать»?
andreyverbin
Вот это поворот, не ожидал, что разработчики Swift такую ошибку сделают. Но теперь понятно, что автор хочет сделать. Эта «классная» особенность Swift делает разработку идиоматических коллекций раз в 10 сложнее. А если подумать про многопоточность и эффективность то наступает полный !"№%:.
Совет автору — не пытайтесь повторить в своих коллекциях дурные паттерны, даже если они исходят от создателей языка. immutable interface прошел тест временем, а COW это геморой на ровном месте, на который вы потратите 90% времени и который нужен в 0.001% случаев (если отказаться от value semantic коллекции).
t-nick
Преимущество связного списка именно в возможности удаления и вставки за O(1). Немутабельный связный список не имеет смысла, как и копирование списка на каждое изменение.
andreyverbin
Immutable interface и immutable linked list это две большие разницы. А вообще NSMurableArray порвёт самодельный linked list на всех, практически значимых, сценариях, там внутри как раз linked list из сегментов.
t-nick
Зачем вам immutable interface, кода вы хотите менять состояние объекта? Можно конечно иметь методы возвращающие измененную копию, но это непрактично для данной задачи.
NSMurableArray
— имеет как раз mutable interface, потомуNSArray
приходится копировать на каждый чих.Вы, похоже, слабо представляете себе область применения связного списка. Это не только вставка/удаление элементов за O(1), но и, например, доступ к следующему/предыдущему элементам и манипуляции над ними без индекса за то же, константное, время.
NSMutableArray
такого интерфейса не предоставляет. То, что он использует связный список под капотом, не делает его связным списком.Но нужно признать, что задачи, требующие применения связного списка, на iOS встречаются нечасто.
andreyverbin
Immutable interface нужен чтобы кто- о мог произвести объект, а затем передать его куда-то зная, что его менять не будут. Внутри класса NSMutableArray а наружу торчит NSArray. Почти всегда этого достаточно и ничего копировать не нужно.
Но больше всего меня волнует вопрос зачем автор делает struct и парится с copy on write, когда можно сделать по аналогии с NSArray/NSMutableArray.
i++ — взять следующий элемент от текущего. i -= 1 — взять предыдущий.
Чем LinkedListNode i отличается принципиально от int i?
Я веду к тому, что разница настолько незначительная, что нет смысла делать свой список.
t-nick
Код, который использует
NSArray
, не может полагаться на его иммутабельность, поэтому обычно создается локальная копия исходного массива (для параметра метода — это обычно перебор, но для поля класса — обязательно). В этом плане value semantics в Swift намного более удобен, так как нельзя забыть скопировать структуру, она всегда копируется.В linked list индексы не используются. Точнее linked list используют вместо массива там, где доступ по индексу неудобен или невозможен, но требуется доступ к соседним элементам имея ссылку на исходный элемент.
Несколько наивное заявление. Вам просто не попадалась соответсвующая задача. При этом, как правило, подобные задачи достаточно специфичны и требуют реализации списка с нуля. По этой же причине в стандартных библиотеках связные списки — редкость.