algorithm - 简单循环太慢

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

以下重构不会导致创建与点一样多的集合，并且依赖于 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

然后粘贴更新的代码。

更新

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

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

在性能至关重要的情况下，我已经建议的面向 C 的方法证明了内存和时间效率，但可能会以可扩展性和组合性为代价。