使用並行流查找來自兩個字符串的匹配字符的第一個索引

試圖找出是否有可能找到某個字符串中的匹配字符的第一個索引，該字符串也在另一個字符串中。所以例如：使用並行流查找來自兩個字符串的匹配字符的第一個索引

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);

我該如何使用它來找到確切的指數？

來源

2016-11-17 relisher

但'e'在索引'1'處，'t'也在'other'，所以它應該返回'0'，對吧？ – Zircon

我想知道使用並行流的性能會在這裏介紹多少。換句話說：爲什麼平行？ – GhostCat

@GhostCat，我會相信通過並行檢查每個字符，複雜度會降低到第一個字符串被檢查的字符的複雜度。這是一個有一個起點的問題，並且一旦我達到能夠應用這個的更大的文本。 – relisher

如果你真的關心性能，你應該儘量避免O(n × m)時間複雜度爲另一個字符的每個字符迭代一個字符串。因此，首先迭代一個字符串以獲得支持高效（O(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()返回的流具有較差的分裂能力，因此並行性能差。上面的代碼將字符串包裝在CharBuffer中，其chars()方法返回不同的實現，具有相同的語義，但具有良好的並行性能。此解決方法應該在Java 9中過時。

或者，您可以使用IntStream.range(0, test.length()).map(test::charAt)創建具有良好並行性能的數據流。第二個操作已經以這種方式工作。

但是，正如所說的，對於這個特定的任務，您不太可能會遇到足夠大的字符串來使並行處理變得有益。

來源

2016-11-18 12:51:41 Holger

您可以通過依靠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);

輸出：

NB 1：結果是1不2因爲索引從0不1啓動。

NB 2：除非你有非常非常長的String，使用的表演任期平行Stream在這種情況下，不應該太大的幫助，因爲任務是不配合和創建，啓動和同步線程具有非常成本高，所以你可能會得到你的結果比普通流慢得多。

來源

2016-11-17 19:32:42

我不知道這是否真的有效。但我相信你......順便說一句很好的新頭像圖標。 – GhostCat

這個解決方案其實很棒：D一注：min（）是一種矯枉過正，因爲強制處理整個流。 findFirst（）可能是一個更好的選擇 –

@pivovarit嗯，至少對於給定的例子，我認爲**過度殺傷**已經開始了，在這裏調用* parallel（）*的想法。 – GhostCat

在此升級Nicolas的答案。 min()方法強制執行整個Stream的消耗。在這種情況下，最好使用findFirst()其找到第一個匹配的元素，而不是最低的是後停止全部執行：

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

來源

2016-11-17 19:43:30

使用並行流查找來自兩個字符串的匹配字符的第一個索引

回答

相關問題