Java 8 Streams - 如何比较元素？

Question

我想使用 Java Stream 在 .txt 文件中查找字谜。这是我所拥有的:

try (InputStream is = new URL("http://wiki.puzzlers.org/pub/wordlists/unixdict.txt").openConnection().getInputStream();
     BufferedReader reader = new BufferedReader(new InputStreamReader(is));
     Stream<String> stream = reader.lines()) {

以及字谜的方法:

public boolean isAnagram(String firstWord, String secondWord) {
    char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
    char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
    Arrays.sort(word1);
    Arrays.sort(word2);
    return Arrays.equals(word1, word2);
}

如何使用 Java 8 Stream 检查 unixdict.txt 中的单词是否是字谜？有没有办法将一个单词与流中的所有单词进行比较？

Answer 1

当您想要找到所有字谜词时，不建议尝试将一个单词与所有其他单词进行比较，因为您最终会将每个单词与其他每个单词进行比较，这称为二次 time complexity 。处理 1,000 个单词，您需要进行一百万次比较，处理 100,000 个单词，您需要进行 10,000,000,000 次比较，依此类推。

您可以更改您的isAnagram方法为 HashMap 等数据结构提供查找键:

static CharBuffer getAnagramKey(String s) {
    char[] word1 = s.replaceAll("[\\s]", "").toCharArray();
    Arrays.sort(word1);
    return CharBuffer.wrap(word1);
}

类(class)CharBuffer包装 char[]数组并提供必要的equals和hashCode方法而不复制数组内容，这使得它比构造新的 String 更好。 .

作为旁注，.replaceAll("[\\s]", "")可以简化为.replaceAll("\\s", "") ，两者都会消除所有空格字符，但问题的示例输入根本没有空格字符。要删除所有非单词字符(例如撇号和与号)，您可以使用 s.replaceAll("\\W", "") .

然后，您可以处理所有单词以在单个线性传递中查找字谜词，例如

URL srcURL = new URL("http://wiki.puzzlers.org/pub/wordlists/unixdict.txt");
try(InputStream is = srcURL.openStream();
    BufferedReader reader = new BufferedReader(new InputStreamReader(is));
    Stream<String> stream = reader.lines()) {

    stream.collect(Collectors.groupingBy(s -> getAnagramKey(s)))
        .values().stream()
        .filter(l -> l.size() > 1)
        .forEach(System.out::println);
}

使用此解决方案，对于较大的单词列表，打印可能会成为更昂贵的部分。因此您可以更改流的操作，例如下面打印前十个字谜组合:

stream.collect(Collectors.groupingBy(s -> getAnagramKey(s)))
    .values().stream()
    .filter(l -> l.size() > 1)
    .sorted(Collections.reverseOrder(Comparator.comparingInt(List::size)))
    .limit(10)
    .forEach(System.out::println);