1

Javaでシークレットk-匿名化アルゴリズムを実装しようとしています。このアルゴリズムの一部は、特定のテーブルの頻度セットの構築です。テーブルの列は毎回異なるため、テーブルをObject []のArrayListとして表すことにしました。ここで、Object[]のサイズは列の数です。このオブジェクトには、各列の各行の値を格納します。

次の方法を使用して度数分布表を作成しようとしています。

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分かかります-これが正常かどうかはわかりません）。度数分布表を作成するより速い方法はありますか？

4

2 に答える 2

3

では絶対に使用removeしないでくださいArrayList。これは O(size()) です。また、カウント変数は、インクリメントするたびにラップおよびアンラップされます。その型を作成し、最後にのみintラップします。Integer

保存するオブジェクトのタイプについて何も知らなくても、メソッドを想定しequalsてhashCode再定義します。次に、オブジェクトの配列をクラス Row にラップし (とにかく実行するのは良いことです)、Row の equals と hashCode を再定義し (Arrays.equals と Arrays.hashCode を使用)、それぞれの出現回数を数えます。を使用して 1 つのパスで行

HashMap<Row, Integer> count;


for (Row row : table) {
    if (count.containsKey(row)) {
        count.put(row, count.get(row) + 1);
    } else {
        count.put(row, 1);
    }
}
于 2011-01-10T11:30:42.773 に答える
1

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

または、代わりにハッシュテーブルを使用してカウントを行います。それは線形時間計算である必要があります。

于 2011-01-10T11:10:15.810 に答える