用标量减去两个数组的最快方法是什么

Question

我有两个数组(我已经从矩阵(Array[Array[Int]])中取出)，我需要从另一个中减去一个。

然而，目前我正在使用这种方法，当我对其进行评测时，它是瓶颈。

def subRows(a: Array[Int], b: Array[Int], sizeHint: Int): Array[Int] = {
val l: Array[Int] = new Array(sizeHint)
var i = 0
while (i < sizeHint) {
l(i) = a(i) - b(i)
i += 1
}
l
}

我需要这样做数十亿次，所以速度的任何提高都是一个加分项。

我曾尝试使用List而不是Array来收集差异，速度快得多，但当我将其转换回Array时，我失去了所有好处。

我确实修改了下游代码，采用了List，看看这是否有帮助，但我需要无序访问列表的内容，因此再次失去了任何收益。

从一种类型到另一种类型的转换似乎都很昂贵，我想知道是否有一些方法可以更快地使用地图等。

有更好的方法吗？

---

编辑

不确定我第一次做了什么！？

所以我用来测试它的代码是这样的：

def subRowsArray(a: Array[Int], b: Array[Int], sizeHint: Int): Array[Int] = {
val l: Array[Int] = new Array(sizeHint)
var i = 0
while (i < sizeHint) {
l(i) = a(i) - b(i)
i += 1
}
l
}
def subRowsList(a: Array[Int], b: Array[Int], sizeHint: Int): List[Int] = {
var l: List[Int] = Nil
var i = 0
while (i < sizeHint) {
l = a(i) - b(i) :: l
i += 1
}
l
}
val a = Array.fill(100, 100)(scala.util.Random.nextInt(2))
val loops = 30000 * 10000
def runArray = for (i <- 1 to loops) subRowsArray(a(scala.util.Random.nextInt(100)), a(scala.util.Random.nextInt(100)), 100)
def runList = for (i <- 1 to loops) subRowsList(a(scala.util.Random.nextInt(100)), a(scala.util.Random.nextInt(100)), 100)
def optTimer(f: => Unit) = {
val s = System.currentTimeMillis
f
System.currentTimeMillis - s
}

我以为我第一次这样做时得到的结果正好相反。。。我一定看错了或者把方法弄混了。

我很抱歉问了一个糟糕的问题。

Answer 1

该代码是使用标准JVM管理单线程的最快代码。如果你认为List更快，你要么在自欺欺人，要么根本没有告诉我们你在做什么。将Int放入List需要创建两个对象：一个用于创建列表元素，另一个用于装箱整数。创建对象的时间大约是数组访问时间的10倍。因此，以任何其他方式做这件事都不是一个成功的提议。

如果你真的，真的需要更快，并且必须使用单个线程，你可能应该切换到C++或类似的东西，并显式地使用SSE指令。例如，请参阅此问题。

如果你真的、真的需要更快，并且可以使用多个线程，那么最简单的方法就是将这样的一块工作(即需要减去的合理数量的向量对——每个块可能至少有几百万个元素)打包到一个与你机器上的处理器数量一样长的列表中，然后调用list.par.map(yourSubtractionRoutineThatActsOnTheChunkOfWork)。

最后，如果你可以破坏，

a(i) -= b(i)

当然，内循环的速度更快。同样，如果你可以重用空间(例如使用System.arraycopy)，你会比继续分配空间更好。但这会改变你所展示的界面。

Answer 2

您可以使用Scalameter尝试对这两个实现进行基准测试，这两个实施至少需要运行JRE 7更新4和Scala 2.10。我使用了scala 2.10 RC2。

用scalac -cp scalameter_2.10-0.2.jar RangeBenchmark.scala编译。

使用scala -cp scalameter_2.10-0.2.jar:. RangeBenchmark运行。

这是我使用的代码：

import org.scalameter.api._
object RangeBenchmark extends PerformanceTest.Microbenchmark {
val limit = 100
val a = new Array[Int](limit)
val b = new Array[Int](limit)
val array: Array[Int] = new Array(limit)
var list: List[Int] = Nil
val ranges = for {
size <- Gen.single("size")(limit)
} yield 0 until size
measure method "subRowsArray" in {
using(ranges) curve("Range") in {
var i = 0
while (i < limit) {
array(i) = a(i) - b(i)
i += 1
}
r => array
}
}
measure method "subRowsList" in {
using(ranges) curve("Range") in {
var i = 0
while (i < limit) {
list = a(i) - b(i) :: list
i += 1
}
r => list
}
}
}

结果如下：

::Benchmark subRowsArray::
Parameters(size -> 100): 8.26E-4
::Benchmark subRowsList::
Parameters(size -> 100): 7.94E-4

你可以得出自己的结论

limit的值越大，堆栈就爆炸了。我想这是因为它多次衡量性能。