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())。此外，每次递增时，您的 count 变量都会被包装和解包。制作它的类型并仅在最后将其int包裹起来。Integer

在不知道您存储的对象类型的情况下，我假设方法equals并hashCode为它们重新定义。然后想到的最好的事情是将Object的数组包装到一个类Row中（无论如何这是一件好事），为Row重新定义equals和hashCode（使用Arrays.equals和Arrays.hashCode）并计算每个的出现使用 a 进行一次传球

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 回答