300k +文字列を含むリスト内の重複要素を特定する

Question

305899文字列（Webサイトのユーザー名）を含むリストがあります。すべての重複を削除すると、その数は172123文字列になります。

特定のString（ユーザー名）が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に保存し、自動的に頻度/回数を維持させます。これはボヘミアンのよりもさらに速くなっ

Answer 7

読むthis tutorialを理解するためにどのように多重集合作品/：

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