Java 8流-如何比较元素？

Question

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

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

[C0类包装了一个CharBuffer数组，并提供了必要的char[]和equals方法，而不复制数组内容，这使得最好构造一个新的hashCode。

然后，您可以处理所有单词以在一次线性传递中找到类似词，例如

String

使用此解决方案，对于较大的单词列表，打印可能会变得更昂贵。因此，您可以更改流的操作，例如以下显示了字谜组合的前十名：

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

Answer 2

[我认为您最好的选择可能是使用多图收集器，以字符串的排序版本作为图的键，将流转换为Guava

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

。有关如何执行此操作的示例，请参见multimap。如果您只想要结果的字谜集，则可以使用Cleanest way to create a guava MultiMap from a java8 stream根据您的需要过滤和收集结果。

Answer 3

这有效。我首先完成了流中的所有排序，但这效率更高。

multimap.asMap().entrySet().stream()...

可能的改进是首先过滤单词的长度。并且您可能想尝试一下

      InputStream is = new URL("http://wiki.puzzlers.org/pub/wordlists/unixdict.txt")
              .openConnection().getInputStream();
      BufferedReader reader = new BufferedReader(new InputStreamReader(is));

      String word = "germany";
      final String sword = sortedWord(word);
      reader.lines().filter(w -> sortedWord(w).compareTo(sword) == 0).forEach(
            System.out::println);

      static String sortedWord(String w) {
         char[] chs = w.toCharArray();
         Arrays.sort(chs);
         return String.valueOf(chs);
      }

，因为其中包含更多单词。