Построение таблицы частот объектов в ArrayList <Object[]>

Question

Я пытаюсь реализовать Incognito k-anonymization algorithm в Java. Часть этого алгоритма - это построение частоты для данной таблицы. Столбцы таблицы меняются каждый раз, поэтому я решил представить таблицу как 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

Никогда не используйте remove на ArrayList, это O (размер()). Кроме того, ваша переменная count обертывается и распаковывается каждый раз, когда вы увеличиваете ее. Сделайте свой тип int и оберните его в Integer только в самом конце.

Не зная ничего о типе объектов, которые вы храните, я предполагаю, что методы equals и hashCode переопределены для них. Тогда самое лучшее, что приходит в голову, заключается в том, чтобы обернуть массив Object в класс Row (это хорошо сделать в любом случае), переопределить equals и hashCode for Row (используя 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)

или вместо этого используйте хеш-таблицу. Это должно быть линейное вычисление времени.