Простая петля слишком медленная

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 (п), где п числа точек, чтобы разделить. Могу ли я получить некоторые советы, чтобы сделать этот код намного быстрее?

Answer 1

Здесь (как отдельный ответ, так как он сильно отличается от моего первого ответа) - это еще один «C-стиль», который обрабатывает переменное количество ведер.

Интересно, что на моей машине это примерно в два раза быстрее, чем в другом ответе C-стиля от Espen Brekke. ОБНОВЛЕНИЕ: я беру это обратно - оба выполнялись так быстро, что фактическое время выполнения было замаскировано временем запуска и т. Д. Запуск на 100x по количеству точек (60000000), Espen примерно в два раза быстрее (но имеет фиксированное количество ковшей) - около 220 мс по сравнению с примерно 420 мс

UPDATE2: последняя версия Espen в настоящее время более или менее такая же, как и ниже (за исключением использования исключения вместо явной проверки границ) и, что не удивительно, работает с одинаковой скоростью.

Также обратите внимание, что ни одна версия не создает массивы ковша. На моей машине это примерно еще 200 мс (для любой версии), поэтому примерно 50% -100% времени, затрачиваемого на то, чтобы положить вещи в ведра ...

Этот вариант, следовательно, примерно в 100 000 раз быстрее, чем исходный код 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 

Или вы могли бы сделать это с функциональным подходом, который рекомендуется, если вы работаете с Скале:

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 мсек.

Этот код позволяет избежать индексирования ссылок и обновления существующих коллекций.

Update с кодом, который заполнит память (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 ведер.

Update

Попробуйте

scala -J-Xmx4g 

, а затем вставить обновленный код.

Update

В случае, если конечная карта карта на массивы 0.0 следующее оказывается довольно быстро на 70 миллионов точек,

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

Иногда правильный подход заключается в том, чтобы отказаться от функционального стиля. Я написал решение в стиле 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, важно помнить, что это хорошо скрывает вычислительную стоимость его операций. Большинство операций с коллекциями вводит по крайней мере пару вызовов процедур для каждого элемента.