Scala List.updated

Question

Мне любопытно, что List.updated.Что это за время выполнения?И как это можно сравнить с простым изменением одного элемента в ArrayBuffer?На заднем плане, как это происходит с копированием всего списка?Это процедура O (n)?Если да, то есть ли неизменяемая структура данных с обновленным методом like, но не такая медленная?

Пример:

val list = List(1,2,3)
val list2 = list.updated(2, 5) --> # list2 = (1,5,3)
var abuf = ArrayBuffer(1,2,3)
abuf(2) = 5 --> # abuf = (1,5,3)

Answer 1

1. Время и сложность памяти для метода updated(index, value) являются линейными с точки зрения index (не с точки зрения размера списка).Первые ячейки index воссоздаются.

2. Изменение элемента в ArrayBuffer имеет постоянное время и сложность памяти.Вспомогательный массив обновляется на месте, копирование не происходит.

3. Этот метод updated не медленный, если вы обновляете элементы в начале списка.Для больших последовательностей Vector имеет другой способ поделиться общими частями списка и, вероятно, сделает меньше копирования.

Answer 2

List.updated - это операция O (n) (линейная).

Вызывает линейную операцию List.splitAt, чтобы разделить список по индексу для получения двух списков (before, rest), а затем построить новыйсписок, добавляя элементы в before, обновленный элемент, а затем элементы в rest.tail.

Я не уверен - это нужно было бы проверить, но кажется, что если бы обновленный элемент был в начале списка, он может быть довольно эффективным, как в теории получить rest и добавить rest.tail можно сделать за постоянное время.

Answer 3

Я полагаю, что производительность будет O (n), поскольку list не хранит индекс для каждого элемента и реализуется как ссылки на следующий el -> el2 -> el3`, поэтому только операция list.head - это O (1) как быстро. Вы должны использовать IndexedSeq для этой цели с наиболее распространенным вектором имплментации.

Хотя он не копирует данные, поэтому в памяти фактически обновляется только 1 значение. Как правило, все неизменяемые коллекции Scala не копируют все данные о модификации или создании обновленного нового экземпляра. Это ключевое отличие с коллекциями Java.