[Алгоритмы, Swift] Linked List: Когда нужно писать свой Copy-on-write в iOS?

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 2 месяца
Сообщений: 27286

news_bot ^® написал(а)
01-Янв-2021 20:31

Цитировать

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

Теги для поиска: #_algoritmy (Алгоритмы), #_swift, #_linkedlist, #_algoritmy (
Алгоритмы
), #_swift

Профиль ЛС

Ответить на тему

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

Текущее время: 01-Май 18:31
Часовой пояс: UTC + 5