识别包含 300k+ 的列表中的重复元素弦乐

Question

我有一个包含 305899 个字符串的列表（这是网站的用户名）。删除所有重复项后，数字降至 172123 个字符串。

我想找出特定字符串（用户名）在该 ArrayList 中重复了多少次。我写了一个简单的冒泡排序类型逻辑，但是太慢了。

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();
    int duplicate = 0;
    int size = userNameList.size();
    for (int i = 0; i < size - 1; i++) {
        duplicate = 0;
        for (int j = i + 1; j < size; j++) {
            if (userNameList.get(i).equals(userNameList.get(j))) {
                duplicate++;
                userNameList.remove(j);
                j--;
                size--;

            }
        }
        numberOfPosts.put(userNameList.get(i), duplicate);
    }

    return numberOfPosts;
}

然后我把它改成这样：

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    Set<String> unique = new HashSet<String>(userNameList);

    for (String key : unique) {
        numberOfPosts.put(key, Collections.frequency(userNameList, key));
    }

    return numberOfPosts;
}

这也很慢。当我说慢时，需要 30 多分钟才能浏览完列表。

有没有其他有效的方法来处理这个问题？只是减少查找和计算重复元素所需的时间？

Answer 1

您的 findNumberOfPosts 方法是在正确的轨道上，但您的实现正在执行大量不必要的工作。
试试这个：

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    for (String userName : userNameList) {
        Integer count = numberOfPosts.get(userName);
        numberOfPosts.put(userName, count == null ? 1 : ++count);
    }
    return numberOfPosts;
}

在大多数机器上这应该在几秒钟内执行。

Answer 2

看看第二种方法的这种变体是否运行得更快：

private static Map<String, Integer> findNumberOfPosts(
        List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    for (String name : userNameList) {
        Integer count = numberOfPosts.get(name);
        numberOfPosts.put(name, count == null ? 1 : (1 + count));
    }

    return numberOfPosts;
}

它有一些装箱/拆箱开销，但运行速度应该比您正在做的快得多，您正在做的事情需要迭代每个唯一名称的整个名称列表。

Answer 3

您可以尝试根据用户名构建 Trie 结构。那么找到不同元素（用户名）的数量就很简单了。 Trie 的代码有点复杂，因此您最好查找资源以了解如何实现。

另一方面，考虑到实际情况，您一开始就不应该有这个重复的列表。我的意思是，如果提供用户名的系统设计得当，那么首先就不会存在重复项。

Answer 4

这比 Bohemian 的速度还要快：

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {

        Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

        for (String userName : userNameList) {
            if (!numberOfPosts.containsKey(userName)) {
                numberOfPosts.put(userName, Collections.frequency(userNameList, userName));
            }
        }

        return numberOfPosts;
    }

Answer 5

最好的解决方案是将所有元素添加到数组中，然后对该数组进行排序。

然后你可以迭代数组，重复项将被放置在数组中彼此相邻的位置。

Answer 6

您应该尝试改进第一个实现：对于每个条目，您都将迭代整个列表。怎么样：

Map<String, Integer> map;
for (String username : usernames) {
    if (!map.containsKey(username)) {
        map.put(username, new Integer(0));
    } else {
        map.put(username, new Integer(map.get(username).intValue() + 1));
    }
}
return map;

Answer 7

使用旨在本地支持此操作的数据结构。将用户名存储在 Multiset 中并让它自动为您维护频率/计数。

阅读本教程了解多重集的工作原理/

Answer 8

以下是删除重复项并计算列表中重复元素数量的最佳且方便的方法。不需要有额外的逻辑。

List<String> userNameList = new ArrayList<String>();
// add elements to userNameList, including duplicates

userNameList.add("a");
userNameList.add("a");
userNameList.add("a");
userNameList.add("a");

userNameList.add("b");
userNameList.add("b");
userNameList.add("b");
userNameList.add("b");

userNameList.add("c");
userNameList.add("c");
userNameList.add("c");
userNameList.add("c");

int originalSize=userNameList.size();

HashSet hs = new HashSet();   //Set would handle the duplicates automatically.
hs.addAll(userNameList);
userNameList.clear();
userNameList.addAll(hs);

Collections.sort(userNameList);  //Sort the List, if needed.

//Displays elements after removing duplicate entries.
for(Object element:userNameList)
{
    System.out.println(element);
}

int duplicate=originalSize-userNameList.size();

System.out.println("Duplicate entries in the List:->"+duplicate); //Number of duplicate entries.

 /*Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();   //Store duplicate entries in your Map using some key.
 numberOfPosts.put(userNameList.get(i), duplicate);

 return(numberOfPosts);*/