java - 在大文件中查找字数并对结果进行排序

Question

我有一个包含各种字符串的大文件。我需要解析文件并找到文件中存在的各种单词的字数。之后，我需要按单词的计数顺序排列单词。

我的方法是解析文件并将单词存储在 Hashmap 中，其中单词是键，计数是值。随着我们继续解析文件，计数将被更新。解析完成后，我将根据计数对集合进行排序。

上面的方法非常简单，并没有考虑到文件很大。

我应该对处理大文件的方法进行哪些更改？

Answer 1

HashMap如果您要拥有多个线程，请不要使用 a ，ConcurrentHashMap而是使用 a ( javadoc )。

Integer如果值已经存在，您仍然需要对更新值进行某种检查。有关该过程的更多详细信息，请参阅这篇文章。

填充地图后，请参阅此帖子以对地图进行排序。

Answer 2

首先我会使用 aMap来确定字数：

    String[] words = {"one", "two", "three", "two", "three", "three"};
    Map<String, Integer> map = new HashMap<String, java.lang.Integer>();
    for (String word : words) {
        int count = 0;
        if (map.containsKey(word)) {
            count = map.get(word);
        }
        map.put(word, ++count);
    }
    System.out.println(map);
    --> output: {two=2, one=1, three=3}

然后，我将使用一个TreeMap或一个新的“自定义”键/值类按计数排序：

使用TreeMap：

private static void sortUsingTreeMap(Map<String, Integer> map) {
    TreeMap<String, Integer> sorted = new TreeMap<String, Integer>(new MyComparator(map));
    sorted.putAll(map);
    System.out.println(sorted);
}

static class MyComparator implements Comparator<String> {
    private Map<String, Integer> map;

    MyComparator(Map<String, Integer> map) {
        this.map = map;
    }

    @Override
    public int compare(String o1, String o2) {
        return map.get(o1).compareTo(map.get(o2));
    }
}
--> output: {one=1, two=2, three=3}

使用新的键/值类：

private static void sortUsingKeyValueClass(Map<String, Integer> map) {
    class KeyValue implements Comparable<KeyValue> {
        private final Integer count;
        private final String word;

        public KeyValue(Integer count, String word) {
            this.count = count;
            this.word = word;
        }

        @Override
        public int compareTo(KeyValue o) {
            return count.compareTo(o.count);
        }

        @Override
        public String toString() {
            return word + "=" + count;
        }
    }

    List<KeyValue> keyValues = new ArrayList<KeyValue>();
    for (String word : map.keySet()) {
        keyValues.add(new KeyValue(map.get(word), word));
    }
    Collections.sort(keyValues);
    System.out.println(keyValues);
}
--> output: [one=1, two=2, three=3]

我还要补充一点，我会推迟将线程添加到混合中，直到我发现它在性能方面是必要的。正如这里的其他人所说，通过同时处理结果不会保存一个糟糕的实现。

Answer 3

因此，为了让您更清楚地了解我在评论中的陈述：

假设您有大文件。需要 N 次操作才能以逐字的方式阅读所有内容。到目前为止，这将是您的瓶颈，因为 I/O 通常很慢。

对于您的计数方案，您使用Map<String, Integer>. 您看到的每个单词都放入 Map 中，如果多次遇到特定单词，则加 1。通常，特定键值对的加法是常数时间（HashMap），并弄清楚是否可以是否在地图中添加新Integer的也是恒定的。

因此，计算文件中单词的整体运行时性能将是 O(N) + C，其中 N 主要是由于 I/O。

现在，假设您使用十个线程。您将大文件切成十块，并让每个线程将它们的值插入到ConcurrentHashMap. 您的整体运行时复杂性没有改变，只是它（可能）减少了 10 倍。

带有额外线程的运行时间将为 O(t(1/10)N) + C，但仍会减少到 O(N) + C。

唯一能让它更有效的方法是，如果你能改变所采用的线性扫描方法，使其比线性时间更有效。

Answer 4

正如评论中所说，线程对于您希望您的解决方案比其他人的解决方案快一点的决胜局情况很有用。如果线程内部运行的速度真的很慢，那么线程就没用了。

对于问题的第一部分，哈希图将是时间复杂度的最佳选择。

对于您问题的第二部分，我将使用一个集合、一个二维数组和您在第一部分中使用的数据结构。如果您再次解析文件，将每个新单词添加到集合中并在您已经创建的哈希图中检查其字数，您可以将每个单词存储在其字数的索引位置。之后，只需向后遍历数组，您就会按照单词的计数顺序获得单词。