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

Question

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

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

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

Спасибо!

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Существует также промежуточный подход, который вы также можете использовать.Когда поток запрашивает «отсортированный вид» карты, создайте копию карты и затем выполните сортировку по ней.

public List<Integer> getMaxFive() {
    Map<String, Integer> copy = null;
    synchronized(lockObject) {
        copy = new HashMap<String, Integer>(originalMap);
    }

    //sort the copy as usual
    return list;
}

В идеале, если к какому-либо состоянию (например, к этой карте) обращаются несколько потоков, вы инкапсулируете состояние за другим классом, чтобы каждый поток не обновлял карту напрямую.

Answer 4

Есть два способа сделать это легко:

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

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

Answer 5

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

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()

Answer 6

Если изменения редки, я бы реализовал некоторую SortedByValHashMap<K,V> extends HashMap <K,V>, аналогичную LinkedHashMap), в которой записи упорядочены по значению.

Answer 7

Пожалуйста, попробуйте другую структуру данных. Предположим, есть класс с именем MyClass, его атрибутами являются key (String) и value (int). MyClass, конечно, должен реализовать Comparable интерфейс. Другой подход заключается в создании класса с именем MyClassComparator, который расширяет Comparator.

Метод compareTo (независимо от того, где он находится) должен быть определен следующим образом: CompareTo (параметры) { возвращаемое значение2 - значение1; // по убыванию }

Остальное легко. Использование List и вызов метода Collections.sort (параметры) сделают часть сортировки.

Я не знаю, какой алгоритм сортировки использует Collections.sort (параметры). Но если вы чувствуете, что некоторые данные могут поступить со временем, вам потребуется сортировка вставок. Так как это хорошо для данных, которые почти отсортированы, и это онлайн .