Scala per loop ed iteratori

Question

Supponiamo di avere una raccolta di valori iterabile molto grande (nell'ordine di 100.000 voci di stringa, leggere dal disco uno per uno) e faccio qualcosa sul suo prodotto cartesiano (e scrivo il risultato indietro su disco, anche se non voglio dimostrare che qui):

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

capisco che questo è solo un altro modo di scrivere

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

questo fa sì che a quanto pare l'intera collezione per ogni iterazione flatMap (o anche l'intero prodotto cartesiano?) da conservare in memoria. Se leggi la prima versione usando il ciclo for questo ovviamente non è necessario. Idealmente, solo due voci (quelle combinate) dovrebbero essere conservate in memoria in ogni momento.

Se riformulare il prima versione come questa:

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

consumo di memoria è molto più basso, portandomi a pensare che questa versione deve essere fondamentalmente diverso. Cosa fa esattamente nella seconda versione? Perché Scala non utilizza implicitamente gli iteratori per la prima versione? C'è qualche accelerazione quando non si usano gli iteratori in alcune circostanze?

Grazie! (E anche grazie a "lmm" che ha risposto a una precedente versione di questa domanda)

Answer 1

La prima versione è valutata rigorosamente; crea una vera raccolta concreta con tutti quei valori. Il secondo "solo" fornisce uno Iterator, che consente di scorrere tutti i valori; verranno creati mentre si esegue effettivamente l'iterazione.

Il motivo principale per cui Scala è il primo è perché scala come linguaggio consente effetti collaterali. Se si scrivono i due mappature come:

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

poi cosa succede con la seconda maggio ti ha sorpreso, soprattutto in un'applicazione più ampia in cui l'iteratore potrebbe essere creato molto lontano dal punto in cui è effettivamente utilizzato.

Una raccolta funzionerà meglio di un iteratore se l'operazione di mappa stessa è costosa e la si crea una volta e riutilizzata più volte - l'iteratore deve ricalcolare i valori ogni volta, mentre la raccolta esiste in memoria. Probabilmente questo rende le prestazioni della collezione più prevedibili - consuma molta memoria, ma è la stessa quantità per cui viene utilizzata la collezione.

Se si desidera una libreria di raccolte che sia più propensa a escludere operazioni e ottimizzare, forse perché si scrive già tutto il codice senza effetti collaterali, è possibile prendere in considerazione lo Paul Philips' new effort.

Answer 2

In Scala, yield non produce una sequenza lenta. La mia comprensione è che ottieni tutti i valori contemporaneamente in modo da poterli indicizzare tutti come una raccolta. Per esempio, io avevo scritto quanto segue per un ray tracer per generare raggi: (! Sorpresa)

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

che non è riuscito spettacolare (la memoria) perché ha fatto tutti i raggi in anticipo. Utilizzando il metodo .iterator, si richiede specificamente un iteratore pigro. L'esempio sopra può essere modificato a questo:

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

che funziona in modo pigro.