如何使用范围编写高效的嵌套循环

Question

作为一名scala新手，我试图编写一个在一些二维数据上运行的方法。此方法被调用多次，因此性能很重要。

首先我用编码

private def sumWithRange(xEnd: Int, yEnd: Int) = {
var sum = 0
for {
x <- 0 until xEnd
y <- 0 until yEnd
} sum += 1
sum
}

然后使用while循环：

private def sumWithWhileLoop(xEnd: Int, yEnd: Int) = {
var sum = 0
var x = 0
while (x < xEnd) {
var y = 0
while (y < yEnd) {
sum += 1
y += 1
}
x += 1
}
sum
}

我很惊讶范围理解运行得如此缓慢，所以我写了一个ScalaMeter基准：

object TestDoubleLoopPerformance {
val standardConfig = config(
Key.exec.minWarmupRuns -> 5,
Key.exec.maxWarmupRuns -> 10,
Key.exec.benchRuns -> 10,
// Key.verbose -> true
) withWarmer(new Warmer.Default)

def main(args: Array[String]): Unit = {
val whileLoopTime = standardConfig measure {
for (iter <- 0 to 1000) {
sumWithWhileLoop(1000, 2000)
}
}
println(s"while loop time: $whileLoopTime")
val rangeLoopTime = standardConfig measure {
for (iter <- 0 to 1000) {
sumWithRange(1000, 2000)
}
}
println(s"range loop time: $rangeLoopTime")
}
}

结果：

while loop time: 0.3065984 ms
range loop time: 2585.5892847 ms

此外，通过详细的输出，为for compensation版本报告了多个GC。

我意识到，对于每个x，都会创建新的Range，这解释了的迟缓

有没有一种方法可以修改for composition版本以更快地运行(与while循环相当(？

//编辑：我试着去理解：

var sum = 0
(0 until xEnd).foreach(x => {
val yRange = 0 until yEnd
yRange.foreach(y => sum += 1)
})

然后拉起yRange:

var sum = 0
val yRange = 0 until yEnd
(0 until xEnd).foreach(x => {
yRange.foreach(y => sum += 1)
})

据报道，它的运行时间约为287毫秒，比以前好得多，但仍不令人满意

Answer 1

在我的一个相当简单的例子中，我用自己的Range2D类解决了这个问题

class Range2D(a0: Int, a1: Int) {
def foreach(f: ((Int, Int)) => Unit): Unit = {
var i0 = 0
while (i0 < a0) {
var i1 = 0
while (i1 < a1) {
f(i0, i1)
i1 += 1
}
i0 += 1
}
}
}

和

private def sumWithRange(xEnd: Int, yEnd: Int) = {
var sum = 0
for {
xy <- new Range2D(xEnd, yEnd)
} sum += 1
sum
}

在我的机器上，它比原始循环慢大约10倍，这比我最初的代码有了很大的改进。

编辑

我尝试将Function1[(Int, Int), Unit]更改为Function2[Int, Int, Unit]

• 我无法在中使用Range2D进行理解(我得到missing parameter type错误(
• 我可以使用foreach：new Range2D(xEnd, yEnd).foreach((_, _) => sum += 1)
• 我的机器差别不大
• 生成的代码确实看起来更好-没有创建Tuple2：

原始Range2D(反编译为java(

private int sumWithRange(final int xEnd, final int yEnd) {
IntRef sum = IntRef.create(0);
(new Range2D(xEnd, yEnd)).foreach((xy) -> {
$anonfun$sumWithRange$1(sum, xy);
return BoxedUnit.UNIT;
});
return sum.elem;
}

修改的Range2D(反编译为java(

private int sumWithRange(final int xEnd, final int yEnd) {
IntRef sum = IntRef.create(0);
(new Range2D(xEnd, yEnd)).foreach((x$1, x$2) -> {
++sum.elem;
});
return sum.elem;
}