java - 在大型数据集中查找唯一条目的最有效方法

Question

首先，我要明确表示这是一项作业，我不期望完整的编码答案。我所寻求的只是建议，也许还有对我有帮助的代码片段。

所以，我正在读取大约 900,000 个单词，所有单词都存储在 arrayList 中。我需要使用 java 中的排序数组(或数组列表)来计算唯一单词的数量。

到目前为止，我只是循环遍历给定的 arrayList 并使用

Collections.sort(words); 

和 Collections.binarySearch(words, wordToLook); 实现如下:

OrderedSet set = new OrderedSet();
    for(String a : words){
        if(!set.contains(a)){
            set.add(a);
        }
    }

和

public boolean contains(String word) {
    Collections.sort(uniqueWords);
    int result = Collections.binarySearch(uniqueWords, word);

    if(result<0){
        return false;
    }else{
        return true;
    }
}

这段代码的运行时间约为 60 秒，但我想知道是否有更好的方法来做到这一点，因为每次添加元素时运行排序似乎效率很低(但如果我要使用二进制，当然是必要的)搜索)。

任何形式的反馈将不胜感激。谢谢。

Answer 1

因此，您需要使用排序数组。没关系，因为您(还没有)在现实世界中编程。

我会建议两种选择:

第一个使用二分搜索(您在当前代码中使用)。

我将创建一个包含两个字段的类:单词(字符串)和该单词的计数(整数)。您将构建这些类的排序数组。

从一个空数组开始，并在阅读每个单词时向其中添加。对于每个单词，对您正在构建的数组中的单词进行二分搜索。搜索将找到包含该单词的条目(并且您将增加计数)，或者您将确定该单词尚未在数组中。

当你的二分搜索结束而没有找到单词时，你将创建一个新对象来保存单词+计数，并将其添加到搜索结束位置的数组中(注意确保你的逻辑确实将其放入放在正确的位置以保持列表排序)。当然，您的新单词计数设置为 1。

另一种选择:

将所有单词读入列表并对其进行排序。排序后，所有重复项将在列表中彼此相邻。

您将沿着这个排序列表走一次，并创建一个单词+计数列表。如果您看到的下一个单词与上一个单词+计数相同，则增加计数。如果是新单词，则将新单词+计数添加到结果列表中，其中 count=1。