java - 构建 ArrayList 中对象的频率表

Question

我尝试执行 Incognito k-anonymization algorithm在 java 。该算法的一部分是给定表的频率集构造。表的列每次都不同，所以我决定将表表示为 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 分钟才能运行——我不知道这是否正常)。有没有更快的构造频率表的方法？

Answer 1

永远不要在ArrayList 上使用remove，它是O(size())。此外，每次递增时，您的 count 变量都会被包装和解包。将其类型设为 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);
    }
}