14

最近我接受了 Scala 开发人员职位的面试。我被问到这样的问题

// matrix 100x100 (content unimportant)

val matrix = Seq.tabulate(100, 100) { case (x, y) => x + y }

// A

for {

   row <- matrix

   elem <- row

} print(elem)

// B

val func = print _
for {

   row <- matrix

   elem <- row

} func(elem)

问题是：A 或 B 哪个实现更有效？

我们都知道for 推导式可以翻译成

// A

matrix.foreach(row => row.foreach(elem => print(elem)))

// B

matrix.foreach(row => row.foreach(func))

B 可以写成matrix.foreach(row => row.foreach(print _))

假设正确答案是 B，因为 A 将创建print100 倍的函数。

我检查了语言规范，但仍然无法理解答案。有人可以向我解释一下吗？

4

3 回答 3

8

简而言之：

示例 A 在理论上更快，但实际上您应该无法测量任何差异。

长答案：

正如你已经发现的

for {xs <- xxs; x <- xs} f(x)

被翻译成

xxs.foreach(xs => xs.foreach(x => f(x)))

这在 §6.19 SLS 中有解释：

一个 for 循环

for ( p <- e; p' <- e' ... ) e''

其中 ... 是生成器、定义或守卫的（可能为空）序列，被转换为

e .foreach { case p => for ( p' <- e' ... ) e'' }

现在，当人们编写函数文字时，每次需要调用函数时都会获得一个新实例（第 6.23 节 SLS）。这意味着

xs.foreach(x => f(x))

相当于

xs.foreach(new scala.Function1 { def apply(x: T) = f(x)})

引入局部函数类型时

val g = f _; xxs.foreach(xs => xs.foreach(x => g(x)))

您没有引入优化，因为您仍然将函数文字传递给foreach. 实际上代码比较慢，因为内部foreach被翻译成

xs.foreach(new scala.Function1 { def apply(x: T) = g.apply(x) })

apply发生对方法的额外调用的地方g。不过，您可以在编写时进行优化

val g = f _; xxs.foreach(xs => xs.foreach(g))

因为foreach现在的内部被翻译成

xs.foreach(g())

这意味着函数g本身被传递给foreach.

这意味着 B 在理论上更快，因为每次执行 for 理解的主体时都不需要创建匿名函数。但是，上面提到的优化（函数直接传递给foreach）不适用于理解，因为正如规范所说，翻译包括函数文字的创建，因此总是会创建不必要的函数对象（在这里我必须说编译器也可以优化它，但它不会因为对理解的优化很困难并且在 2.11 中仍然没有发生）。总而言之，这意味着 A 更有效，但如果 B 在没有 for 理解的情况下编写（并且没有为最里面的函数创建函数字面量），则 B 会更有效。

尽管如此，所有这些规则都只能在理论上应用，因为实际上有 scalac 的后端和 JVM 本身都可以进行优化 - 更不用说由 CPU 完成的优化了。此外，您的示例包含在每次迭代时执行的系统调用 - 它可能是这里最昂贵的操作，它超过了其他所有操作。

于 2014-05-19T14:48:17.393 回答
2

我同意sschaef并说这A是更有效的选择。

查看生成的类文件，我们得到以下匿名函数及其应用方法：

MethodA:
  anonfun$2            -- row => row.foreach(new anonfun$2$$anonfun$1)
  anonfun$2$$anonfun$1 -- elem => print(elem)

IEmatrix.foreach(row => row.foreach(elem => print(elem)))

MethodB:
  anonfun$3            -- x => print(x)
  anonfun$4            -- row => row.foreach(new anonfun$4$$anonfun$2)
  anonfun$4$$anonfun$2 -- elem => func(elem)

即matrix.foreach(row => row.foreach(elem => func(elem))) wherefunc只是调用 to 之前的另一个间接方式print。此外还func需要查找，即通过this.func()对每行的实例 ( ) 的方法调用。

所以对于方法 B，创建了 1 个额外的对象 ( func) 并且有# of elem额外的函数调用。

最有效的选择是

matrix.foreach(row => row.foreach(func))

因为它创建的对象数量最少，并且完全符合您的预期。

于 2014-05-19T15:30:49.233 回答
2

基准

概括

方法 A 比方法 B 快近 30%。

代码链接：https ://gist.github.com/ziggystar/490f693bc39d1396ef8d

实施细节

我添加了方法 C（两个 while 循环）和 D（折叠、求和）。我还增加了矩阵的大小并使用了一个IndexedSeq。我也print用不那么重的东西（总和所有条目）替换了。

奇怪的是，while构造并不是最快的。但是，如果一个人使用它Array而不是IndexedSeq它，那么它就会以很大的优势成为最快的（因子 5，不再装箱了）。使用显式装箱整数，方法 A、B、C 都同样快。特别是与 A、B 的隐式装箱版本相比，它们快了 50%。

结果

A
4.907797735
4.369745787
4.375195012000001
4.7421321800000005
4.35150636
B
5.955951859000001
5.925475619
5.939570085000001
5.955592247
5.939672226000001
C
5.991946029
5.960122757000001
5.970733164
6.025532582
6.04999499
D
9.278486201
9.265983922
9.228320372
9.255641645
9.22281905
verify results
999000000
999000000
999000000
999000000

>$ scala -version
Scala code runner version 2.11.0 -- Copyright 2002-2013, LAMP/EPFL

代码摘录

val matrix = IndexedSeq.tabulate(1000, 1000) { case (x, y) => x + y }

def variantA(): Int = {
  var r = 0
  for {
    row <- matrix
    elem <- row
  }{
    r += elem
  }
  r
}

def variantB(): Int = {
  var r = 0
  val f = (x:Int) => r += x
  for {
    row <- matrix
    elem <- row
  } f(elem)
  r
}

def variantC(): Int = {
  var r = 0
  var i1 = 0
  while(i1 < matrix.size){
    var i2 = 0
    val row = matrix(i1)
    while(i2 < row.size){
      r += row(i2)
      i2 += 1
    }
    i1 += 1
  }
  r
}

def variantD(): Int = matrix.foldLeft(0)(_ + _.sum)
于 2014-05-19T16:00:41.177 回答