Perché è necessario un combinatore per ridurre il metodo che converte il tipo in java 8



1 Answers

La risposta di Eran descriveva le differenze tra le versioni two-arg e three-arg di reduce in quanto il primo riduce Stream<T> a T mentre il secondo riduce Stream<T> a U Tuttavia, in realtà non ha spiegato la necessità della funzione combinatore aggiuntiva quando si riduce Stream<T> a U

Uno dei principi di progettazione dell'API di Streams è che l'API non dovrebbe differire tra i flussi sequenziali e paralleli o, in altri termini, una particolare API non dovrebbe impedire il corretto funzionamento di uno stream in sequenza o in parallelo. Se i tuoi lambda hanno le proprietà giuste (associative, non interferenti, ecc.), Un flusso eseguito sequenzialmente o in parallelo dovrebbe dare gli stessi risultati.

Consideriamo innanzitutto la versione a due argomenti della riduzione:

T reduce(I, (T, T) -> T)

L'implementazione sequenziale è semplice. Il valore dell'identità I viene "accumulato" con l'elemento zeroth stream per dare un risultato. Questo risultato viene accumulato con il primo elemento stream per fornire un altro risultato, che a sua volta viene accumulato con il secondo elemento stream e così via. Dopo che l'ultimo elemento è stato accumulato, viene restituito il risultato finale.

L'implementazione parallela inizia dividendo il flusso in segmenti. Ogni segmento viene elaborato dal proprio thread nel modo sequenziale descritto sopra. Ora, se abbiamo thread N, abbiamo N risultati intermedi. Questi devono essere ridotti a un solo risultato. Poiché ogni risultato intermedio è di tipo T, e ne abbiamo diversi, possiamo usare la stessa funzione di accumulatore per ridurre quei risultati intermedi N a un unico risultato.

Consideriamo ora un'ipotetica operazione di riduzione a due arg che riduce il Stream<T> a U In altre lingue questa operazione viene chiamata "fold" o "fold-left" quindi è quello che chiamerò qui. Nota questo non esiste in Java.

U foldLeft(I, (U, T) -> U)

(Si noti che il valore di identità I è di tipo U.)

La versione sequenziale di foldLeft è proprio come la versione sequenziale di reduce tranne per il fatto che i valori intermedi sono di tipo U anziché di tipo T. Ma è altrimenti lo stesso. ( foldRight operazione foldRight sarebbe simile eccetto che le operazioni sarebbero eseguite da destra a sinistra invece che da sinistra a destra.)

Considerare ora la versione parallela di foldLeft . Iniziamo dividendo il flusso in segmenti. Possiamo quindi fare in modo che ciascuno dei thread N riduca i valori T nel suo segmento in N valori intermedi di tipo U. Ora che cosa? Come possiamo ottenere da N i valori di tipo U fino a un singolo risultato di tipo U?

Ciò che manca è un'altra funzione che combina i risultati multipli intermedi di tipo U in un singolo risultato di tipo U. Se abbiamo una funzione che combina due valori U in uno, è sufficiente ridurre qualsiasi numero di valori fino a uno - proprio come la riduzione originale sopra. Pertanto, l'operazione di riduzione che dà un risultato di un tipo diverso ha bisogno di due funzioni:

U reduce(I, (U, T) -> U, (U, U) -> U)

Oppure, usando la sintassi di Java:

<U> U reduce(U identity, BiFunction<U,? super T,U> accumulator, BinaryOperator<U> combiner)

In sintesi, per eseguire la riduzione parallela a un tipo di risultato diverso, abbiamo bisogno di due funzioni: una che accumula elementi T in valori intermedi U e un secondo che combina i valori intermedi U in un risultato U singolo. Se non stiamo cambiando i tipi, risulta che la funzione dell'accumulatore è la stessa della funzione combinatore. Ecco perché la riduzione allo stesso tipo ha solo la funzione di accumulatore e la riduzione ad un tipo diverso richiede funzioni separate di accumulatore e combinatore.

Infine, Java non fornisce le operazioni foldLeft e foldRight perché implicano un particolare ordinamento di operazioni che è intrinsecamente sequenziale. Ciò si scontra con il principio di progettazione sopra riportato di fornire API che supportano allo stesso modo operazioni sequenziali e parallele.

Question

Ho difficoltà a comprendere appieno il ruolo che il combiner soddisfa negli Stream reduce metodo.

Ad esempio, il seguente codice non viene compilato:

int length = asList("str1", "str2").stream()
            .reduce(0, (accumulatedInt, str) -> accumulatedInt + str.length());

L'errore di compilazione dice: (argomento non corrispondente, int non può essere convertito in java.lang.String)

ma questo codice si compila:

int length = asList("str1", "str2").stream()  
    .reduce(0, (accumulatedInt, str ) -> accumulatedInt + str.length(), 
                (accumulatedInt, accumulatedInt2) -> accumulatedInt + accumulatedInt2);

Capisco che il metodo del combinatore sia usato in flussi paralleli - quindi nel mio esempio si sommano due interi accumulati intermedi.

Ma non capisco perché il primo esempio non si compili senza il combinatore o come il combinatore stia risolvendo la conversione di string in int poiché si tratta di aggiungere solo due interi.

Qualcuno può far luce su questo?




Non esiste una versione ridotta che prende due diversi tipi senza un combinatore poiché non può essere eseguito in parallelo (non è sicuro il motivo per cui questo è un requisito). Il fatto che l' accumulatore debba essere associativo rende questa interfaccia praticamente inutile poiché:

list.stream().reduce(identity,
                     accumulator,
                     combiner);

Produce gli stessi risultati di:

list.stream().map(i -> accumulator(identity, i))
             .reduce(identity,
                     combiner);



Related