简单循环太慢了

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")
  }
}

访问map和追加到列表缓冲区需要一个恒定的时间,所以对我来说,这段代码的复杂性是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

然后粘贴更新的代码.

更新

如果最终的地图映射到阵列上0.0,以下证明在7000万点上非常快,

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

如果性能是必不可少的,那么已经提出的面向C的方法证明了我的内存和时间效率,可能以牺牲可扩展性和组合性为代价.