java - リストをグループ化し、そのリストをJavaで出現順にソートします

Question

私は名前 (名と姓) の大きなリストを持っています: 例:

{ john a, david x, marry u, john b, david y, john c}

結果は次のようになります (名前でグループ化され、名前の頻度で並べ替えられ、姓は考慮されません)。

john b
john a
john c
david x
david y
marry u

非常に大きなリスト (30M インスタンス) があるため、アルゴリズムの複雑さを考慮する必要があります。

Answer 1

Map<String, Integer> freq = new HashMap<String, Integer>();
for (String s: names):
    first_name = Arrays.asList(s.split()).get(0).toLowerCase()
    int count = freq.containsKey(name) ? freq.get(name) : 0;
    freq.put(name, count + 1);

Arrays.sort(names, new Comparator<String>() {
  public int compare(String s1, String s2) {
    int c = freq.get(Arrays.asList(s1.split()).get(0).toLowerCase()) - Arrays.asList(s2.split()).get(0).toLowerCase();
    return c;
  }
});

基本的に、名の出現頻度のヒストグラムを作成し、それをカスタム コンパレータとして使用します。

たった2つの操作なので、問題の最も複雑な領域の複雑さによって制限されます。また、ヒストグラムの生成は線形であるため、並べ替えでnlognできる最善の方法であると私が信じている並べ替え機能によって制限されます。