Есть или будет коллекция Scala, расширяющая Seq с более быстрой итерацией, чем Array?

Question

Из того, что я тестировал, и чтение , Array - самая быстрая коллекция, когда речь идет о произвольном доступе или итерации через foreach, while и tailrec, но они изменчивыв отличие от Vector, который, к сожалению, не так быстр, как Array.

Я все еще застрял на Scala 2.11, но недавно я обнаружил, что в Scala 2.13 были внесены изменения.Есть ли надежда, что существует или будет существовать неизменная коллекция, которая превосходит Array в плане произвольного доступа?

Вот пример евклидова расстояния на Array[Double], он работает точно так же на потомках Seq.

    final def euclidean(v1: Array[Double], v2: Array[Double]): Double = {
      @annotation.tailrec
      def go(d: Double, i: Int): Double = {
        if(i < v1.size) { 
          val toPow2 = v1(i) - v2(i)
          go(d + toPow2 * toPow2, i + 1)
        }
        else d
      }
      sqrt(go(0D, 0))
    }

Answer 1

В общем, я не думаю, что можно превзойти Array с точки зрения произвольного доступа в JVM.Поскольку элементы массива имеют одинаковый размер и они расположены последовательно в памяти, положение элемента может быть быстро вычислено в постоянное время с использованием данного индекса.Более того, это приводит к хорошей локализации кэша.

В лучшем случае коллекция может иметь производительность произвольного доступа наравне с массивами.Взглянув на источники Scala 2.11 для упомянутого ArraySeq, он говорит:

Это означает, что элементы * примитивных типов заключены в квадрат.

https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/ArraySeq.scala#L19

Это, скорее всего, объясняет наблюдаемое 10% падение производительности.Массивы имеют метод toSeq, который реализован как WrappedArray, и для каждого примитивного типа есть специализированная реализация, которая, как я считаю, является наиболее производительной коллекцией в scala 2.11 для обёртывания массива https://github.com/scala/scala/blob/2.11.x/src/library/scala/collection/mutable/WrappedArray.scala#L173.