Обнаружение дублированных групп в потоке

Я хочу, чтобы все числа в списке группировались вместе. Позвольте мне объяснить это на примерах:

{1, 1, 1, 2, 2}    // OK, two distinct groups
{1, 1, 2, 2, 1, 1} // Bad, two groups with "1"
{1, 2, 3, 4}       // OK, 4 distinct groups of size 1
{1, 1, 1, 1}       // OK, 1 group
{3, 4, 3}          // Bad, two groups with "3"
{99, -99, 99}      // Bad, two groups with "99"
{}                 // OK, no groups

Вот как я получаю поток:

IntStream.of(numbers)
    ...

Теперь мне нужно передать или вернуть true для примеров "ОК" и бросить AssertionError или вернуть false на примерах "Плохие". Как я могу это сделать с помощью Stream API?

Здесь мое текущее решение с дополнительным Set создало:

Set<Integer> previousNumbers = new HashSet<>();
IntStream.of(numbers)
        .reduce(null, (previousNumber, currentNumber) -> {
                    if (currentNumber == previousNumber) {
                        assertThat(previousNumbers).doesNotContain(currentNumber);
                        previousNumbers.add(currentNumber);
                    }
                    return currentNumber;
                }
        );

Ответы

Ответ 1

Используя мою бесплатную библиотеку StreamEx:

IntStreamEx.of(numbers).boxed().runLengths().toMap();

Этот код будет бросать IllegalStateException, если есть повторяющиеся группы.

Здесь используется метод runLengths(). Он сворачивает равные смежные элементы, заменяя их Map.Entry, где ключ является элементом ввода, а значение - количеством повторов. Наконец используется toMap(), который является ярлыком для .collect(Collectors.toMap(Entry::getKey, Entry::getValue)). Мы используем тот факт, что .toMap() выбрасывает IllegalStateException, когда клавиши повторяются (если не предоставляется специальная функция mergeFunction).

В качестве бесплатного бонуса за успешное выполнение вы получите карту, где ключи являются элементами ввода, а значения - это длины серии.

Ответ 2

По-моему, эта проблема не подходит для Stream API вообще, но мне было любопытно, как это может быть реализовано (однако, по-настоящему).

Проблема в том, что вы должны отслеживать увиденные элементы, и весь тест должен иметь поведение при коротком замыкании. Поэтому я придумал это решение (без Streams):

public static boolean hasUniqueGroups(int[] arr) {
    Objects.requireNonNull(arr);
    Set<Integer> seen = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        if (i == 0 || arr[i] != arr[i - 1]) {
            if (!seen.add(arr[i])) {
                return false;
            }
        }
    }
    return true;
}

Следующий шаг - ввести Stream API, и решение будет выглядеть следующим образом:

public static boolean hasUniqueGroups(int[] arr) {
    Objects.requireNonNull(arr);
    Set<Integer> seen = new HashSet<>();
    return IntStream.range(0, arr.length)
            .filter(i -> i == 0 || arr[i] != arr[i - 1])
            .mapToObj(i -> arr[i])
            .allMatch(seen::add);
}

Примечание. Чтобы распараллелить этот Stream, вы должны использовать поточно-безопасный Set.

Ответ 3

Больше того, что уже было сказано, мы могли бы попытаться ответить на этот вопрос, используя метод collect. Проблема с этим подходом (как указывали другие) заключается в том, что операции сокращения не заканчиваются быстро.

Как правило, для короткого замыкания длинной операции сокращения мы можем коротко закоротить функцию уменьшения. Таким образом, хотя мы все еще повторяем все элементы в потоке, требуемая минимальная работа минимальна.

public static boolean hasUniqueGroups(int... arr) {
    return !IntStream
        .of(arr) 
        .collect(
                Container::new, // 1
                (container, current) -> {
                    if (container.skip) return; // 2
                    if (current != container.previous) {
                        container.previous = current;
                        if (!container.integers.add(current))
                            container.skip = true; // 3
                    }
                },
                (c1, c2) -> {
                    if (c1.skip != c2.skip) {
                        c1.skip = true;
                        c1.integers.addAll(c2.integers);
                    }
                }
        )
        .skip;
}

private static class Container {
    private int previous = MAX_VALUE; // 4
    private boolean skip = false;
    private Set<Integer> integers = new HashSet<>();
}
  • Мы создаем Поставщика, который создаст новый Контейнер для каждого вычисления. Контейнер (между прочим) будет содержать информацию, если мы должны продолжить или пропустить вычисления.
  • Если в какой-то момент мы встретили неединственную группу, мы пропустим все вычисления.
  • Если мы сейчас находимся в начале новой группы, мы проверяем, является ли она уникальной. Если нет, мы решили пропустить остальную часть потока.
  • Это плохой взлом для решения проблемы, когда у нас есть последовательность {0, 1, 0}. Конечно, это решение не будет работать, т.е. {MAX_VALUE, 0, MAX_VALUE}. Я решил оставить эту проблему по простоте.

Мы можем проверить производительность, заменив

IntStream.of(arr)

to

IntStream.concat(IntStream.of(1, 2), IntStream.range(1, Integer.MAX_VALUE))

который возвращает false. Это, конечно, не будет работать для бесконечных потоков, но проверка уникальных групп в бесконечном потоке не имеет смысла.