13

特别是关于模式匹配和案例类。考虑以下：

abstract class Expr
case class Var(name: String) extends Expr
case class Number(num: Double) extends Expr
case class UnOp(operator: String, arg: Expr) extends Expr
case class BinOp(operator: String, left: Expr, right: Expr) extends Expr

object Expr {
  def simplify(expr: Expr): Expr = expr match {
    // Some basic simplification rules...
    case UnOp("-", UnOp("-", e)) => simplify(e) // Double negation
    case BinOp("+", e, Number(0)) => simplify(e) // Adding zero
    case BinOp("-", e, Number(0)) => simplify(e) // Subtracting zero
    case BinOp("*", e, Number(1)) => simplify(e) // Multiplying by one
    case BinOp("*", e, Number(0)) => Number(0) // Multiplying by zero
    case _ => expr // Default, could not simplify given above rules
  }
}

例如，给定任何示例调用simplify(UnOp("-", UnOp("-", UnOp("-", UnOp("-", Var("x"))))))（结果为Var("x")），匹配表达式中的替代顺序对性能有影响吗？

旁注，有点相关（我自己的观察）：真正让我印象深刻的一件事simplify是它是一个递归函数，尽管与我编写/处理的其他递归函数不同，基本情况排在最后是为了避免终止早期的。

4

3 回答 3

10

理论上是的，因为匹配测试是按顺序进行的。

但在实践中，差异可能并不显着。我已经使用 Caliper 和您的示例运行了一个微基准测试。我以Var("x")100'000为前缀Unop以使其更大。

结果是：

[info]  0% Scenario{vm=java, trial=0, benchmark=ForFirst} 240395.82 ns; σ=998.55 ns @ 3 trials
[info] 50% Scenario{vm=java, trial=0, benchmark=ForLast} 251303.52 ns; σ=2342.60 ns @ 5 trials
[info] 
[info] benchmark  us linear runtime
[info]  ForFirst 240 ============================
[info]   ForLast 251 ==============================

在第一个测试中，UnOp案例是第一个，在第二个测试中，它是最后一个（就在默认案例之前）。

如您所见，这并不重要（慢了不到 5%）。或许，在大量案例列表中，顺序很重要，但它也可能是重构的候选者。

完整代码在这里：https ://gist.github.com/1152232 （通过scala-benchmarking-template运行）。

于 2011-08-17T18:24:07.450 回答
9

像上面这样的匹配语句被翻译成字节码中的一堆 if 语句：

public Expr simplify(Expr);
  Code:
   0:   aload_1
   1:   astore_3
   2:   aload_3
   3:   instanceof  #17; //class UnOp
   6:   ifeq    110
   . . .

   110: aload_3
   111: instanceof  #35; //class BinOp
   114: ifeq    336
   . . .

So it's really equivalent to running a bunch of if-statements in order. So as with if-statements, putting commonly-encountered cases first can help. The compiler does a fairly good job at collapsing similar tests, but it's not perfect, so sometimes it works better to catch multiple cases (or even use nested if-statements) and have some sort of decision tree that you go down. Still, the compiler does do a fairly good job, so don't waste your time unless you know that this is the bottleneck.

于 2011-08-17T18:54:53.363 回答
0

When matching against types, the order IS crucial: the first type that matches will be used even if they are better matches (less generic) later. Hence the most specific type should come first and so on.

The second criteria to order your tests is to evaluate first the test the most likely to succeed, this way you reduce on average the number of tests that fail. Only the second criteria matters in you example.

于 2018-07-18T13:43:58.867 回答