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 后的猜测-Xprint:all是，在示例中 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示例更直接，它检查列表是否为空（两次比较），如果不是则返回 a Some(head)，然后将它的_1and_2分配给thingand stuff。所以没有迭代器被创建，集合的长度也没有线性关系。

于 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几乎相同。

方法head，tail并dequeue可能导致reverce内部List的Queue（与成本O(n)）。在您的两个代码示例中，最多会有 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)
于 2013-07-31T04:25:26.853 回答
0

_*用于指定 varargs 参数，因此您在第一个版本中所做的是将 Queue 解构为一对字符串，以及适当数量的其他字符串对 - 即您正在解构整个 Queue 即使您只关心第一个元素。

如果你只是删除星号，给

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

那么您只是将队列解构为一对字符串和一个余数（因此不需要完全解构）。这应该在与您的第二个版本相当的时间内运行（虽然我自己没有计时）。

于 2013-07-31T04:00:10.373 回答