将 scala 集合从一种类型转换为另一种类型的复杂性是什么?

Question

我想知道转换 scala 集合操作的复杂性，如下所示：

List.fill(n)(1).toArray
Array.fill(n)(1).toList
ArrayBuffer( Array.fill(n)(1):_* )

我想对于这些示例，我们需要遍历所有元素，因此它将是 O(n(，不幸的是我不知道这些转换下的子例程，因此可以优化复杂性。

不要犹豫，为其他类型的 scala 转换增加复杂性。

Answer 1

我快速浏览了源代码，它们似乎都像你想象的那样是O(n(。

例如，子例程copyToArray(由toArray使用(：

override /*TraversableLike*/ def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
  var i = start
  val end = (start + len) min xs.length
  val it = iterator
  while (i < end && it.hasNext) {
    xs(i) = it.next()
    i += 1
  }
}

源

如您所见，它只是线性迭代集合。