在包含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

您可以嘗試從用戶名中構建Trie結構。然後，找到不同元素（用戶名）的數量是微不足道的。 Trie的代碼有點複雜，所以你最好查看資源，看看如何完成實現。

在其他的想法，考慮到實際情況，你不應該有第一個這個重複列表。我的意思是，如果系統提供的用戶名是正確設計的，那麼重複將不存在在第一位。

Answer 3

看看你的第二個方法的這種變化工作速度快：

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 4

最好的解決方案是將所有元素添加到數組，然後對該數組進行排序。

然後，您可以迭代數組，並將重複項放在數組中相鄰。

Answer 5

你應該嘗試改進第一個實現：對於每個條目你迭代整個列表。如何像：

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 6

使用設計用於本機支持的數據結構。將用戶名保存在Multiset中，讓它自動爲您保留頻率/計數。

閱讀this tutorial瞭解如何多集作品/

Answer 7

這正好速度甚至超過了波西米亞的：

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 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);*/