Stile funzionale Java 8 per iterare con gli indici

Question

Ho praticato java 8 stream e lo stile funzionale per un po '. A volte provo a risolvere alcuni enigmi di programmazione usando solo i flussi. E durante questo periodo ho trovato una classe di compiti che non so come risolvere con i flussi, solo con un approccio classico.

Un esempio di questo tipo di attività è: Dato un array di numeri, trovare l'indice dell'elemento che farà la somma della parte sinistra della matrice sotto zero. ad es. per array [1, 2, 3, -1, 3, -10, 9] la risposta sarà 5

La mia prima idea era quella di usare IntStream.generate(0, arr.length)... ma poi non so come accumulare valori e di essere consapevole dell'indice stesso tempo.

Così domande sono:

• E 'possibile accumulare in qualche modo il valore sul torrente e poi fare uscire condizionale?
• Che cos'è allora con l'esecuzione parallela? non è corretto il problema di trovare indici in cui è necessario essere a conoscenza dell'ordine degli elementi.

Answer 1

Dubito che il tuo compito sia adatto per i flussi. Quello che stai cercando è una tipica operazione di scansione a sinistra che è per sua natura un'operazione sequenziale.

Ad esempio, immaginare i seguenti elementi nella pipeline: [1, 2, -4, 5]. Un'esecuzione parallela può dividerla in due parti secondarie, ovvero [1, 2] e [-4, 5]. Allora cosa faresti con loro? Non è possibile sommarle in modo indipendente perché produrrà [3] e [1] e quindi si è perso il fatto che 1 + 2 - 4 < 0 è stato rispettato.

Quindi, anche se si scrive un raccoglitore che tiene traccia dell'indice, e la somma, non sarà in grado di comportarsi bene in parallelo (dubito che si possa anche trarne beneficio) ma si può immaginare un tale collezionista per uso sequenziale:

public static Collector<Integer, ?, Integer> indexSumLeft(int limit) { 
     return Collector.of(
       () -> new int[]{-1, 0, 0}, 
       (arr, elem) -> { 
        if(arr[2] == 0) { 
         arr[1] += elem; 
         arr[0]++; 
        } 
        if(arr[1] < limit) { 
         arr[2] = 1; 
        } 

       }, 
       (arr1, arr2) -> {throw new UnsupportedOperationException("Cannot run in parallel");}, 
       arr -> arr[0] 

     ); 
    } 

e un uso semplice:

int index = IntStream.of(arr).boxed().collect(indexSumLeft(0)); 

Questo sarà ancora attraversare tutti gli elementi della pipeline, quindi non molto efficiente.

Inoltre, è possibile utilizzare Arrays.parallelPrefix se la sorgente dati è una matrice. Basta calcolare le somme parziali su di esso e quindi utilizzare un flusso per trovare il primo indice in cui la somma è inferiore al limite.

Arrays.parallelPrefix(arr, Integer::sum); 
int index = IntStream.range(0, arr.length) 
        .filter(i -> arr[i] < limit) 
        .findFirst() 
        .orElse(-1); 

Qui anche tutte le somme parziali sono calcolate (ma in parallelo).

In breve, vorrei utilizzare un semplice ciclo.

Answer 2

posso proporre una soluzione usando il mio StreamEx libreria (che fornisce funzioni aggiuntive per l'API Stream), ma non vorrei essere molto felice con tale soluzione:

int[] input = {1, 2, 3, -1, 3, -10, 9}; 
System.out.println(IntStreamEx.of(
    IntStreamEx.of(input).scanLeft(Integer::sum)).indexOf(x -> x < 0)); 
// prints OptionalLong[5] 

Esso utilizza IntStreamEx.scanLeft operazione per calcolare la matrice di somme prefisso, quindi le ricerche su questo array utilizzando l'operazione IntStreamEx.indexOf. Mentre indexOf è in cortocircuito, l'operazione scanLeft elaborerà l'intero input e creerà un array intermedio della stessa lunghezza dell'input che è completamente inutile quando si risolve lo stesso problema in modo imperativo.

Answer 3

Con il nuovo metodo headTail nella mia libreria StreamEx è possibile creare una soluzione lazy che funzioni bene per flussi molto lunghi o infiniti. In primo luogo, si può definire un nuovo scanLeft operazione intermedia:

public static <T> StreamEx<T> scanLeft(StreamEx<T> input, BinaryOperator<T> operator) { 
    return input.headTail((head, tail) -> 
       scanLeft(tail.mapFirst(cur -> operator.apply(head, cur)), operator) 
        .prepend(head)); 
} 

Questo definisce un pigro scanLeft usando l'headTail: si applica in funzione alla head e il primo elemento del flusso tail, quindi antepone il head. Ora è possibile utilizzare questo scanLeft:

scanLeft(StreamEx.of(1, 2, 3, -1, 3, -10, 9), Integer::sum).indexOf(x -> x < 0); 

Lo stesso può essere applicato al flusso infinito (ad esempio flusso di numeri casuali):

StreamEx<Integer> ints = IntStreamEx.of(new Random(), -100, 100) 
            .peek(System.out::println).boxed(); 
int idx = scanLeft(ints, Integer::sum).indexOf(x -> x < 0); 

Questo durerà fino la somma cumulativa diventa negativo e restituisce il indice dell'elemento corrispondente.