简单循环太慢

Question

我不明白为什么下面的代码太慢了。这段代码的目标非常简单：我有一组点，我想将它们分成 6 个桶（因此每个桶 100000 个点）。代码：

import scala.collection.mutable.{Map, ListBuffer}
object Main {
  def main(args : Array[String]) = {
    val m : Map[String, ListBuffer[Double]] = Map()
    val labels = Array("1","2","3","4","5","6")
    val points = Array.fill(600000){0.0}
    var it = 0
    val t1 = System.currentTimeMillis
    for (i <- 0 until points.length) {
      if(it == labels.length-1) it = 0
      val point = points(i)
      val currentLabel = labels(it)
      val values = m.getOrElse(currentLabel, ListBuffer())
      m += (currentLabel -> (values :+ point))
      it += 1
      println("it -> = " + it)

    }
    val t2 = System.currentTimeMillis
    println("fill values in = " +  (t2-t1) + " msecs")
  }
}

访问列表缓冲区上的映射和追加需要固定时间，所以对我来说，这段代码的复杂度为 O(n)，其中 n 是要拆分的点数。我可以提出一些建议来使这段代码更快吗？

Answer 1

正如@Noah 在评论中正确注意到的那样，您不必将缓冲区推回地图。这应该足够了：

val values = m.getOrElseUpdate(currentLabel, ListBuffer())
values += point

或者您可以使用函数式方法来完成，如果您使用 Scala，建议这样做：

val labels = Array("1","2","3","4","5","6")
val points = Array.fill(60000){2.0}
val t1 = System.currentTimeMillis
val m = points.zipWithIndex.groupBy {
  case (point, i) => labels(i % labels.size)
}.mapValues(arr => arr.map(_._1).toList)

val t2 = System.currentTimeMillis
println(m)
println("fill values in = " +  (t2-t1) + " msecs")

请注意 - 这里没有可变数据结构

Answer 2

以下重构不会导致创建与点一样多的集合，并且依赖于 Scala API、

object Main {
  def main(args : Array[String]) = {
    val labels = Array("1","2","3","4","5","6")
    val points = Array.fill(600000){0.0}

    val t1 = System.currentTimeMillis
    val xst = points.grouped(labels.size).toArray.transpose
    val m = (labels zip xst).toMap
    val t2 = System.currentTimeMillis

    println("fill values in = " +  (t2-t1) + " msecs")
  }
}

虽然原始代码需要几分钟，但这个代码需要大约 700 毫秒。

此代码避免了索引引用和更新现有集合。

用我填满内存的代码更新(Alifirat)

object Main {
  def main(args : Array[String]) = {
    val labels = Array("1","2","3","4","5","6", "7")
    val points = Array.fill(7000000){0.0}

    val t1 = System.currentTimeMillis
    val xst = points.grouped(labels.size).toArray.transpose
    val m = (labels zip xst).toMap
    val t2 = System.currentTimeMillis

    println("fill values in = " +  (t2-t1) + " msecs")
  }
}

相同的代码，但运行 7 个桶的 7 000 000 个点。

更新

尝试

scala -J-Xmx4g

然后粘贴更新后的代码。

更新

如果最终映射映射到 0.0 的数组上，以下证明在 7000 万个点上速度相当快，

val m = labels.map(l => l -> Array.fill(10*1000*1000){0.0}).toMap

如果性能是必不可少的，我已经建议的面向 C 的方法证明了内存和时间效率，可能以可伸缩性和组合性为代价。

Answer 3

给猫剥皮的另一种方法：

val buckets = Array.fill(labels.length)(ArrayBuffer.empty[Double])
points.zipWithIndex.foreach{case(p, i) => buckets(i%labels.length) += p}
(labels zip buckets).toMap

我没有正确地对其进行基准测试，但这是我尝试过的最快的方法（不再是 - 请参阅我的其他答案）

Answer 4

有时正确的方法是改变函数式风格。我用 c 风格的 Scala 编写了一个解决方案。

def main(args : Array[String]) = {
val labels = Array("1","2","3","4","5","6")
val points = Array.fill(600000){0.0}


val numChannels=6;
val channels=new Array[Array[Double]](numChannels);
for(i<-0 until numChannels){
  channels(i)=new Array[Double]((points.length/6));
}

var from=0;

val t1 = System.currentTimeMillis

for(i<-0 until numChannels){
  val channel=channels(i);
  from=i
  var to=0;
  try{
    while(true){
      channel(to)=points(from);
      to=to+1;
      from=from+numChannels;
    }
  } catch {
    case e:ArrayIndexOutOfBoundsException =>{
      //Ok finished this channel
    }
  }
}

val t2 = System.currentTimeMillis

println("fill values in = " +  (t2-t1) + " msecs")
println("from:"+from)
}

此解决方案仅完成需要完成的工作，仅此而已。

在我的机器上它使用 8 毫秒。
Elm 的代码使用 309 毫秒。
原来用了 221226 毫秒。

虽然我喜欢 Scala，但重要的是要记住它擅长隐藏其操作的计算成本。大多数对集合的操作都会为每个元素引入至少几个过程调用。

Answer 5

这里（作为一个单独的答案，因为它与我的第一个答案完全不同）是另一个 "C style"，它确实处理可变数量的桶。

有趣的是，在我的机器上，它的速度大约是 Espen Brekke 的其他 C 风格答案的两倍。更新：我收回这一点——两者都运行太快了，实际执行时间被启动时间等掩盖了。运行在100倍的点数（60000000）上，Espen的速度大约是两倍（但是有固定数量的桶） - 大约 220 毫秒与大约 420 毫秒相比

更新 2：Espen 的最新版本现在或多或少与下面相同（除了使用异常而不是显式边界检查），并且毫不奇怪，运行速度相似。

另请注意，这两个版本都没有计算存储桶数组的创建时间。在我的机器上，这大约是另外 200 毫秒（对于任一版本），所以大约 50%-100% 的时间将东西放入桶中...

因此，这个变体比 OP 的原始代码（在我的机器上）快大约 100,000 倍！

object buckets2 extends App {

 val labels = Array("1","2","3","4","5","6")
val points = Array.fill(600000){0.0}

val count = 6
val bucket_size = ((points.length-1)/count) + 1 

val buckets = Array.fill(count) (new Array[Double](bucket_size));

var b = 0
val t1 = System.currentTimeMillis

while (b < count) {
  var i = b
  var j  = 0
  val this_bucket = buckets(b)
  while (i < points.length) {
    this_bucket(j) =  points(i)
    i = i + count
    j = j + 1
  }
  b = b + 1

}

val t2 = System.currentTimeMillis

println("fill values in = " +  (t2-t1) + " msecs")

}

简单循环太慢

Simple loop is too slow

algorithm

complexity-theory

scala