Linked List: Когда нужно писать свой Copy-on-write в iOS?

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