Блог

Мне нужно найти верхние теги k из потока тегов в любой момент времени во время потока.

Я могу найти верхние теги K в конце потока, используя HashMap и PriorityQueue размера K. Но я не уверен, как изменить этот подход, чтобы находить верхние теги во время потока тегов, т. Е. Если тег уже входит в десятку лучших, и просто обновите его количество, вместо того, чтобы снова добавлять тот же тег с новым количеством.

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

Вы можете сохранить этот список верхнего K, если хотите, и всякий раз, когда обновляется какой-либо другой элемент, вы проверяете, превышает ли его новое количество значение для наименьшего элемента в верхнем K. Если это так, то замените этот наименьший элемент на недавно обновленный элемент. Это должно быть достаточно легко сделать с помощью вспомогательной структуры данных. Основным недостатком здесь является объем памяти, который требуется для хранения копии верхних K элементов.

Другим способом сделать это было бы сохранить вашу хэш-карту с подсчетами и дополнительный связанный список, который упорядочивает вещи по убыванию количества. Данные в хэш-таблице содержат ссылки на узлы связанного списка. Всякий раз, когда элемент обновляется, вы обновляете его количество, а затем сравниваете его количество с количеством элемента непосредственно перед ним в связанном списке. Если новое количество больше, чем количество предыдущего элемента, переместите элемент вверх по списку, чтобы сохранить его в порядке. Конечно, вам, возможно, придется перемещать его несколько раз. По сути, это сортировка по вставке.

Преимущество такого подхода заключается в том, что верхние K элементов всегда находятся в начале списка. Недостатком является потенциальная производительность. Если у вас много элементов, а диапазон подсчетов невелик, каждое обновление может занять O (n) времени. Вы можете немного ускорить это, отслеживая следующий более высокий элемент, чтобы, например, если есть 100 элементов со счетом 1, у вас была ссылка на последний элемент со счетом 2. Поэтому, когда вы увеличиваете количество элементов с количеством 1, вам не нужно просеивать его по всем элементам с количеством 1. Это потребует от вас больше памяти (в худшем случае, O (n) памяти), но это сделает вставку O (1) и сохранит порядок в списке.

Существуют и другие возможности, все из которых предусматривают компромиссы между скоростью и использованием памяти. То, что вы выбираете, зависит от того, сколько памяти вы хотите потратить и насколько быстро вы хотите, чтобы это было.