Некоторые из приведенных здесь утверждений сбивают с толку или даже ошибочны, особенно идея о том, что 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 элементов одновременно, когда вы создаете его с помощью компоновщика, вместо того, чтобы добавлять или добавлять элементы один за другим).Конечно, все операции, которые занимают линейное время в списках, но фактически постоянное время для векторов (как произвольный доступ или добавление), будут чрезмерно медленными в больших списках.
Так какую структуру данных мы должны использовать?По сути, существует четыре распространенных случая:
- Нам нужно преобразовывать последовательности только с помощью таких операций, как отображение, фильтрация, свертывание и т. Д. В принципе это не имеет значения, мы должны программировать наш алгоритм в общем и даже выиграть отпринимая параллельные последовательности.Для последовательных операций List, вероятно, немного быстрее.Но вы должны сравнить его, если вам нужно оптимизировать.
- Нам нужно много произвольного доступа и разных обновлений, поэтому мы должны использовать вектор, список будет слишком медленным.
- Мы работаем со спискамиклассическим функциональным способом, построение их путем добавления и итерации с помощью рекурсивной декомпозиции: используйте список, вектор будет медленнее в 10-100 и более раз.
- У нас есть алгоритм, критичный к производительности, который в основном необходим и делаетмного произвольного доступа к списку, что-то вроде быстрой сортировки на месте: используйте императивную структуру данных, например, ArrayBuffer, локально и копируйте свои данные с и на него.