时间戳

首页 > 解决方案 > 是否存在或将存在扩展 Seq 的 Scala 集合，其迭代速度比 Array 更快？

scala - 是否存在或将存在扩展 Seq 的 Scala 集合，其迭代速度比 Array 更快？

问题描述

根据我测试和阅读的内容，在通过、和Array进行随机访问或迭代时，它是最快的集合，但它们是可变的，不像，不幸的是，它不如.foreachwhiletailrecVectorArray

我仍然坚持使用 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))
    }

标签： scalaperformancecollections

解决方案

总的来说，我认为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作为 a 实现的方法，WrappedArray并且每种原始类型都有专门的实现，我认为这是 scala 2.11 中用于包装数组的性能最高的集合https://github.com/scala/scala/blob/2.11.x/ src/library/scala/collection/mutable/WrappedArray.scala#L173。

推荐阅读