Sequenze di valori di gruppo

Question

Mi chiedo se c'è un modo ingegnoso di usare le nuove API di Stream per "raggruppare" sequenze di valori.

ad es. dividere una serie di numeri interi, in gruppi di numeri interi in cui ogni gruppo è una sequenza numerica ascendente:

IntStream seq = IntStream.of(1, 2, 3, -1, -1, 1, 2, 1, 2); 
IntFunction next = i -> i + 1; 

// DESIRED OUTPUT: [[1,2,3], [-1], [-1], [1,2], [1,2]] 

Answer 1

Sfortunatamente, l'API Stream non è molto adatto per affrontare problemi che comportano operazioni dipendenti sull'elemento flusso, come questa uno.

Tuttavia, è possibile utilizzare la libreria StreamEx per questo:

public static void main(String[] args) { 
    IntStream seq = IntStream.of(1, 2, 3, -1, -1, 1, 2, 1, 2); 
    IntUnaryOperator next = i -> i + 1; 

    List<List<Integer>> result = 
     IntStreamEx.of(seq).boxed().groupRuns((i1, i2) -> next.applyAsInt(i1) == i2).toList(); 

    System.out.println(result); // prints "[[1, 2, 3], [-1], [-1], [1, 2], [1, 2]]" 
} 

Questo gruppi in un List tutti interi consecutivi in ​​cui il secondo è uguale alla funzione next applicata al primo. Infine, questo stream viene raccolto in un List. flussi

Answer 2

Non è così elegante come soluzione @Tunaki, ma utilizzando Java-8 "puro":

IntStream seq = IntStream.of(1, 2, 3, -1, -1, 1, 2, 1, 2); 

Deque<Deque<Integer>> r = new ArrayDeque<>(singleton(new ArrayDeque<>())); 

seq.filter(i -> !r.getLast().isEmpty() && r.getLast().getLast() + 1 != i || !r.getLast().add(i)) 
      .forEach(i -> r.add(new ArrayDeque<>(singleton(i)))); 

System.out.println(r); // prints: [[1, 2, 3], [-1], [-1], [1, 2], [1, 2]] 

qui solo per eleganza di codice che utilizzo Deque classe al fine di utilizzare il metodo getLast() (per List lo farà non essere così compatto).

Answer 3

Se si desidera operare su una struttura di dati in memoria, come un array o un elenco, è possibile farlo in Java 8 standard in pochi passaggi. Questo può essere fatto usando tecniche di programmazione di array come illustrato nel mio answer to this question. L'utilizzo di alcuni condizionali intelligenti simili a quelli utilizzati in Flown's answer to this question si prende cura delle casse marginali in modo pulito.

L'intuizione chiave è comprendere che un nuovo segmento (o gruppo) inizia in ogni punto in cui il predicato desiderato è non soddisfatto. Cioè, inizia un nuovo segmento dove seq[i-1] + 1 != seq[i]. Corriamo un IntStream sopra l'ingresso e filtrare gli indici per questa proprietà e memorizzare il risultato in alcune serie x:

int[] seq = { 1, 2, 3, -1, -1, 1, 2, 1, 2 }; 
    int[] x = IntStream.range(1, seq.length) 
         .filter(i -> seq[i-1] + 1 != seq[i]) 
         .toArray(); 

conseguente

[3, 4, 5, 7] 

Questo ci dà solo l'interno confini del segmenti. Per ottenere l'inizio e la fine dei segmenti, dobbiamo virare all'inizio del primo segmento e alla fine dell'ultimo segmento. Noi regolare l'intervallo di indice e aggiungere alcuni condizionali al filtro:

int[] x = IntStream.rangeClosed(0, seq.length) 
         .filter(i -> i == 0 || i == seq.length || 
            seq[i-1] + 1 != seq[i]) 
         .toArray(); 

    [0, 3, 4, 5, 7, 9] 

Ora ogni coppia adiacente di indici è un sottoinsieme della matrice originale. Possiamo usare un altro flusso per estrarre tali sottocampi, che dà il risultato desiderato:

int[][] result = 
     IntStream.range(0, x.length - 1) 
       .mapToObj(i -> Arrays.copyOfRange(seq, x[i], x[i+1])) 
       .toArray(int[][]::new); 

    [[1, 2, 3], [-1], [-1], [1, 2], [1, 2]] 

Questo può essere estratta in una funzione che si prende una funzione "next" che calcola il valore successivo segmento. Cioè, per ogni elemento, se l'elemento alla sua destra corrisponde al risultato della funzione successiva, gli elementi si trovano nello stesso segmento; altrimenti è un limite di segmento.Ecco il codice:

int[][] segments(int[] seq, IntUnaryOperator next) { 
    int[] x = IntStream.rangeClosed(0, seq.length) 
         .filter(i -> i == 0 || i == seq.length || 
           next.applyAsInt(seq[i-1]) != seq[i]) 
         .toArray(); 

    return IntStream.range(0, x.length - 1) 
        .mapToObj(i -> Arrays.copyOfRange(seq, x[i], x[i+1])) 
        .toArray(int[][]::new); 
} 

si definirebbe così:

int[] seq = { 1, 2, 3, -1, -1, 1, 2, 1, 2 }; 
    System.out.println(Arrays.deepToString(segments(seq, i -> i + 1))); 

    [[1, 2, 3], [-1], [-1], [1, 2], [1, 2]] 

Modifica della nuova funzione permette di dividere i segmenti in un modo diverso. Ad esempio, per dividere un array in segmenti di valori uguali, faresti questo:

int[] seq = { 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 4 }; 
    System.out.println(Arrays.deepToString(segments(seq, i -> i))); 

    [[2, 2], [1], [3, 3], [1, 1, 1], [4, 4, 4]] 

La difficoltà con utilizzando una nuova funzione come questo è che la condizione per valori appartenenti ad un segmento è limitata. Sarebbe più utile fornire un predicato comparabile ai valori adiacenti per verificare se si trovano nello stesso segmento. Possiamo farlo utilizzando un BiPredicate<Integer, Integer> se siamo disposti a pagare il costo della boxe:

int[][] segments(int[] input, BiPredicate<Integer, Integer> pred) { 
    int[] x = IntStream.rangeClosed(0, input.length) 
         .filter(i -> i == 0 || i == input.length || 
           !pred.test(input[i-1], input[i])) 
         .toArray(); 

    return IntStream.range(0, x.length - 1) 
        .mapToObj(i -> Arrays.copyOfRange(input, x[i], x[i+1])) 
        .toArray(int[][]::new); 
} 

In questo modo i segmenti di raccolta utilizzando un criterio diverso, ad esempio, monotona crescente segmenti:

int[] seq = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 }; 
    System.out.println(Arrays.deepToString(segments(seq, (a, b) -> b > a))); 

    [[3], [1, 4], [1, 5, 9], [2, 6], [5], [3]] 

Questo potrebbe essere specializzato nell'uso di un bi-predicato primitivo su due valori int oppure potrebbe essere generalizzato per consentire l'utilizzo di un valore BiPredicate di qualsiasi tipo su un input di qualsiasi tipo.