斯卡拉Seq vs列表性能

所以我有點困惑。我在Scala中有一段代碼（確切的代碼並不是那麼重要）。我已經將所有的方法寫入Seq [T]。這些方法大多是尾遞歸，並使用Seq [T]作爲最初像Seq（）那樣饋入的累加器。有趣的是，當我將所有簽名與具體的List（）實現進行交換時，我觀察到性能提高了三倍。斯卡拉Seq vs列表性能

Seq的默認實現實際上是不可變的List嗎？所以如果是這樣的話，究竟發生了什麼？

來源

2017-03-21 Zahari

你有一些代碼可以證明這一點嗎？ – puhlen

'Seq'的默認實現實際上是一個'ArrayBuffer'，而不是'List'。你使用的用例實際上是爲'List'量身定做的，因爲它們是以尾遞歸方式實現的。 –

這會導致如此巨大的性能差異嗎？ – Zahari

調用Seq(1,2,3)和調用List(1,2,3)都將導致1 :: 2 :: 3 :: Nil。該Seq.apply方法只是一個非常普通的方法是這樣的：

def apply[A](elems: A*): CC[A] = { 
    if (elems.isEmpty) empty[A] 
    else { 
    val b = newBuilder[A] 
    b ++= elems 
    b.result() 
    } 
}

newBuilder是事之類的問題在這裏。 That method委託給scala.collection.immutable.Seq.newBuilder：

def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer

所以Builder的Seq是mutable.ListBuffer。甲Seq被通過附加的元素爲空ListBuffer然後調用result就可以了，這是這樣實現的構造：

def result: List[A] = toList 

/** Converts this buffer to a list. Takes constant time. The buffer is 
* copied lazily, the first time it is mutated. 
*/ 
override def toList: List[A] = { 
    exported = !isEmpty 
    start 
}

List還具有作爲ListBufferBuilder。它經歷了一個稍微不同但相似的構建過程。無論如何，這並不會產生太大的影響，因爲我認爲你的算法大部分都是將事件添加到Seq，而不是全程調用Seq.apply(...)。即使你做了，也不應該有太大的區別。

如果沒有看到具有該行爲的代碼，就無法說出導致您所看到的行爲的原因。

來源

2017-03-22 13:44:48

根據你的假設，Seq.apply只是一個List，並沒有太大的區別，你實際上可以做這樣的事情，對吧： val序列：LinearSeq [_] = Seq（）這應該相應地工作，因爲Seq是List並且List使用LinearSeq特徵。但它不起作用，因此，如何構造序列非常重要，特別是如果您需要高效的尾部訪問或尾部遞歸操作（即對序列執行迭代的方法）時。 –

否.Seq（）'返回一個'List'，但它的靜態'返回類型'是'Seq'。這就是爲什麼你不能將它分配給'LinearSeq'類型的變量。評估'Seq（1）.getClass'並看看你得到了什麼。 –

但是要明確我同意，如果你想要List的性能特徵，最好使用'List'。 –

斯卡拉Seq vs列表性能

回答

相關問題