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

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

Ответ 1

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

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

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

Изменчивые структуры

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

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

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

Ответ 2

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

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

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

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

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

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

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

Ответ 3

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

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