как получить самые частые предметы

Я работаю над приложением, которое имеет большой массив, содержащий строки чисел,

transNum[20000][200]//this is the 2d array containing the numbers and always keep track of the line numbers

Я использую вложенный цикл для поиска наиболее часто встречающихся элементов. который

for(int i=0/*,lineitems=0*/;i<lineCounter;i++)
  {
      for(int j=0,shows=1;j<lineitem1[i];j++)
      {
          for(int t=i+1;t<lineCounter;t++)
          {
              for(int s=0;s<lineitem1[t];s++)
              {
                  if(transNum[i][j]==transNum[t][s])
                      shows++;
              }
          }

          if(shows/lineCounter>=0.2)
          {

              freItem[i][lineitem2[i]]=transNum[i][j];
              lineitem2[i]++;
          }
      }

  }

когда я выполнял тесты с использованием небольших входных массивов, таких как test[200][200], этот цикл работал нормально, и время вычислений было приемлемым, но когда я пытался обработать массив, содержащий 12000 строк, время вычислений было слишком большим, поэтому я я думаю, есть ли другие способы вычисления частых элементов, а не использование этого цикла. Я только что провел тест на 10688 строк, и время, чтобы получить все частые элементы, составляет 825805 мс, что слишком дорого.


java arrays frequency
person starcaller    schedule 02.10.2010    source источник
comment
что такое lineCounter и lineitem1?   -  person Starkey    schedule 02.10.2010
comment
lineCounter — это общее количество строк транзакций. и lineitem1 представляет собой массив, записывающий номера элементов (которые являются числами) в каждой строке.   -  person starcaller    schedule 02.10.2010
comment
Какова максимальная/минимальная стоимость предметов?   -  person Stan Kurilin    schedule 02.10.2010
comment
См. решение ниже. Было бы интересно посмотреть, какую производительность вы получите с ним.   -  person James P.    schedule 14.01.2011

Ответы (4)


arrow_upward
0
arrow_downward

Зависит от вашего ввода. Если вы также вставляете данные в тот же код, вы можете подсчитывать частые элементы по мере их вставки.

Вот псевдо-C решение:

int counts[1000000];

while(each number as n)
{
    counts[n]++;
    // then insert number into array
}

РЕДАКТИРОВАНИЕ №2: убедитесь, что во избежание непредвиденных результатов все элементы массива инициализируются нулем.

person Thomas O    schedule 02.10.2010
comment
Я использовал буферизованный считыватель для чтения строк чисел из файла .dat, а затем сохранял числа в массиве 2d. - person starcaller; 02.10.2010
comment
и какой смысл использовать этот массив подсчетов, чтобы получить количество подсчетов, мне все еще нужно сканировать массив с тем же временем, что и цикл - person starcaller; 02.10.2010
comment
Да, но, делая это одновременно с добавлением данных, вам не нужно снова сканировать массив, и это незначительно увеличит время, необходимое для добавления данных. - person Thomas O; 02.10.2010
comment
о, я понял, попробую, если получится, но думаю, что время сильно не уменьшится, спасибо :) - person starcaller; 02.10.2010
comment
@Thomas O: В java всегда будет 0) Вам не нужно инициализировать все элементы нулем. - person Stan Kurilin; 02.10.2010
comment
^ Как и в большинстве языков, таких как Python. Но если язык не определяет это или вы знаете, что массив пуст (например, вы использовали calloc), вы должны очистить массив. - person Thomas O; 02.10.2010
comment
@Thomas O: в Java примитивные типы автоматически инициализируются «пустыми» значениями. Нет никакого calloc(). Добро пожаловать в мир Java!) - person Stan Kurilin; 02.10.2010
comment
Да, я на самом деле программист Java. (Иногда я предпочитаю C из-за его чистой скорости, но Java проще и почти такая же быстрая.) Я не осознавал, что этот вопрос относится к Java, пока не посмотрел на теги, потому что синтаксис был очень похож на C. - person Thomas O; 02.10.2010

arrow_upward
1
arrow_downward

Имейте в виду, что в лучшем случае это алгоритм O (n ^ 2), а может быть и хуже. Это означает, что количество операций пропорционально количеству элементов в квадрате. После определенного количества строк производительность будет быстро снижаться, и вы ничего не сможете с этим поделать, кроме как улучшить алгоритм.

person Tony Ennis    schedule 02.10.2010
comment
да, я знаю, что этот цикл отнимает много времени, дело в том, какой другой алгоритм можно использовать, чтобы разобраться с этим - person starcaller; 02.10.2010
comment
Как вы получаете данные? Изменяется ли он после приобретения? - person Tony Ennis; 02.10.2010
comment
изначально строки чисел считывались из файла .dat, и я использовал буферизованный считыватель для чтения всех чисел в массив 2d (чтобы отслеживать номера строк). - person starcaller; 02.10.2010

arrow_upward
0
arrow_downward

Реализация Multiset от Google. В таких случаях может быть полезен проект Guava. Вы можете хранить элементы там, а затем извлекать набор значений с подсчетом каждого вхождения.

person oiavorskyi    schedule 02.10.2010
comment
но я должен отслеживать, в какой строке появляется определенный элемент - person starcaller; 02.10.2010
comment
Затем вы можете использовать Multimap и вызывать метод put(item, line number). Тогда у вас будет возможность не только получить количество каждого элемента, но и значения отдельных элементов. - person oiavorskyi; 02.10.2010
comment
Кроме того, реализация TreeMultimap просто позволит вам установить Comparator для ключей, и в этом случае вы сможете сортировать элементы по количеству связанных вхождений. - person oiavorskyi; 02.10.2010

arrow_upward
0
arrow_downward

Дал алгоритм для этого некоторые мысли. Вот решение, которое я придумал:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class NumberTotalizerTest {

    public static void main(String args[]) {

        HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();

        // Number input
        Random randomGenerator = new Random();
        for (int i = 1; i <= 50; ++i ) {
            int randomInt = randomGenerator.nextInt(15);
            System.out.println("Generated : " + randomInt);

            Integer tempInt = hashMap.get(randomInt);

            // Counting takes place here
            hashMap.put(randomInt, tempInt==null?1:(tempInt+1) );
        }

        // Sorting and display
        Iterator itr =  sortByValue(hashMap).iterator();

        System.out.println( "Occurences from lowest to highest:" );

        while(itr.hasNext()){
            int key = (Integer) itr.next();

            System.out.println( "Number: " + key + ", occurences: " + hashMap.get(key));
        }
    }

     public static List sortByValue(final Map m) {
        List keys = new ArrayList();
        keys.addAll(m.keySet());
        Collections.sort(keys, new Comparator() {
            public int compare(Object o1, Object o2) {
                Object v1 = m.get(o1);
                Object v2 = m.get(o2);
                if (v1 == null) {
                    return (v2 == null) ? 0 : 1;
                }
                else if (v1 instanceof Comparable) {
                    return ((Comparable) v1).compareTo(v2);
                }
                else {
                    return 0;
                }
            }
        });
        return keys;
    }
}
person James P.    schedule 14.01.2011