簡單循環太慢

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

這裏（作爲一個單獨的答案，因爲它與我的第一個答案完全不同）是另一個「C風格」，它處理可變數量的桶。

有趣的是，在我的機器上，它比Espen Brekke的其他C式回答快兩倍。更新：我回過頭來看 - 兩者運行速度非常快，實際執行時間被啓動時間等所掩蓋。運行在100x的點數（60000000）上，Espen的速度是其兩倍（但是具有固定數量的存儲桶） - 大約220ms相比，大約420ms

更新2：Espen的最新現在或多或少像下面一樣（除了使用異常而不是明確的邊界檢查）並且毫不奇怪，以相似的速度運行。

另請注意，這兩個版本都不會創建存儲桶陣列。在我的機器上，這大約是另一個200毫秒（對於任一版本），因此大約有50％-100％的時間需要將東西放入桶中......

因此，此變體比OP的原始代碼（在我的機器上）！

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

} 

Answer 2

由於@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 3

下重構不創造儘可能多的藏品爲點承擔，並依賴於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 000 000分，連續7桶運行的代碼。

更新

嘗試

scala -J-Xmx4g 

然後粘貼更新的代碼。

更新

如若最終地圖上的0.0陣列，下面的證明開70μm萬點相當快，

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

在情況下的性能是必不可少的，C爲導向的方法前面已經建議我證明自己的記憶和時間有效率，可能會犧牲可擴展性和組合性。

Answer 4

剝皮貓的另一種方式：

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 5

有時正確的做法是改變功能風格。 我已經寫了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) 
} 

該解決方案只處理需要完成的工作，不再需要處理。

在我的mashine上它使用8毫秒。
elm的代碼使用309毫秒。
原來花了221226毫秒。

雖然我愛Scala，但重要的是要記住它很好地隱藏了其操作的計算成本。對集合的大多數操作至少引入了每個元素的幾個過程調用。