Поиск наивысших значений n на карте

Question

Поиск наивысших значений n на карте

У меня есть большая карта String-> Integer, и я хочу найти 5 самых высоких значений на карте. Мой текущий подход включает в себя перевод карты в список массивов объектов пары (ключ, значение), а затем сортировку с помощью Collections.sort () перед тем, как взять первые 5. Значение ключа может обновляться в процессе работы.

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

Могу ли я дать несколько предложений / альтернатив по оптимизации, пожалуйста? Я рад рассмотреть различные структуры данных, если есть преимущества.

Спасибо!

7

java algorithm data-structures optimization

задан Carl Manaster 31 August 2010 в 15:17

5 ответов

Другие вопросы по тегам:

java algorithm data-structures optimization

Похожие вопросы:

score 3 · Answer 1

Вы можете использовать две Карты:

// Map name to value
Map<String, Integer> byName

// Maps value to names
NavigableMap<Integer, Collection<String>> byValue

и следить за их синхронизацией (возможно, оберните обе в другой класс, который отвечает за размещение, получение и т. д.). Для самых высоких значений используйте byValue.navigableKeySet().descendingIterator().

score 1 · Answer 2

Есть два простых способа сделать это:

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

Если вы хотите получить неизвестное или большое количество самых высоких значений, вам подойдет первый метод. Если у вас есть фиксированное небольшое количество значений для извлечения, второе может быть легче понять для некоторых программистов. Лично я предпочитаю первый способ.

score 1 · Answer 3

Я бы создал такой метод:

private static int[] getMaxFromMap(Map<String, Integer> map, int qty) {
    int[] max = new int[qty];
    for (int a=0; a<qty; a++) {
        max[a] = Collections.max(map.values());
        map.values().removeAll(Collections.singleton(max[a]));
        if (map.size() == 0)
            break;
    }
    return max;
}

Воспользовавшись преимуществами Collections.max() и Collections.singleton()

score 5 · Answer 4

Ну, чтобы найти 5 самых высоких значений на карте, вы можете сделать это за O(n) раз, где любая сортировка медленнее.

Самый простой способ — просто выполнить цикл for по набору записей карты.

for (Entry<String, Integer> entry: map.entrySet()) {
    if (entry.getValue() > smallestMaxSoFar) 
        updateListOfMaximums();
}

score 0 · Answer 5

Если модификации редки, я бы реализовал SortedByValHashMap расширяет HashMap , аналогично LinkedHashMap), в котором записи упорядочиваются по значению .