爲什麼headOption更快

Question

我對某些代碼進行了更改，它的速度提高了4.5倍。我想知道爲什麼。它曾經是本質：

def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue match { 
    case Queue((thing, stuff), _*) => doThing(queue.tail) 
    case _ => queue 
} 

，我把它改成這個獲得巨大的速度提升：

def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue.headOption match { 
    case Some((thing, stuff)) => doThing(queue.tail) 
    case _ => queue 
} 

是什麼_*做，爲什麼它如此昂貴相比headOption？

Answer 1

與-Xprint:all運行scalac後，我的猜測是，在patmat在queue match { case Queue((thing, stuff), _*) => doThing(queue.tail) }例子結束時，我看到被調用下面的方法（編輯爲簡潔起見）：

val o9 = scala.collection.immutable.Queue.unapplySeq[(String, String)](x1); 
if (o9.isEmpty.unary_!) 
    if (o9.get.!=(null).&&(o9.get.lengthCompare(1).>=(0))) 
    { 
     val p2: (String, String) = o9.get.apply(0); 
     val p3: Seq[(String, String)] = o9.get.drop(1); 

所以lengthCompare比較集的長度在一個可能是最優化的方式。對於Queue，它創建一個迭代器並迭代一次。所以這應該有點快。另一方面，drop(1)也構造一個迭代器，跳過一個元素並將其餘元素添加到結果隊列中，以便在集合的大小上是線性的。

的headOption例子是更直接的，它會檢查是否該列表是空的（兩個比較），並且如果沒有返回一個Some(head)，然後只有其_1和_2分配給thing和stuff。所以沒有創建迭代器，並且集合的長度沒有任何線性。

Answer 2

_*用於指定可變參數參數，因此您在第一個版本中所做的是將隊列解構爲一對字符串以及適當數量的其他字符串 - 即使您正在解構整個隊列你只關心第一個元素。

如果你只是刪除了星號，給

def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = queue match { 
    case Queue((thing, stuff), _) => doThing(queue.tail) 
    case _ => queue 
} 

那麼你只解構隊列進入一對字符串，和餘數（這因此並不需要完全解構）。這應該在與第二個版本相當的時間內運行（儘管我自己也沒有計時）。

Answer 3

代碼示例之間應該沒有顯着差異。

case Queue((thing, stuff), _*)實際上是由編譯器翻譯來調用head（apply(0)）的方法。你可以使用scalac -Xprint:patmat對此展開調查：

<synthetic> val p2: (String, String) = o9.get.apply(0); 
if (p2.ne(null)) 
    matchEnd6(doThing(queue.tail)) 

的head的成本和費用headOption幾乎相同。

方法head，tail和dequeue可以在（與成本O(n)）內部Queue的List導致reverce。在這兩個代碼示例中，最多隻能有2個reverce調用。 你應該使用dequeue這樣獲得至多一個單一reverce電話：

def doThing(queue: Queue[(String, String)]): Queue[(String, String)] = 
    if (queue.isEmpty) queue 
    else queue.dequeue match { 
    case (e, q) => doThing(q) 
    } 

你也可以用_取代(thing, stuff)。在這種情況下，編譯器將生成唯一的lengthCompare呼叫而不head或tail：

if (o9.get != null && o9.get.lengthCompare(1) >= 0)