Разница между массивом и списком в scala

147

В каких случаях следует использовать Array (Buffer) и List (Buffer). Единственное отличие, которое я знаю, заключается в том, что массивы невариантны, а списки ковариантны. А как насчет производительности и некоторых других характеристик?

arrays list scala scala-collections Иерихон
источник

Ответы:

159

Неизменяемые структуры

Scala Listявляется непреложной рекурсивной структурой данных , которая является такой фундаментальной структурой в Scala, что вы должны (возможно) будете использовать его гораздо больше , чем Array(что на самом деле изменяемый - неизменен аналог из Arrayэто IndexedSeq).

Если вы работаете с Java, очевидная параллель - когда использовать LinkedListover ArrayList. Первый обычно используется для списков, которые только когда-либо просматриваются (и размер которых не известен заранее), тогда как последний следует использовать для списков, которые либо имеют известный размер (или максимальный размер), либо для которых важен быстрый произвольный доступ .

Изменяемые структуры

ListBufferобеспечивает преобразование с постоянным временем в a, Listчто является единственной причиной для использования, ListBufferесли требуется такое более позднее преобразование.

Scala Arrayдолжен быть реализован на JVM с помощью массива Java, и, следовательно, он Array[Int]может быть намного более производительным (как int[]), чем List[Int](который будет упаковывать его содержимое, если вы не используете самые последние версии Scala, которые имеют новую @specializedфункцию) .

Однако я думаю, что использование Arrays в Scala должно быть сведено к минимуму, потому что кажется, что вам действительно нужно знать, что происходит под капотом, чтобы решить, действительно ли ваш массив будет поддерживаться требуемым примитивным типом или может быть упакованным как тип оболочки.

Oxbow_lakes
источник
также см. stackoverflow.com/questions/3213368/… и stackoverflow.com/questions/2481149/… определение «равно» для массивов состоит в том, что они относятся к одному и тому же массиву
oluies
131

В дополнение к уже опубликованным ответам, вот некоторые особенности.

В то время как an Array[A]буквально представляет собой массив Java, a List[A]- это неизменяемая структура данных, которая либо Nil(пустой список), либо состоит из пары (A, List[A]).

Различия в производительности

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Различия в памяти

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

Поэтому, если вам не нужен быстрый произвольный доступ, нужно подсчитывать элементы или по какой-то причине вам нужны деструктивные обновления, Listлучше, чем Array.

Апокалисп
источник
Должны ли эти О учитывать время, чтобы скопировать список? Я предполагаю , что вы делаете тест , как это, например: list = list.drop(i). Или, за капотом творится какая-то магия?
2
При этом учитывается копирование списков и массивов при необходимости. Обратите внимание, что такие вещи, как dropникогда не нужно копировать часть списка, которая не была удалена. Например, (x::xs).drop(1)это точно xs, а не "копия" xs.
Apocalisp
6
Эта асимптотика не имеет никакого отношения к Scala. Та же структура данных в C будет точно такой же быстрой с точностью до постоянных коэффициентов.
Apocalisp
1
@Apocalisp У вас есть ссылка или при каких условиях вы определили эту информацию?
Фил
1
@Phil Это асимптотика, а не измерения. Они будут верны при любых условиях.
Apocalisp
18

Массив является изменяемым, что означает, что вы можете изменять значения каждого индекса, в то время как список (по умолчанию) является неизменным, что означает, что новый список создается каждый раз, когда вы вносите изменения. В большинстве случаев это более «функциональный» стиль работы с неизменяемыми типами данных , и вы , вероятно , следует попытаться использовать список с конструкциями , как yield, foreach, matchи так далее.

Что касается характеристик производительности, массив быстрее работает с произвольным доступом к элементам, тогда как список быстрее при добавлении (добавлении) новых элементов. Итерация по ним сопоставима.

Леон
источник
@leonm - apols, я думал, ОП спрашивал исключительно о классах * Buffer, я понимаю, что они также спрашивали о "нормальных"!
oxbow_lakes
2
Обычно быстрее добавлять в ArrayBuffer, чем добавлять в список (или добавлять элемент в ListBuffer), поскольку списки требуют создания объекта-оболочки, в то время как ArrayBuffer просто нужно скопировать объект (в среднем примерно дважды) в новый массив . Две копии обычно быстрее, чем создание одного объекта, поэтому добавление ArrayBuffer обычно превосходит добавление списка.
Рекс Керр
array работает намного быстрее, чем list, когда iterate overиз-за кеширования
Bin