Scala 列表拼接比较

23 浏览
0 Comments

Scala 列表拼接比较

在scala中，有两种列表连接的方法：:::和++。

例如，有三个列表-x，y，z。我听说x ::: y ::: z比x ++ y ++ z快，因为:::是右结合的。x ::: y ::: z被解析为x ::: (y ::: z)。

我的问题如下：

  1. 上面的说法是否正确？
  2. :::和++的时间复杂度是什么？
admin 更改状态以发布 2023年5月22日
0

1 答案

0 Comments

上面的说法正确吗？

不是，两者都需要O(n)的时间来连接列表。:::是右结合的，它会先连接y和z，然后再连接x（x ::: (y ::: z))，而++会先连接x和y，然后再连接z（(x ++ y) ++ z）。

:::和++的时间复杂度是多少？

O(n)。具体来说，对于List[A]上的++，如果我们连接两个列表，它会在内部优化为使用:::。

override def ++[B >: A, That](that: GenTraversableOnce[B])
                             (implicit bf: CanBuildFrom[List[A], B, That]): That =
  if (bf eq List.ReusableCBF) (this ::: that.seq.toList).asInstanceOf[That]
  else super.++(that)

0