Grupowe sekwencje wartości

Question

Zastanawiam się, czy istnieje jakaś sprytna metoda wykorzystania nowych API Stream do "grupowania" sekwencji wartości.

np. podzielić serię liczb, na grupy liczb całkowitych, gdzie każda grupa jest sekwencja liczb rosnąco:

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

Niestety, API Stream nie jest bardzo dobrze nadaje się do rozwiązania problemów, które dotyczą operacji zależnych od elementu Stream, podobnie jak to jeden.

Można jednak korzystać z biblioteki StreamEx na to:

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]]" 
} 

tej grupie w List wszystkich kolejnych liczb całkowitych, gdzie druga jest równa funkcji next przyłożonego do pierwszego. Wreszcie, ten strumień jest zbierany do List.

Answer 2

Nie tak elegancki jak roztwór @Tunaki, ale za pomocą „czystego” Java-8 strumienie:

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]] 

tu tylko na elegancji kodu używam Deque klasę, aby korzystać getLast() metody (dla List to będzie nie być tak kompaktowy).

Answer 3

Jeśli chcesz operować na strukturze danych w pamięci, takiej jak tablica lub lista, możesz to zrobić w standardowej Java 8 w zaledwie kilku krokach. Można to zrobić za pomocą technik programowania tablicowego, takich jak przedstawione w moim answer to this question. Korzystanie z niektórych sprytnych warunków, podobnych do tych używanych w Flown's answer to this question, zajmuje porządek na krawędziach w uporządkowany sposób.

Kluczowym wglądem jest uświadomienie sobie, że nowy segment (lub grupa) zaczyna się od każdego punktu, w którym pożądany predykat jest spełniony , a nie. Oznacza to, że rozpoczyna się nowy segment, gdzie seq[i-1] + 1 != seq[i]. Uciekajmy się IntStream nad wejściem i filtrować indeksy dla tej nieruchomości i zapisać wynik w jakiejś tablicy 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(); 

skutkuje

[3, 4, 5, 7] 

To daje nam tylko wnętrze granice segmenty. Aby uzyskać początkowe i końcowe segmenty, musimy zastosować się do początku pierwszego segmentu i końca ostatniego segmentu. Możemy dostosować zakres indeksu i dodać kilka warunkowe do filtra:

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] 

Teraz każdy sąsiedniej pary indeksów jest podzakres oryginalnej tablicy. Możemy użyć innego strumienia wyodrębnić te podzakresy, dając pożądany rezultat:

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]] 

ten można ekstrahować do funkcji, która sama wykonuje „następny” funkcję, która oblicza wartość następnego segmentu. Oznacza to, że dla dowolnego elementu, jeśli element po prawej stronie odpowiada wynikowi następnej funkcji, elementy znajdują się w tym samym segmencie; w przeciwnym razie jest to granica segmentu.Oto kod:

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); 
} 

Można by nazwać tak:

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]] 

Zmiana następnej funkcji umożliwia podział segmentów w inny sposób. Na przykład, aby podzielić tablicę na segmenty równej wartości, można to zrobić:

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]] 

Trudności z zastosowaniem następnej funkcji, jak to jest, że warunek dla wartości należących do segmentu jest ograniczona. Byłoby ładniej dostarczyć predykatu, który porównuje sąsiednie wartości do sprawdzenia, czy są one w tym samym segmencie. Możemy to zrobić za pomocą BiPredicate<Integer, Integer> czy jesteśmy gotowi zapłacić koszty boksie:

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); 
} 

Pozwala to na gromadzenie segmenty używając innego kryterium, na przykład, monotonicznie rosnącą segmenty:

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]] 

ten może być wyspecjalizowany, aby używać prymitywnego b-predykatu dla dwóch wartości int, lub może być uogólniony, aby umożliwić użycie dowolnego typu dowolnego typu na podstawie BiPredicate.