7

我有两个数组（我已经从矩阵中提取出来（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
 }

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

我曾尝试使用 aList而不是 anArray来收集差异，它要快得多，但是当我将它转换回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
}

我认为我第一次这样做时得到的结果完全相反......我一定是误读或混淆了方法。

我很抱歉问了一个不好的问题。

4

2 回答 2

6

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

如果你真的，真的需要更快，并且必须保持单线程，你可能应该切换到 C++ 或类似的，并明确使用 SSE 指令。例如，请参阅这个问题。

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

最后，如果你可以具有破坏性，

a(i) -= b(i)

在内循环中当然更快。同样，如果您可以重用空间（例如使用System.arraycopy），那么您比必须继续分配空间要好。但这会改变您所显示的界面。

于 2012-12-18T22:23:52.557 回答
1

您可以使用Scalameter对至少需要运行 JRE 7 update 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。我猜这是因为它多次测量性能。

于 2012-12-19T03:02:20.350 回答