並列ストリームを使用して2つの文字列から一致する文字の最初のインデックスを見つけよう

Question

ある文字列内にある一致文字の最初のインデックスが他の文字列内にあるかどうかを調べることを試みます。したがって、たとえば：

String first = "test"; 
String second = "123er"; 
int value = get(test, other); 
// method would return 1, as the first matching character in 
// 123er, e is at index 1 of test 

私はこれを並列ストリームを使用して達成しようとしています。私は、それほど単純にそのような文字があるかどうかを知ることができます。

test.chars().parallel().anyMatch(other::contains); 

正確なインデックスを見つけるにはどうすればよいですか？

Answer 1

あなたが本当にパフォーマンスの世話をした場合、あなたはO(n × m)時間の複雑さを避けるために試してみてくださいもう一方の文字ごとに1つの文字列を反復処理します。したがって、最初に効率的な（O(1)）ルックアップをサポートするデータ構造を取得するために1つの文字列を繰り返し、次にこれを利用して繰り返します。文字列が十分に大きい場合

BitSet encountered = new BitSet(); 
test.chars().forEach(encountered::set); 
int index = IntStream.range(0, other.length()) 
    .filter(ix->encountered.get(other.charAt(ix))) 
    .findFirst().orElse(-1); 

、このソリューションのO(n + m)時間の複雑さがはるかに短い実行時間に変わります。小文字の場合は、とにかく無関係です。

あなたは本当に、文字列は（非常に低いです）、並列処理の恩恵を受けるのに十分な大きさである、あなたは小さなadaptionsと、並行して両方の操作を行うことができると思う場合は、次の

BitSet encountered = CharBuffer.wrap(test).chars().parallel() 
    .collect(BitSet::new, BitSet::set, BitSet::or); 
int index = IntStream.range(0, other.length()).parallel() 
    .filter(ix -> encountered.get(other.charAt(ix))) 
    .findFirst().orElse(-1); 

最初の操作が使用していますやや複雑なパラレル互換のcollectがあり、それはストリーム作成のためにそれほど明白でない変更を含んでいます。

問題はbug report JDK-8071477に記載されています。簡単に言えば、String.chars()によって返されたストリームは分割能力が低いため、並列パフォーマンスが悪いです。上記のコードは、の文字列をラップしています。その文字列のchars()メソッドは、同じセマンティクスを持ちながらも優れた並列パフォーマンスを持つ別の実装を返します。この回避策は、Java 9では時代遅れになっているはずです。を使用すると、良好な並列処理のストリームを作成することができます。 2番目の操作はすでにそのように動作します。

しかし、この特定のタスクでは、並行処理を有効にするのに十分な大きさの文字列に遭遇することはほとんどありません。

Answer 2

String#indexOf(int ch)に依存して、values >= 0のみを保持して、既存の文字を削除して最初の値を取得することができます。

// Get the index of each characters of test in other 
// Keep only the positive values 
// Then return the first match 
// Or -1 if we have no match 
int result = test.chars() 
    .parallel() 
    .map(other::indexOf) 
    .filter(i -> i >= 0) 
    .findFirst() 
    .orElse(-1); 
System.out.println(result); 

出力：

1 

NB 1：インデックスは0ない1から始めるので、結果が1ない2です。

NB 2：あなたは非常に非常に長いStringを持っていない限り、タスクは複合体ではなく、作成しているため、この場合のStream並列を使用すると、公演の期間に多くを助けるべきではない、スレッドを開始し、同期は非常にあり高コストなので、通常のストリームよりもはるかに遅くなるでしょう。

Answer 3

ここでニコラスの答えをアップグレードしてください。 min()メソッドは、Stream全体の消費を強制します。このような場合には、最初に一致した要素ではなく、すべての最小値を発見した後、全体の実行を停止しfindFirst()を使用することをお勧めします：

test.chars().parallel() 
    .map(other::indexOf) 
    .filter(i -> i >= 0) 
    .findFirst() 
    .ifPresent(System.out::println);