Структура данных для кеширования наиболее частых элементов

Question

Предположим, я прочитал поток целых чисел. Одно и то же целое число может появляться более одного раза в потоке. Теперь я хотел бы сохранить кеш из N целых чисел, которые появлялись наиболее часто. Кеш отсортирован по частоте элементов потока.

Как бы вы реализовали это на Java?

Answer 1

Вы хотите использовать двоичное индексированное дерево, код в ссылке для C ++ и должен быть достаточно простым для преобразования в Java (AFAICT код будет таким же):

Paper PeterФенвик

Реализация на C ++

Answer 2

public class MyData implements Comparable<MyData>{
  public int frequency = 0;
  public Integer data;
  @Override
  public int compareTo(MyData that) {
    return  this.frequency - that.frequency;
  }

}

Хранить в PriorityQueue

Answer 3

Используйте Гуава Multiset и сортируйте по частоте

Answer 4

Знаете ли вы диапазон чисел?Если это так, возможно, имеет смысл использовать массив.Например, если бы я знал, что диапазон чисел был между 0 и 10, я бы создал массив размером 10. Каждый элемент в этом массиве будет подсчитывать количество раз, которое я видел данное число.Тогда вам просто нужно запомнить наиболее часто встречающееся число.

например,

array[10];
freq_index = -1;
freq_count = -1;

readVal(int n){
  array[n]+=1;
  if array[n] > freq_count
    freq_index = n;
    freq_count = array[n];
}

Конечно, такой подход плох, если распределение чисел редкое.

Я бы попробовал приоритетную очередь.

Answer 5

Создайте объектную модель для int, внутри создайте свойство Count. Создайте коллекцию SortedVector, расширяющую коллекцию Vector. Каждый раз, когда возникает целое число, добавляйте его в вектор, если оно не существует. Иначе, найдите его, обновите свойство count + = 1, затем вызовите Collections.sort (this) в вашем векторе.