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

Question

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

Хотя Array[A] является буквально массивом Java, 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.

Answer 3

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

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