检测流中的重复组

我想确保列表中的所有数字都组合在一起。 让我用例子解释一下：

{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) ... 

现在我需要为“OK”示例传递或返回true，并抛出AssertionError或在“Bad”示例中返回false。 如何使用Stream API执行此操作？

这是我当前创建的附加Set解决方案：

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

Answer 1

使用我的免费StreamEx库：

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

如果有重复的组，此代码将抛出IllegalStateException 。

这里使用了runLengths()方法。 它折叠相等的相邻元素，用Map.Entry替换它们，其中key是输入元素，value是重复的数量。 最后使用toMap() ，它是.collect(Collectors.toMap(Entry::getKey, Entry::getValue))的快捷方式。 我们正在使用.toMap()在键重复时抛出IllegalStateException这一事实（除非提供了自定义mergeFunction）。

作为成功执行的免费奖励，您将拥有一个地图，其中键是输入元素，值是系列的长度。

Answer 2

在我看来，这个问题根本不适合Stream API ，但我很好奇这是如何实现的（但是以高效的方式）。

问题是你必须跟踪看到的元素，整个测试应该有一个短路行为。 所以我提出了这个解决方案（没有Streams ）：

 public static boolean hasUniqueGroups(int[] arr) { Objects.requireNonNull(arr); Set 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 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 。

Answer 3

除了已经说过的内容之外，我们可以尝试使用collect方法回答这个问题。 这种方法的问题（正如其他人所指出的）是减少操作不会很快终止。

通常，为了使长时间减速操作短路，我们可以使减少function短路。 这样，虽然我们仍然遍历流中的所有项目，但所需的工作量是最小的。

 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 integers = new HashSet<>(); } 

1. 我们创建供应商，为每次计算创建新的Container。 如果我们应该继续或跳过计算，容器（以及其他内容）将保存信息。
2. 如果在某些时候我们遇到了非唯一组，我们将跳过整个计算。
3. 如果我们目前处于新组的开头，我们会检查它是否是唯一的。 如果没有，我们决定跳过其余的流。
4. 当我们有序列{0, 1, 0}时，这是一个很难解决问题的黑客。 当然，此解决方案不适用于{MAX_VALUE, 0, MAX_VALUE} 。 为了简单起见，我决定留下这个问题。

我们可以通过替换来检查性能

 IntStream.of(arr) 

至

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

返回false 。 这当然不适用于无限流，但检查无限流中的唯一组并不真正有意义。