Временная сложность становится O (n), когда возвращаемое значение myArray.reversed () назначено ранее инициализированному массиву? Копирование при записи?

Question

Состояние документов Apple. Сложность времени для метода .reversed () равна O (1).

В следующем коде arr (строка 2) имеет тип ReversedCollection<Array<Int>>.

Почему печать arr (строка 3) не возвращает числа в обратном порядке?

// 1 -  let a = [1, 2, 3, 4, 5]
// 2 -  let arr = a.reversed()   // <- O(1) is the complexity of this operation.
// 3 -  print(arr)               // unexpected - prints ReversedCollection<Array<Int>>(_base: [1, 2, 3, 4, 5])

Что касается следующего примера кода - Преобразование ReversedCollection в Array (строка 2) ) возвращает значения в обратном порядке, как и ожидалось в новом массиве. Дополнительное хранилище было выделено. Я понимаю, что a.reversed() сама операция - O (1). Там нет вопроса об этом. Я не понимаю, как эта операция остается O (1) после преобразования ее вывода во вновь инициализированный массив. Документы Apple показывают это преобразование в Array, а непосредственно под ним упоминается O (1). https://developer.apple.com/documentation/swift/arrayslice/1688969-reversed

Неужели Apple не смогла заявить, что сложность времени и пространства изменилась после завершения выполнения строки 2?

// 1 -  let a = [1, 2, 3, 4, 5]
// 2 -  let arr = Array(a.reversed())    // arr is type Array<Int>
// 3 -  print(arr)                       // prints [5, 4, 3, 2, 1] as expected  

В следующем коде (строка 3) - a.reversed() возвращаемое значение - тип ReversedCollection<Array<Int>>, которому затем присваивается arr - тип Array<Int>. Я обеспокоен тем, что это назначение операции arr устраняет сложность времени O (1); это похоже на код выше (строка 2) - где мы преобразовали ReversedCollection<Array<Int>> в Array.

Является ли код ниже таким же, как код непосредственно выше?

временная сложность остается O (1) после завершения выполнения строки 3 в приведенном ниже коде?

// 1 -  let a = [1, 2, 3, 4, 5]
// 2 -  var arr = a                   // arr is type Array<Int>
// 3 -  arr = arr.reversed()          // assigns a ReversedCollection<Array<Int>> to an Array
// 4 -  print(type(of: arr)           // prints Array<Int>     
// 5 -  print(arr)                    // print [5, 4, 3, 2, 1] as expected

Ниже описан другой сценарий - (строка 3) - возвращается ошибка - невозможно назначить rev для arr. Я представляю его для сравнения с кодом выше (строка 3), который присваивает тип ReversedCollection типу Array на 1 шаг меньше, чем в приведенном ниже коде.

// 1 -  let a = [1, 2, 3]
// 2 -  let rev = a.reversed()       // arr is type Array<Int>
// 3 -  let arr = rev                // Error - Cannot assign value of type 'ReversedCollection<[Int]>' to type '[Int]'

Относительно примера кода ниже (строка 3) - На этот раз я не назначаю arr.reversed() для arr. Это приводит к тому, что arr не меняется, что я не ожидал. Я хотел избежать использования .reverse() в строке 3, потому что это работает в O (n).

// 1 -  let a = [1, 2, 3, 4, 5]
// 2 -  var arr = a                   // arr is type Array<Int>
// 3 -  arr.reversed()                // does not reverse arr's items    
// 5 -  print(arr)                    // prints [1, 2, 3, 4, 5] - not what I initially expected

копирование при записи сохранение сложности времени O (1) даже после того, как ReversedCollection назначено / преобразовано в Array?

Answer 1

Результат .reversed() - это просто структура, которая перебирает коллекцию в обратном направлении. Это стоит постоянного времени для создания. Итерирование по нему стоит O (n), как и любая коллекция.

Так что let rev = a.reversed() - это O (1), но let rev = Array(a.reversed()) - это O (n), поскольку для создания копии итерируется по a. Не существует неявного преобразования. Array и ReversedCollection<Array> - это совершенно разные типы. Вы можете передать любую последовательность в Array.init, и она скопирует значения в новый массив.

Stdlib с открытым исходным кодом, поэтому вы также можете посмотреть на , как все это реализовано . Вы увидите, что инициализатор является только назначением:

internal init(_base: Base) {
  self._base = _base
}

Answer 2

Как вы заметили, Array.reversed () является операцией O (1). Он просто оборачивает исходный массив Array с логами c, которые автоматически корректируют индексы при доступе к ним для эффективного обращения.

Если вы явно создаете новый массив из обращенной коллекции, вы создаете полную копию данные, и вы собираетесь оплатить стоимость O (N). Я не думаю, что оптимизация копирования при записи в Swift применима здесь.

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

var array = [Int]()
for i in 0..<1000000 {
    array.append(i)
}

let startDate = Date()
let reversed = array.reversed() // O(1)
print(Date().timeIntervalSince(startDate)) // ~0s from start

var newArray = Array(reversed) // O(n)
print(Date().timeIntervalSince(startDate)) // ~0.2s from start

newArray[0] = 0
print(Date().timeIntervalSince(startDate)) // ~0.2s from start