Из предыдущих объяснений стало ясно, что разные типы коллекций имеют разные показатели производительности. Что зачастую является основной причиной выбора одной коллекции вместо другой. Показатели для наиболее распространенных операций собраны в таблицах ниже.
Показатели производительности на последовательностях:
head | tail | apply | update | prepend | append | insert | |
---|---|---|---|---|---|---|---|
Не изменяемые | |||||||
List |
C | C | L | L | C | L | - |
LazyList |
C | C | L | L | C | L | - |
ArraySeq |
C | L | C | L | L | L | - |
Vector |
eC | eC | eC | eC | eC | eC | - |
Queue |
aC | aC | L | L | C | C | - |
Range |
C | C | C | - | - | - | - |
String |
C | L | C | L | L | L | - |
Изменяемые | |||||||
ArrayBuffer |
C | L | C | C | L | aC | L |
ListBuffer |
C | L | L | L | C | C | L |
StringBuilder |
C | L | C | C | L | aC | L |
Queue |
C | L | L | L | C | C | L |
ArraySeq |
C | L | C | C | - | - | - |
Stack |
C | L | L | L | C | L | L |
Array |
C | L | C | C | - | - | - |
ArrayDeque |
C | L | C | C | aC | aC | L |
Показатели производительности на множествах и мапах:
lookup | add | remove | min | |
---|---|---|---|---|
Не изменяемые | ||||
HashSet /HashMap |
eC | eC | eC | L |
TreeSet /TreeMap |
Log | Log | Log | Log |
BitSet |
C | L | L | eC1 |
VectorMap |
eC | eC | aC | L |
ListMap |
L | L | L | L |
Изменяемые | ||||
HashSet /HashMap |
eC | eC | eC | L |
WeakHashMap |
eC | eC | eC | L |
BitSet |
C | aC | C | eC1 |
TreeSet |
Log | Log | Log | Log |
Примечание: 1 Предполагаем, что биты плотно упакованы.
Объяснение записей:
C | Операция занимает (быстрое) постоянное время. |
eC | Операция занимает практически постоянное время, но может зависеть от некоторых допущений, таких как максимальная длина вектора или распределение ключей хэширования. |
aC | Операция занимает постоянное амортизированное время. Некоторые вызовы операции могут занять больше времени, но если в среднем выполняется много операций, то на одну операцию приходится постоянное время. |
Log | Операция занимает время, пропорциональное логарифму от размера коллекции. |
L | Операция линейная, т.е. занимает время, пропорциональное размеру коллекции. |
- | Операция не поддерживается. |
В первой таблице рассматриваются типы последовательностей - как изменяемые, так и неизменяемые - со следующими операциями:
head | Выбор первого элемента последовательности. |
tail | Создание новой последовательности, состоящей из всех элементов, кроме первого. |
apply | Работа с индексом. |
update | Функционал обновления (с updated ) для неизменяемых последовательностей и через сайд эффекты обновление (с update ) для изменяемых последовательностей. |
prepend | Добавление элемента спереди последовательности. В неизменяемых последовательностях происходит создание новой последовательности. В изменяемых - модифицируется исходная. |
append | Добавление элемента в конец последовательности. В неизменяемых последовательностях происходит создание новой последовательности. В изменяемых - модифицируется исходная. |
insert | Вставка элемента в любом месте последовательности. Поддерживается только в изменяемых последовательностях. |
Во второй таблице показаны изменяемые и неизменяемые множества и мапы со следующими операциями:
lookup | Проверка наличия элемента во множестве или получение значения, связанного с ключом в мапе. |
add | Добавление нового элемента во множество или пару ключ/значение в мапу . |
remove | Удаление элемента из множества или ключа из мапы. |
min | Наименьший элемент множества, или наименьший ключ в мапе. |
Contributors to this page:
Contents
- Введение
- Изменяемые и Неизменяемые Коллекции
- Трейт Iterable
- Последовательности. Трейт Seq, IndexedSeq и LinearSeq
- Множества
- Мапы
- Реализации Неизменяемых Коллекций
- Реализации Изменяемых Коллекций
- Массивы
- Строки
- Показатели производительности
- Равенство
- Отображения
- Итераторы
- Создание коллекций с нуля
- Преобразования между Java и Scala коллекциями