Топ-10 в потоке пар ключевых значений за последний час

Question

Допустим, есть поток пар значений ключа с отметкой времени, и мы хотели бы найти 10 лучших ключей с наибольшим значением за последний час. (Значение ключа за последний час представляет собой сумму всех значений, переданных из этого конкретного ключа).

Я попытался придумать решение, которое выглядит так: http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/. Но я не могу привнести время в картину, не обойдя меня тяжелой сложностью во времени. Любые идеи приветствуются.

Answer 1

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

При том, что ваш процесс добавления наблюдения выглядит следующим образом:

1. Удалить любые замечания, которые в настоящее время для удаления. (Подробнее о том, как это сделать через минуту.)
2. Добавить наблюдение в очередь для удаления, с отметкой времени, чтобы удалить его.
3. Ключ, найдите текущее общее значение в хеш значения по ключу.
4. Клавиша value + найдите запись в сбалансированном двоичном дереве и удалите ее.
5. Обновить текущее общее значение в хеш значения по ключу.
6. Вставьте новое значение в хэш значения по ключу.

Чтобы найти лучшие 10, вам необходимо следовать по тому же пути.

1. Удалите все замечания, которые в настоящее время необходимо удалить. (Подробнее о том, как это сделать через минуту.)
2. Посмотрите на сбалансированное двоичное дерево для 10 лучших наблюдений.

И удалить наблюдения, которые в настоящее время для удаления, в то время как верхний элемент в очереди, чтобы удалить более чем один час старый:

1. Поп пару ключ/значение из очереди, чтобы удалить.
2. Найти значение в хэше полного значения по ключу.
3. Удалить значение из сбалансированного двоичного дерева.
4. Обновить общее значение в хэше полного значения по ключу.
5. Вставьте новое значение/ключ в сбалансированный двоичный ключ.

ОК, так каковы затраты и время?

Мы сохраняем 3 копии каждого наблюдения. Некоторые из сложных структур данных с накладными расходами. Таким образом, мы используем, возможно, 5 раз пространство для событий последнего часа. На наблюдение много операций, но они все логарифмичны. Фактически, общая сумма усилий на наблюдение оценивается как O(log(n)) как для поддержания структуры данных в актуальном состоянии, так и для возврата 10 лучших.

Теперь, если накладные расходы становятся слишком много, простое решение - сделать его приблизительным. Существует тонна аппроксимационных алгоритмов, но проще всего сделать так, чтобы включение в структуру данных было случайным. Например, вы можете сказать, что все, что имеет значение выше 100, включается в 1% от его стоимости, а все, что имеет значение ниже, имеет свою ценность как процентный шанс включения. Затем умножьте окончательные ответы на 100. Если среднее значение находится в диапазоне 1-10, то фильтр O(1) только что удалил 90-99% из необходимого хранилища данных и работы. Но у вас будут приблизительные ответы, которые должны быть в порядке.