ストリーム内の重複グループを検出する

Question

リスト内のすべての数値がグループ化されていることを確認します。私は例でこれを説明してみましょう：

{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を投げるか、falseを返す必要があります"例。 Stream APIを使用してどうすればいいですか？私の自由StreamExライブラリを使用して

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

Answer 1

：繰り返しグループがある場合

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

このコードはIllegalStateExceptionを投げます

は、ここに私の現在の作成、追加Setとソリューションです。

ここではrunLengths()の方法が使用されます。それは等しい隣接する要素を畳んで、Map.Entryで置き換えます。ここで、keyは入力要素であり、valueは繰り返しの数です。最後にのショートカットであるtoMap()が使用されます。我々は、.toMap()がIllegalStateExceptionを投げるという事実を利用しています（カスタムmergeFunctionが与えられていない限り）。

成功した実行での無料ボーナスとして、キーが入力要素で値がシリーズの長さであるマップがあります。

Answer 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を使用する必要があります。

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

1. 私たちは、それぞれの計算のための新しいコンテナを作成するサプライヤーを作成します。コンテナ（他のものの中でも）は、計算を続行するかスキップする必要がある場合に情報を保持します。
2. ある時点でユニークでないグループが発生した場合は、計算全体をスキップします。
3. 現在新しいグループの先頭にいる場合は、グループが一意であるかどうかを確認します。そうでない場合は、残りのストリームをスキップすることにします。
4. これは、{0, 1, 0}というシーケンスがあるときに問題を解決するための貧弱なハックです。もちろん、この解決法は、{MAX_VALUE, 0, MAX_VALUE}では機能しません。私は単純な理由からこの問題を残すことに決めました。

我々はfalseを返し

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

に

IntStream.of(arr) 

を交換することにより、性能を確認することができます。これはもちろん、無限のストリームでは機能しませんが、無限ストリームでユニークなグループをチェックすることは実際には意味がありません。