Dlaczego Scala "dla pętli" jest tak bardzo powolna w porównaniu do pętli FOR?

Question

Mówi się, że Scala Dla zrozumienia są w rzeczywistości dość powolne. Podano mi, że ze względu na ograniczenie Java, dla zrozumienia (takiego jak "zmniejszenie", użytego poniżej), należy wygenerować tymczasowy obiekt z każdą iteracją, aby wywołać funkcję przekazaną.

IS .. .TA PRAWDA? Poniższe testy zdają się potwierdzać, ale nie do końca rozumiem, dlaczego tak się dzieje.

To może mieć sens dla „lambda” lub funkcji anonimowych, ale nie dla funkcji nieanonimowych.

W moim teście, uruchomiłem pętle przed list.reduce (zobacz poniższy kod) i okazało się, że są ponad dwa razy szybsze, nawet jeśli każda iteracja nazywa dokładnie tę samą funkcję, która została przekazana do zredukowania!

Uważam to niezwykle intuicyjne (raz pomyśli, że biblioteka Scala byłby już starannie stworzony, aby być tak optymalne jak to możliwe).

W teście I umieszczone razem, uruchomiony w tej samej pętli (Podsumowując numery 1 do milion, bez przepełnienia) pięć różnych sposobów

1. do pętli ponad tablicy wartości
2. pętli, lecz wywoływania funkcji zamiast inline arytmetyki
3. pętli, tworząc obiekt, który zawiera funkcję Dodawanie
4. list.reduce, przechodząc I anonimową funkcję
5. list.reduce, przekazując człon Przedmiotem funkcyjne

Wyniki były następujące: testy: min/max/średnie (milisekund)

1. 27/157/64.78 
2. 27/192/65.77 <--- note the similarity between tests 1,2 and 4,5 
3. 139/313/202.58 
4. 63/342/150.18 
5. 63/341/149.99 

Jak można zauważyć, że „dla zrozumienia” wersje rzędu " dla nowego dla każdej instancji ", co oznacza, że" nowy "może być w rzeczywistości przeprowadzany zarówno w anonimowych, jak i nieanonimowych wersjach funkcji.

Metodologia: kod poniżej (call Test usunięty) została opracowana w jednym pliku .jar, aby zapewnić wszystkie wersje prowadził ten sam kod biblioteki. Każdy test w każdej iteracji był wywoływany w nowej maszynie JVM (tj. Scala -cp ... dla każdego testu) w celu usunięcia problemów związanych z wielkością sterty.

class t(val i: Int) { 
    def summit(j: Int) = j + i 
} 

object bar { 
    val biglist:List[Int] = (1 to 1000000).toList 

    def summit(i: Int, j:Int) = i+j 

    // Simple for loop 
    def forloop: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      result += i 
     } 
     result 
    } 

    // For loop with a function instead of inline math 
    def forloop2: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      result = summit(result,i) 
     } 
     result 
    } 

    // for loop with a generated object PER iteration 
    def forloop3: Int = { 
     var result: Int = 0 
     for(i <- biglist) { 
      val t = new t(result) 
      result = t.summit(i) 
     } 
     result 
    } 

    // list.reduce with an anonymous function passed in 
    def anonymousfunc: Int = { 
     biglist.reduce((i,j) => {i+j}) 
    } 

    // list.reduce with a named function 
    def realfunc: Int = { 
     biglist.reduce(summit) 
    } 

    // test calling code excised for brevity. One example given: 
    args(0) match { 
     case "1" => { 
        val start = System.currentTimeMillis() 
        forloop 
        val end = System.currentTimeMillis() 
        println("for="+(end - start)) 
        } 
     ... 
} 

Answer 1

Co pan powiedział, było prawdą o „za listowe”, ale problem ze swoim pytaniem jest to, że masz pomieszane „dla listowe” z „anonimowych funkcjach”.

"Dla zrozumienia" w Scali jest cukrem syntaktycznym dla serii aplikacji .flatMap, .map i .filter. Ponieważ testujesz algorytmy redukcji i ponieważ niemożliwe jest zaimplementowanie algorytmu redukcji za pomocą tych trzech funkcji, twoje przypadki testowe są niepoprawne.

Oto przykładem "dla zrozumienia":

val listOfLists = List(List(1,2), List(3,4), List(5)) 
val result = 
    for { 
    itemOfListOfLists <- listOfLists 
    itemOfItemOfListOfLists <- itemOfListOfLists 
    } 
    yield (itemOfItemOfListOfLists + 1) 
assert(result == List(2,3,4,5,6)) 

Kompilator desugars części Rozumienie do następujących elementów:

val result = 
    listOfLists.flatMap(
    itemOfListOfLists => itemOfListOfLists.map(
     itemOfItemOfListOfLists => itemOfItemOfListOfLists + 1 
    ) 
) 

Potem desugars Anonymous Funkcja Składnia:

val result = 
    listOfLists.flatMap(
    new Function1[List[Int], List[Int]] { 
     override def apply(itemOfListOfLists: List[Int]): List[Int] = 
     itemOfListOfLists.map(
      new Function1[Int, Int] { 
      override def apply(itemOfItemOfListOfLists: Int): Int = 
       itemOfItemOfListOfLists + 1 
      } 
     ) 
    } 
) 

Z wyodrębnionego kodu jest teraz widoczne, żeKlasajest tworzona za każdym razem, gdy wywoływana jest metoda apply(itemOfListOfLists: List[Int]): List[Int]. Tak dzieje się w przypadku każdego wpisu o numerze listOfLists. Im bardziej złożone jest twoje zrozumienie, tym więcej obiektów otrzymasz.