Scala: индексирование изменчивых коллекций быстрее, чем неизменяемо?

Question

В настоящее время я ищу тип коллекции в Scala, который будет самым быстрым для запроса по индексу - значение, если x - это моя коллекция, я хочу, чтобы она имела самую быструю возможную производительность для поиска x(i) для любого индекса i. Кроме того, x не может быть изменен во время выполнения.

Глядя в Scala Collections Performance Characteristics, кажется, что лучшее исполнение O (1) приведены в Java Array, mutable.ArrayBuffer и mutable.ArraySeq (в String и Range не являются полезными в моем случае). Это удивительно, поскольку я ожидал, что неизменные коллекции будут быстрее, поскольку они поддерживают меньшую функциональность. Наилучшая производительность неизменной коллекции дается Vector с O (~ 1), которая, насколько я понимаю, не лучше, чем O (1).

Я что-то теряю, или меняются коллекции, которые имеют лучшую производительность поиска?

Answer 1

Scala не имеет неизменяемого массива, а массив - это структура с наилучшим возможным доступом к случайному индексу. Если бы существовал неизменяемый массив, он имел бы ту же производительность, что и измененная версия.

Речь идет не о mutable vs immutable, а о используемых структурах данных.