删除Java中重复项的最快速有效的方法

Question

我想删除数据中的重复值.我知道它经常在stackoverflow中被观察到的问题,但我的问题有点不同,因为现在我正在处理非常大的数据.因此,我必须在代码中考虑最多的执行时间.

如下面的代码片段,我做了一个简单的代码来删除重复的值.

// Suppose that the dataset is very huge so that
// multi-node resources should be necessary.    
String[] data = new String[10_000_000];

HashMap<String, String> uniqueItems = new HashMap<>();

for (int i = 0; i < data.length; i++) {
    if (uniqueItems.containsKey(data[i])) {
        uniqueItems.remove(data[i]);
        uniqueItems.put(data[i], "inserted");
    } else {
        uniqueItems.put(data[i], "inserted");
    }
}

但是,我不喜欢它,因为我认为其他更好的数据结构或不同的算法可以有效地删除重复的比我的代码.

所以我想寻找更好的方法来在数据很大时快速删除重复的值.
如果您能让我知道删除重复值的最快方法,我将不胜感激.

而且,我想知道重复值的数量是否会影响性能.我的意思是如果重复值是原始数据的50%,那么最佳算法和数据结构的选择将会改变吗？如果是这样,我想找到一种在一般情况下可以取得良好性能的方法.

Answer 1

转换uniqueItems为a HashSet<String>和你的for循环简单地:

uniqueItems.add(data[i]);

如果add返回true则您插入了一个唯一的字符串; false如果重复.

在最好的情况下,两种算法都应该在O(n)时间内运行,但是HashMap当你不关心值(对于给定的密钥)时,使用一个算法是愚蠢的,浪费资源.A HashSet更适合这种情况.

您还可以尝试TreeSet<String>查看哪种方法最适合您的特定数据集.鉴于JDK 8的新HashSet实现,可能会更糟糕:过度拥挤的存储桶会自动存储为迷你树集,即使在散列函数表现不佳时也能提供有竞争力的性能.(此优化仅适用于Comparable类型等String.)

蛮力搜索数组.在一个简单的基于数组的算法中,在插入每个元素之前搜索整个数组,会产生非常糟糕的O(n²)性能.

因此,您可能会首先对数据进行排序,将重复的元素放在彼此附近.这样可以获得更快的O(n log n)性能,但仍然落后HashMap/HashSet于一般情况下的版本.

线性是理论上最好的.如果不至少访问每个元素一次,则无法检测所有重复项.因此,我们目前的O(n)时间复杂度实际上是您在这里可以做到的最好的.

当然,你总是可以尝试削减Big O表示法中的一些隐藏常量,但是你不会得到渐近更好的算法.