Групповые последовательности значений

Question

Мне интересно, есть ли какой-нибудь отличный способ использовать новые API-интерфейсы Stream для группировки последовательностей значений.

например. разделить ряд чисел, в группы целых чисел, где каждая группа представляет собой порядковый номер по возрастанию:

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

К сожалению, поток API не очень хорошо подходит для решения проблем, которые связаны зависимые операции на элементе потока, как это один.

Однако, вы можете использовать StreamEx библиотеку для этого:

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

Это групп в List всех последовательных целых чисел, где вторая одна равна функции next, приложенной к первому. Наконец, этот поток собран в List.

Answer 2

Не так элегантно, как решение @Tunaki, но с использованием «чистого» Java-8 потоков:

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

Вот только для изящества кода я использую Deque класс для того, чтобы использовать getLast() метод (для List это будет быть не столь компактным).

Answer 3

Если вы хотите работать со структурой данных в памяти, например массивом или списком, это можно сделать в стандартном Java 8 всего за пару шагов. Это можно сделать с помощью методов программирования массива, например, в моем answer to this question. Используя некоторые умные условные обозначения, аналогичные используемым в Flown's answer to this question, аккуратно заботятся о краях.

Ключевое понимание заключается в том, чтобы понять, что новый сегмент (или группа) начинается в каждой точке, где искомый предикат не met. То есть начинается новый сегмент, где seq[i-1] + 1 != seq[i]. Давайте запускать IntStream над входом и фильтрации индексов для этого свойства и сохранить результат в некотором массиве 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(); 

в результате

[3, 4, 5, 7] 

Это только дает нам интерьер границы сегменты. Чтобы получить начальные и конечные сегменты, нам нужно зацепить начало первого сегмента и конец последнего сегмента. Мы корректируем диапазон индекса и добавить несколько условных к фильтру:

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] 

Теперь каждая смежная пара индексов поддиапазон исходного массива. Мы можем использовать другой поток, чтобы извлечь эти поддиапазоны, что дает желаемый результат:

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

Это может быть извлечена в функцию, которая сама по себе принимает «следующий» функцию, которая вычисляет следующее значение в сегменте. То есть для любого элемента, если элемент справа от него соответствует результату следующей функции, элементы находятся в одном и том же сегменте; в противном случае это граница сегмента.Вот код:

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

Вы назвали бы это так:

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

Изменения следующей функции позволяет разделив сегменты по-другому. Например, чтобы разбить массив на сегменты равных значений, вы могли бы сделать это:

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

Трудности с использованием следующей функции, как это, что условие для значений, принадлежащих к сегменту ограниченно. Было бы лучше предоставить предикат, который сравнивается со смежными значениями, чтобы проверить, находятся ли они в одном сегменте. Мы можем сделать это с помощью BiPredicate<Integer, Integer> если мы готовы заплатить стоимость бокса:

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

Это позволяет Сегменты сбора, используя другой критерий, например, монотонно возрастающие сегменты:

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

Этого может быть специализированным для использования примитивного би-предиката над двумя значениями int или его можно обобщить, чтобы разрешить использование BiPredicate любого типа для ввода любого типа.