如何计算每个单词的出现次数？

Question

如果我有一篇英文文章或一本英文小说,我想计算每个单词出现的次数,用Java编写的最快算法是什么？

有人说你可以使用Map <String,Integer>()来完成这个,但我想知道我怎么知道关键词是什么？每篇文章都有不同的词汇,你怎么知道"关键"词然后加上一个呢？

Answer 1

以下是使用Java 8中出现的内容实现此目的的另一种方法:

private void countWords(final Path file) throws IOException {
    Arrays.stream(new String(Files.readAllBytes(file), StandardCharsets.UTF_8).split("\\W+"))
        .collect(Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting())).entrySet()
        .forEach(System.out::println);
}

那它在做什么？

1. 它将文本文件完全读入内存,更精确地读入字节数组:Files.readAllBytes(file).这个方法在Java 7中出现并且允许以非常快的速度加载文件的方法,但是以文件将完全在内存中的价格为代价,花费了大量内存.对于速度而言,这是一个很好的appraoch.
2. byte []转换为String:new String(Files.readAllBytes(file), StandardCharsets.UTF_8)同时假设文件是​​UTF8编码的.根据自己的需要改变.价格是内存中已经很大的数据的完整内存副本.它可以更快地工作与内存映射文件来代替.
3. 该字符串在非Word charcaters中分割:...split("\\W+")它创建一个包含所有单词的字符串数组.
4. 我们从该数组创建一个流:Arrays.stream(...).这本身并没有做太多,但我们可以用流做很多有趣的事情
5. 我们将所有单词组合在一起:Collectors.groupingBy(Function.<String>identity(), TreeMap::new, counting()).这意味着:
   • 我们想用单词self(identity())对单词进行分组.如果您希望分组不区分大小写,我们还可以首先在此处小写字符串.这最终将成为地图中的关键.
   • 因此,为了存储分组值,我们需要一个TreeMap(TreeMap::new).TreeMaps按其键排序,因此我们可以轻松地按字母顺序输出.如果您不需要排序,也可以在此处使用HashMap.
   • 作为每个组的值,我们希望每个单词的出现次数(counting()).在背景中,这意味着对于我们添加到组的每个单词,我们将计数器增加1.
6. 从第5步开始,我们留下了一个地图,将单词映射到他们的计数.现在我们只想打印它们.因此,我们在此map(.entrySet())中访问包含所有键/值对的集合.
7. 最后实际打印.我们说应该将每个元素传递给println方法:.forEach(System.out::println).现在你留下一个很好的清单.

那么答案有多好？好处是非常短暂,因此表现力很强.它也只与隐藏在后面的单个系统调用相关Files.readAllBytes(或者至少是固定数字,我不确定这是否真的适用于单个系统调用)并且系统调用可能是瓶颈.例如,如果您正在从流中读取文件,则每次调用read都可能触发系统调用.通过使用名称为缓冲区的BufferedReader,可以显着减少这种情况.但是readAllBytes应该是最快的.这样做的代价是它消耗了大量的内存.然而,维基百科声称一本典型的英文书有500页,每页有2000个字符,这意味着大约1兆字节,即使你在智能手机,树莓派或真正的旧电脑上,这在内存消耗方面也不应该成为问题.

这个解决方案确实涉及到Java 8之前无法实现的一些优化.例如,成语map.put(word, map.get(word) + 1)要求在地图中查找"word",这是不必要的浪费.

但是,对于编译器而言,简单的循环可能更容易优化,并且可能会节省大量方法调用.所以我想知道并对此进行测试.我使用以下方法生成文件:

[ -f /tmp/random.txt ] && rm /tmp/random.txt; for i in {1..15}; do head -n 10000 /usr/share/dict/american-english >> /tmp/random.txt; done; perl -MList::Util -e 'print List::Util::shuffle <>' /tmp/random.txt > /tmp/random.tmp; mv /tmp/random.tmp /tmp/random.txt

这给了我一个大约1,3MB的文件,所以对于一本大多数单词重复15次的书来说不是那么不典型,但是随机排序以避免这最终成为一个分支预测测试.然后我运行了以下测试:

public class WordCountTest {

    @Test(dataProvider = "provide_description_testMethod")
    public void test(String description, TestMethod testMethod) throws Exception {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100_000; i++) {
            testMethod.run();
        }
        System.out.println(description + " took " + (System.currentTimeMillis() - start) / 1000d + "s");
    }

    @DataProvider
    public Object[][] provide_description_testMethod() {
        Path path = Paths.get("/tmp/random.txt");
        return new Object[][]{
            {"classic", (TestMethod)() -> countWordsClassic(path)},
            {"mixed", (TestMethod)() -> countWordsMixed(path)},
            {"mixed2", (TestMethod)() -> countWordsMixed2(path)},
            {"stream", (TestMethod)() -> countWordsStream(path)},
            {"stream2", (TestMethod)() -> countWordsStream2(path)},
        };
    }

    private void countWordsClassic(final Path path) throws IOException {
        final Map<String, Integer> wordCounts = new HashMap<>();
        for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) {
            Integer oldCount = wordCounts.get(word);
            if (oldCount == null) {
                wordCounts.put(word, 1);
            } else {
                wordCounts.put(word, oldCount + 1);
            }
        }
    }

    private void countWordsMixed(final Path path) throws IOException {
        final Map<String, Integer> wordCounts = new HashMap<>();
        for (String word : new String(readAllBytes(path), StandardCharsets.UTF_8).split("\\W+")) {
            wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1);
        }
    }

    private void countWordsMixed2(final Path path) throws IOException {
        final Map<String, Integer> wordCounts = new HashMap<>();
        Pattern.compile("\\W+")
            .splitAsStream(new String(readAllBytes(path), StandardCharsets.UTF_8))
            .forEach(word -> wordCounts.merge(word, 1, (key, oldCount) -> oldCount + 1));
    }

    private void countWordsStream2(final Path tmpFile) throws IOException {
        Pattern.compile("\\W+").splitAsStream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8))
            .collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting()));
    }

    private void countWordsStream(final Path tmpFile) throws IOException {
        Arrays.stream(new String(readAllBytes(tmpFile), StandardCharsets.UTF_8).split("\\W+"))
            .collect(Collectors.groupingBy(Function.<String>identity(), HashMap::new, counting()));
    }

    interface TestMethod {
        void run() throws Exception;
    }
}

结果是:

type    length  diff
classic 4665s    +9%
mixed   4273s    +0%
mixed2  4833s    +13%
stream  4868s    +14%
stream2 5070s    +19%

请注意,我之前也使用TreeMaps进行了测试,但发现HashMaps更快,即使我之后对输出进行了排序.在Tagir Valeev在下面的评论中告诉我关于该Pattern.splitAsStream()方法之后,我也改变了上述测试.由于我得到了很大的变化结果,我让测试运行了很长一段时间,因为你可以看到上面几秒钟的长度来获得有意义的结果.

我如何判断结果:

1. 完全不使用流的"混合"方法,但使用Java 8中引入的回调的"merge"方法确实提高了性能.这是我所期望的,因为经典的get/put appraoch需要在HashMap中查找两次密钥,而且不再需要使用"merge"-approach.

2. 令我惊讶的Pattern.splitAsStream()是,相比之下,appraoch实际上更慢Arrays.asStream(....split()).我确实看了两个实现的源代码,我注意到split()调用将结果保存在一个ArrayList中,该ListList的大小为零,并根据需要进行放大.这需要许多复制操作,最后需要另一个复制操作将ArrayList复制到一个数组.但是"splitAsStream"实际上创建了一个迭代器,我认为可以根据需要进行查询,完全避免这些复制操作.我没有仔细查看将迭代器转换为流对象的所有源代码,但它看起来很慢,我不知道为什么.最后它理论上可能与CPU内存缓存有关:如果一遍又一遍地执行完全相同的代码,代码将更有可能在缓存中然后实际运行在大型函数链上,但这是一个非常疯狂的猜测我这边.它也可能是完全不同的东西.然而,splitAsStream MIGHT有更好的内存占用,也许它没有,我没有描述.

3. 流方法通常很慢.这并非完全出乎意料,因为发生了许多方法调用,包括例如无意义的事情Function.identity.但是我没想到这么大的差异.

作为一个有趣的旁注,我发现混合方法最快阅读和理解.对"合并"的调用并没有对我产生最大的影响,但如果你知道这个方法在做什么,那么对我来说似乎最具可读性,同时groupingBy命令对我来说更难以理解.我想有人可能会说这groupingBy是如此特别和高度优化,因此将其用于性能是有意义的,但正如此处所示,情况并非如此.

Answer 2

    Map<String, Integer> countByWords = new HashMap<String, Integer>();
    Scanner s = new Scanner(new File("your_file_path"));
    while (s.hasNext()) {
        String next = s.next();
        Integer count = countByWords.get(next);
        if (count != null) {
            countByWords.put(next, count + 1);
        } else {
            countByWords.put(next, 1);
        }
    }
    s.close();

这个数字"我只是"只有一个字