检测流中的重复组

我想确保列表中的所有数字都组合在一起。让我的例子说明这一点：检测流中的重复组

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

现在我需要传递或返回“确定”的例子也并抛出AssertionError或返回上“坏假“ 例子。我如何使用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; 
       } 
     );

来源

2016-02-05 Michal Kordas

您的解决方案不正确。考虑到当前的实现（显然假定顺序执行），它可能会起作用，但该函数显然违反了关联性要求。不幸的是，没有第三方帮助，没有简单的解决方案... – Holger

@Holger你能解释什么是“结合性要求”？ –

@MichalKordas，请参阅[documentation]（https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#reduce-T-java.util.function.BinaryOperator- ）：累加器必须按照规范进行关联。 –

用我的自由StreamEx库：

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

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

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

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

来源

2016-02-05 09:56:00

在我看来，这个问题根本不适合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。

来源

2016-02-05 21:37:07 Flown

不错，+1。这里的关键洞察是，一个组的开始被谓词'arr [i]！= arr [i-1]'检测到。对于更常见的问题，我会使用收集器来生成结果，但对于这种使用'allMatch（seen :: add）'的特定情况来说，相当聪明。另外，名称'hasMultipleGroups'具有错误的意义;也许'hasUniqueGroups'会更好？ –

@StuartMarks使用'收集器'是我第一次尝试，但它没有短路的行为。因此它不适用于这个问题。 – Flown

除了已经说过的内容之外，我们可以尝试使用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)

检查性能

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

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

来源

2016-04-25 17:18:10

检测流中的重复组

回答

相关问题