Когда следует выбирать Vector в Scala?

Ответ 1

Как правило, по умолчанию используется Vector. Он быстрее, чем List для почти всего и большего объема памяти для более крупных, чем тривиальных. См. Эту документацию относительно производительности Vector по сравнению с другими коллекциями. Есть несколько минусов для перехода с Vector. В частности:

• Обновления в голове медленнее, чем List (хотя и не так сильно, как вы думаете)

Еще один недостаток перед Scala 2.10 заключался в том, что поддержка соответствия шаблону была лучше для List, но это было исправлено в 2.10 с помощью обобщенных экстракторов +: и :+.

Существует также более абстрактный, алгебраический способ приближения к этому вопросу: какую последовательность вы концептуально имеете? Кроме того, что вы концептуально делаете с ним? Если я вижу функцию, которая возвращает Option[A], я знаю, что функция имеет некоторые дыры в своей области (и, следовательно, является частичной). Мы можем применить эту же логику к коллекциям.

Если у меня есть последовательность типа List[A], я эффективно утверждаю две вещи. Во-первых, мой алгоритм (и данные) полностью структурирован в стеке. Во-вторых, я утверждаю, что единственные вещи, которые я собираюсь сделать с этой коллекцией, - это полные обходы O (n). Эти двое действительно идут рука об руку. И наоборот, если у меня есть что-то типа Vector[A], единственное, что я утверждаю, это то, что мои данные имеют четко определенный порядок и конечную длину. Таким образом, утверждения более слабы с Vector, и это приводит к большей гибкости.

Ответ 2

Ну, a List может быть невероятно быстрым, если алгоритм может быть реализован исключительно с помощью ::, head и tail. У меня был объектный урок этого совсем недавно, когда я избил Java split, создав List вместо Array и не мог победить это чем-нибудь еще.

Однако List имеет фундаментальную проблему: он не работает с параллельными алгоритмами. Я не могу разделить List на несколько сегментов или конкатенатировать его обратно эффективным образом.

Существуют и другие типы коллекций, которые могут обрабатывать parallelism намного лучше - и Vector является одним из них. Vector также имеет большую локальность, которой List не является - это может быть реальным плюсом для некоторых алгоритмов.

Итак, все рассмотренные вопросы, Vector - лучший выбор, если у вас нет конкретных соображений, которые делают один из других коллекций предпочтительным - например, вы можете выбрать Stream, если вы хотите ленивую оценку и кеширование (Iterator быстрее, но не кэширует), или List, если алгоритм естественным образом реализуется с упомянутыми операциями.

Кстати, предпочтительнее использовать Seq или IndexedSeq, если вы не хотите использовать определенную часть API (например, List ::) или даже GenSeq или GenIndexedSeq, если ваш алгоритм может выполняться параллельно.

Ответ 3

Для неизменяемых коллекций, если вам нужна последовательность, основное решение - использовать IndexedSeq или LinearSeq, которые дают разные гарантии производительности. IndexedSeq обеспечивает быстрый случайный доступ к элементам и операцию быстрой длины. LinearSeq обеспечивает быстрый доступ только к первому элементу через head, но также имеет быструю операцию tail. (Взято из документации Seq.)

Для IndexedSeq вы обычно выбираете Vector. Range и WrappedString также являются IndexedSeqs.

При a LinearSeq вы обычно выбираете List или его ленивый эквивалент Stream. Другими примерами являются Queue и Stack s.

Итак, в терминах Java ArrayList используется аналогично Scala Vector и LinkedList аналогично Scala List. Но в Scala я хотел бы использовать List чаще, чем Vector, потому что Scala имеет гораздо лучшую поддержку функций, которые включают обход последовательности, например, отображение, свертывание, итерацию и т.д. Вы будете использовать эти функции для манипулирования список в целом, а не случайный доступ к отдельным элементам.

Ответ 4

Некоторые из приведенных здесь инструкций сбивают с толку или даже ошибочны, особенно идея, что immutable.Вектор в Scala является чем-то вроде ArrayList. Список и вектор являются неизменными, постоянными (т.е. "Дешевыми для получения модифицированной копии" ) структурами данных. Разумного выбора по умолчанию не существует, поскольку они могут быть для изменяемых структур данных, но это скорее зависит от того, что делает ваш алгоритм. Список - это одиночный список, в то время как Vector является целым числом-base-32, т.е. Это своего рода дерево поиска с узлами степени 32. Используя эту структуру, вектор может обеспечить наиболее часто используемые операции достаточно быстро, то есть в O (log_32 (n)). Это работает для добавления, добавления, обновления, произвольного доступа, декомпозиции в head/tail. Итерация в последовательном порядке является линейной. Список, с другой стороны, просто обеспечивает линейную итерацию и постоянное добавление времени, декомпозицию в голове/хвосте. Все остальное занимает общее линейное время.

Это может выглядеть так, как если бы вектор был хорошей заменой List почти во всех случаях, но preend, декомпозиция и итерация часто являются важнейшими операциями над последовательностями в функциональной программе, а константы этих операций (намного) выше для вектора из-за его более сложной структуры. Я сделал несколько измерений, так что итерация примерно вдвое быстрее для списка, в списках добавление примерно в 100 раз быстрее, декомпозиция в голове/хвосте примерно в 10 раз быстрее по спискам, а генерация из проходящего - примерно в 2 раза быстрее для векторов. (Вероятно, это потому, что Vector может выделять массивы из 32 элементов одновременно, когда вы создаете их с помощью построителя вместо добавления или добавления элементов по одному). Конечно, все операции, которые занимают линейное время по спискам, но эффективно постоянное время на векторах (как случайный доступ или добавление), будут чрезмерно медленными в больших списках.

Итак, какую структуру данных мы должны использовать? В принципе, существует четыре распространенных случая:

• Нам нужно только преобразовывать последовательности с помощью операций, таких как map, filter, fold и т.д.: в основном это не имеет значения, мы должны программировать наш алгоритм в целом и даже выиграть от принятия параллельных последовательностей. Для последовательных операций Список, вероятно, немного быстрее. Но вы должны сравнить его, если вам нужно оптимизировать.
• Нам нужен много произвольного доступа и разных обновлений, поэтому мы должны использовать вектор, список будет заведомо медленным.
• Мы работаем над списками классическим функциональным способом, создавая их путем добавления и итерации рекурсивным декомпозицией: использовать список, вектор будет медленнее в 10-100 раз или более.
• У нас есть критический алгоритм производительности, который в основном является обязательным и делает много произвольного доступа к списку, что-то вроде быстрого сортировки: используйте императивную структуру данных, например. ArrayBuffer, локально и скопируйте свои данные и с ним.

Ответ 5

В ситуациях, связанных с большим случайным доступом и случайной мутацией, Vector (или - как docs говорят - a Seq), кажется, является хорошим компромиссом. Это также показывает характеристики производительности.

Кроме того, класс Vector кажется хорошо воспроизводится в распределенных средах без большого дублирования данных, потому что нет необходимости делать копию на запись для всего объекта. (См.: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures)

Ответ 6

Если вы программируете неизменно и нуждаетесь в произвольном доступе, Seq - это путь (если вы не хотите Set, который вы часто на самом деле делаете). В противном случае List работает хорошо, за исключением того, что операции не могут быть распараллелены.

Если вам не нужны неизменные структуры данных, придерживайтесь ArrayBuffer, так как это Scala эквивалентно ArrayList.