5

一部のコードを変更したところ、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 と比べてそれほど高価なのですか?

4

3 に答える 3

4

scalac を実行した後の私の推測では、例のpatmat-Xprint:allの最後に、次のメソッドが呼び出されていることがわかります (簡潔にするために編集されています)。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、イテレータを作成し、1 回繰り返します。そのため、多少高速になるはずです。一方drop(1)、イテレータも構築し、1 つの要素をスキップして残りの要素を結果キューに追加するため、コレクションのサイズは線形になります。

このheadOption例はより単純で、リストが空かどうかをチェックし (2 回の比較)、そうでない場合はを返しSome(head)ます。そのため、イテレータは作成されず、コレクションの長さは直線的ではありません。_1_2thingstuff

于 2013-07-31T05:01:16.277 に答える
2

コード サンプル間に大きな違いはないはずです。

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はほぼ同じです。

Methods head、tailおよび内部で発生するdequeue可能性があります ( with cost )。どちらのコード サンプルでも、呼び出しは最大で 2 回です。せいぜい単一の呼び出しを取得するには、次のように使用する必要があります。reverceListQueueO(n)revercedequeuereverce

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

(thing, stuff)に置き換えることもできます_。この場合、コンパイラはorlengthCompareなしの呼び出しのみを生成します。headtail

if (o9.get != null && o9.get.lengthCompare(1) >= 0)
于 2013-07-31T04:25:26.853 に答える
0

_*varargs 引数を指定するために使用されるため、最初のバージョンで行っていることは、Queue を文字列のペアに分解し、さらに適切な数の文字列のペアを分解することです。最初の要素。

アスタリスクを削除するだけで、

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

次に、キューを文字列のペアと残りに分解するだけです（したがって、完全に分解する必要はありません）。これは、2 番目のバージョンと同等の時間で実行されるはずです (ただし、自分で時間を測定していません)。

于 2013-07-31T04:00:10.373 に答える