Scala dla pętli i iteratorów

Question

Załóżmy, że mam bardzo duży zbiór wartości iterowalnych (w kolejności 100 000 wpisów String, czytanych z dysku jeden po drugim), i robię coś na produkcie kartezjańskim (i zapisuję wynik) na dysku, choć nie pokaże, że tutaj):

for(v1 <- values; v2 <- values) yield ((v1, v2), 1) 

rozumiem, że jest to po prostu inny sposób pisania

values.flatMap(v1 => values.map(v2 => ((v1, v2), 1))) 

to najwyraźniej powoduje całą kolekcję dla każdego flatMap iteracji (lub nawet cały produkt kartezjański?), który ma być przechowywany w pamięci. Jeśli czytasz pierwszą wersję za pomocą pętli for, to oczywiście nie jest konieczne. Najlepiej byłoby, gdyby tylko dwa wpisy (te połączone) zawsze były przechowywane w pamięci.

Gdybym przeformułować pierwszą wersję takiego:

for(v1 <- values.iterator; v2 <- values.iterator) yield ((v1, v2), 1) 

zużycie pamięci jest dużo niższy, prowadząc mnie przyjąć, że ta wersja musi być zasadniczo różne. Co dokładnie robi to inaczej w drugiej wersji? Dlaczego Scala nie używa domyślnie iteratorów w pierwszej wersji? Czy jest jakieś przyspieszenie, gdy nie używasz iteratorów w pewnych okolicznościach?

Dzięki! (A także dzięki "lmm", który odpowiedział na wcześniejszą wersję tego pytania)

Answer 1

Pierwsza wersja jest ściśle oceniana; tworzy prawdziwą, konkretną kolekcję z wszystkimi tymi wartościami. Drugi "po prostu" zapewnia Iterator, który pozwala ci powtórzyć wszystkie wartości; zostaną utworzone, gdy faktycznie wykonasz iterację.

Głównym powodem, dla którego Scala domyślnie jest pierwszym, jest to, że scala jako język pozwala na efekty uboczne. Jeśli piszesz dwa mapowania jako:

for(v1 <- values; v2 <- values) yield {println("hello"); ((v1, v2), 1)} 
for(v1 <- values.iterator; v2 <- values.iterator) yield { 
    println("hello"); ((v1, v2), 1)} 

to co dzieje się z drugim mogą Cię zaskoczyła, zwłaszcza w większych zastosowaniach, gdzie iterator może być utworzony długą drogę od miejsca, gdzie to jest rzeczywiście używany.

Kolekcja będzie działała lepiej niż iterator, jeśli sama operacja mapy jest kosztowna i tworzy się ją raz, a następnie wielokrotnie jej używa - iterator musi za każdym razem przeliczać wartości, podczas gdy kolekcja istnieje w pamięci. Prawdopodobnie sprawia to, że wydajność kolekcji jest bardziej przewidywalna - zużywa dużo pamięci, ale jest taka sama, niezależnie od tego, do jakiej kolekcji jest przeznaczona.

Jeśli potrzebujesz biblioteki kolekcji, która jest bardziej skłonna do znoszenia operacji i optymalizacji - być może dlatego, że już piszesz cały swój kod bez efektów ubocznych - możesz wziąć pod uwagę Paul Philips' new effort.

Answer 2

W Scali, yield nie wytwarza leniwych sekwencji. Rozumiem, że otrzymujesz wszystkie wartości naraz, dzięki czemu możesz je zindeksować jako kolekcję. Na przykład, miałem napisane następujące dla znacznika ray do generowania promieniowania: (! Niespodzianka)

def viewRays(aa:ViewHelper.AntiAliasGenerator) = 
{ 
    for (y <- 0 until height; x <- 0 until width) 
    yield (x, y, aa((x, y))) 
} 

które zawiodły spektakularnie (z pamięci), ponieważ wykonane wszystkie promienie z przodu. Korzystając z metody .iterator, prosisz o leniwy iterator. Powyższy przykład można zmodyfikować do tego:

def viewRays(aa:ViewHelper.AntiAliasGenerator) = 
{ 
    for (y <- 0 until height iterator; x <- 0 until width iterator) 
    yield (x, y, aa((x, y))) 
} 

który działa w leniwy sposób.