Построение таблицы частот Объектов в ArrayList - PullRequest
Новая
       4

Построение таблицы частот Объектов в ArrayList

1 голос
/ 10 января 2011

Я пытаюсь реализовать Алгоритм инкогнито k-анонимизации в Java.Частью этого алгоритма является построение набора частот для данной таблицы.Столбцы таблицы меняются каждый раз, поэтому я решил представить таблицу в виде ArrayList объекта Object [], где размер 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 минут для запуска - я не знаю, нормально ли это).Есть ли более быстрый способ построения таблицы частот?

Ответы [ 2 ]

3 голосов
/ 10 января 2011

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

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

Сортируйте их, а затем посчитайте повторения с помощью цикла.Это снизит его до O (n log n)

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

...