Когда я должен выбрать Vector в Scala?

Похоже, что Vectorопоздал на вечеринку коллекций Scala, и все влиятельные посты в блоге уже ушли.

В Java ArrayListэто коллекция по умолчанию - я мог бы использовать, LinkedListно только когда я продумал алгоритм и достаточно осторожен, чтобы оптимизировать. В Scala я должен использовать Vectorпо умолчанию Seqили пытаться работать, когда Listэто на самом деле более уместно?

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

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

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

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

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

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

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

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

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

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

Некоторые из приведенных здесь утверждений сбивают с толку или даже ошибочны, особенно идея о том, что immutable.Vector в Scala - это что-то вроде ArrayList. List и Vector являются неизменными, постоянными (то есть «дешевыми, чтобы получить измененную копию») структурами данных. Нет разумного выбора по умолчанию, так как они могут быть для изменяемых структур данных, но это скорее зависит от того, что делает ваш алгоритм. List - это односвязный список, а Vector - целочисленное дерево с целым числом 32, т. Е. Это своего рода дерево поиска с узлами степени 32. Используя эту структуру, Vector может предоставлять наиболее распространенные операции достаточно быстро, т. Е. В O (log_32 ( п)). Это работает для prepend, append, update, произвольного доступа, декомпозиции в голове / хвосте. Итерация в последовательном порядке является линейной. Список, с другой стороны, просто обеспечивает линейную итерацию и постоянное предварительное добавление, разложение в голове / хвосте.

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

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

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

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

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

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

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

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

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

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

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