Расположение элементов списка (с повторяющимися элементами) в соответствии с частотой появления

Question

Что было бы хорошим способом упорядочить элементы списка (с повторяющимися элементами) в соответствии с частотой их появления в списке.

Мне нужно использовать 5 наиболее часто встречающихся элементов вlist.

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

Answer 1

Вы можете использовать Гуава Multiset и упорядочить его по частоте

---

А по поводу производительности. Конечно, это зависит от того, сколько у вас различных значений, но этот тестовый код занял около секунды на моем компьютере. И я бы сказал, что это достаточно разумно для 10 M предметов:

Multiset<Integer> set = HashMultiset.create();
int amount = 10000000;
Random random = new Random();
for (int i = 0; i < amount; i++) {
    set.add(Integer.valueOf(random.nextInt(255)));
}
TreeSet<Entry<Integer>> sortedEntries = Sets.newTreeSet(
        new Comparator<Entry<Integer>>() {
    public int compare(Entry<Integer> a, Entry<Integer> b) {
        return Ints.compare(a.getCount(), b.getCount());
    }
});
Iterables.addAll(sortedEntries, set.entrySet());
for (Entry<Integer> entry : Iterables.limit(sortedEntries, 5)) {
    System.out.println(entry.getElement());
}

Answer 2

Как насчет этого подхода?

ведите карту, в которой хранится количество

public static Map  <Foo,Integer>;

---

class Foo implements Comparator<Foo>{  
      private Bar element;


      public int compare(Foo f1, Foo f2){
       return SomeClass.map.get(f1) - SomeClass.map.get(f2);
      }

    }

просто обновить карту с обновлением в list.

Оберните доступ к списку принудительно с помощью addFooToList(), removeFooFromList() и инкапсулируйте там логику обновления карты.

Answer 3

Любая сортировка на основе сравнения повлечет за собой O(N log N) или худшую временную сложность, поэтому (асимптотически) это не очень хорошие советы.

Ваш подход имеет O(N) временную сложность, и это лучшее, что вы можете получить,Вы можете попытаться понизить константу (в настоящее время вы делаете примерно 6*N доступ к элементам списка).

Я бы сделал это в две итерации, например: сначала посчитайте частоты, используя HashMap.Затем, переберите записи на карте и сохраните упорядоченный 5-элементный массив из 5 наиболее часто встречающихся значений, которые вы когда-либо видели.С каждым новым элементом проверьте, является ли значение более распространенным, чем 5-е наиболее распространенное на данный момент, и при необходимости обновите «Топ 5».

---

ОБНОВЛЕНИЕ Более простое решение, той же сложности сложности .Сначала рассчитайте частоты, используя HashMap.Затем поместите все записи в PriorityQueue и вставьте пять значений.Записи должны быть парами значение-частота, сопоставимыми по частоте (как в решении @ Jigar).Такой порядок не будет «согласован с равными» (см. Comparable для объяснения), но это нормально.

Answer 4

Я бы также использовал HashMap.Я нашел некоторый код, где я сделал именно это:

HashMap<String, Integer> counts = new HashMap<String, Integer>();

void increment(String s) {
    Integer oldCount = counts.get(s);
    if (oldCount == null) {
        counts.put(s, 1);
    } else {
        counts.put(s, oldCount + 1);
    }
}

Список элементов:

Map.Entry<String, Integer>[] array = new Map.Entry[counts.size()];
counts.entrySet().toArray(array);
Arrays.sort(array, new Comparator<Map.Entry<String, Integer>>() {
    public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
        return b.getValue() - a.getValue();
    }
});
int x = 0, min = 0;
for (Map.Entry<String, Integer> el : array) {
    String k = el.getKey();
    println("Count: " + el.getValue() + "\n" + k + "\n\n");
}