ArrayListのオブジェクトの頻度テーブルの作成<Object[]>

Question

私はIncognito k-anonymization algorithmをJavaで実装しようとしています。 このアルゴリズムの一部は、指定されたテーブルの頻度セット構成です。テーブルのカラムは毎回変わるので、テーブルをObject []のArrayListとして表現することにしました。ここで、Object [] sizeはカラムの数です。このオブジェクトでは、各列の各行の値を格納します。

私は、以下の方法を用いて周波数テーブルを構築しよう：

ArrayList<Object[]> table = new ArrayList<Object[]>(); 
....// table filling//..... 
ArrayList<Object[]> frequencySet = new ArrayList<Object[]>(); 
for(int i=0;i<table.size();i++) 
    { 
     Integer count = 1; 
     int j = 0; 
     for(j=i+1;j<table.size();j++) 
     { 
      if(Arrays.equals(table.get(i), table.get(j))) 
      { 
       //System.out.println(i+" equals to "+j); 
       count++; 
       table.remove(j); 
       j = j-1; 
      } 
     } 
     int size = arguments.size()+1; 
     Object[] anObject = new Object[size]; 
     System.arraycopy(table.get(i), 0, anObject, 0, arguments.size()); 
     anObject[size-1] = count; 
     frequencySet.add(anObject); 
    } 

問題は、アルゴリズムが非常に遅いことである、と私はほとんどの時間をこの方法で消費されていることを考え出しました。 （100.000データの場合、実行するのに13分必要です - これが正常かどうかわかりません）。頻度表を作成するためのより速い方法がありますか？

Answer 1

ArrayListにはremoveを使用しないでください.O（サイズ）です。また、カウント変数は、インクリメントするたびにラップされラップ解除されます。そのタイプをintにして、最後にIntegerに包んでください。

保存するオブジェクトの種類について知らずに、私はequalsとhashCodeのメソッドが再定義されていると仮定します。次に、Objectの配列をクラスRowにラップします（とにかくするのは良いことです）、RowのequalsとhashCode（Arrays.equalsとArrays.hashCodeを使用）を再定義し、それぞれの出現を数えます

HashMap<Row, Integer> count;

for (Row row : table) { 
    if (count.containsKey(row)) { 
     count.put(row, count.get(row) + 1); 
    } else { 
     count.put(row, 1); 
    } 
} 

Answer 2

これらを並べ替え、その後にループで再発生をカウントします。それはO（n log n）

にダウンさせるか、代わりにハッシュテーブルを使用してカウントします。それは線形時間計算でなければなりません。