Когда я должен выбрать Vector в Scala?
Кажется, что Vector опоздал на вечеринку коллекций Scala, и все влиятельные посты в блоге уже ушли.
На яве ArrayList это коллекция по умолчанию - я мог бы использовать LinkedList но только когда я продумал алгоритм и позаботился об оптимизации. В Scala я должен использовать Vector как мой по умолчанию Seqили пытаясь решить, когда List на самом деле более уместно?
6 ответов
Как правило, по умолчанию используется Vector, Это быстрее чем List почти для всего и более эффективно для памяти для последовательностей большего размера, чем тривиальный. См. Эту документацию относительно производительности Вектор по сравнению с другими коллекциями. Есть некоторые недостатки, чтобы идти с Vector, В частности:
- Обновления в голове медленнее, чем
List(хотя и не так сильно, как вы думаете)
Еще одним недостатком до Scala 2.10 было то, что поддержка сопоставления с образцом была лучше для List, но это было исправлено в 2.10 с обобщением +: а также :+ экстракторы.
Существует также более абстрактный, алгебраический подход к этому вопросу: какая последовательность у вас концептуально? Кроме того, что ты концептуально делаешь с этим? Если я вижу функцию, которая возвращает 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 или LinearSeq, которые дают разные гарантии для производительности. IndexedSeq обеспечивает быстрый произвольный доступ к элементам и быструю операцию длины. LinearSeq обеспечивает быстрый доступ только к первому элементу через head, но также имеет быстрый tail операция. (Взято из документации Seq.)
Для IndexedSeq вы обычно выбираете Vector, Rangeс и WrappedStrings также IndexedSeqs.
Для LinearSeq вы обычно выбираете List или его ленивый эквивалент Stream, Другие примеры Queueс и Stacks.
Так что в терминах Java, ArrayList используется аналогично Scala's Vector, а также LinkedList подобно скале List, Но в Scala я бы предпочел использовать List чаще, чем Vector, потому что Scala имеет гораздо лучшую поддержку функций, которые включают обход последовательности, таких как отображение, свертывание, итерации и т. Д. Вы будете склонны использовать эти функции для управления списком как в целом, а не случайный доступ к отдельным элементам.
В ситуациях, которые включают много случайного доступа и случайных мутаций, Vector (или - как говорят документы - SeqКажется, хороший компромисс. Это также то, что показывают характеристики производительности.
Так же Vector Кажется, класс хорошо работает в распределенных средах без большого дублирования данных, потому что нет необходимости выполнять копирование при записи для всего объекта. (См.: http://akka.io/docs/akka/1.1.3/scala/stm.html)
Если вы постоянно программируете и нуждаетесь в произвольном доступе, Seq - это то, что вам нужно (если вы не хотите использовать Set, который вы часто делаете). В противном случае список работает хорошо, за исключением того, что его операции нельзя распараллелить.
Если вам не нужны неизменяемые структуры данных, используйте ArrayBuffer, поскольку это Scala-эквивалент ArrayList.