Найти наиболее посещаемый URL за последний день, или последний час, или последнюю минуту?
Исходный вопрос - файл, содержащий URL-адрес 5 ГБ, который был посещен в последний день. Эта проблема может быть решена с помощью хэш-карты для подсчета вхождений различных URL-адресов и определения top k с помощью min heap, что занимает время O (n log k).
Теперь я думаю, что, если ввод был неограниченным потоком онлайн-данных (вместо статического файла), то как я могу узнать верхний k URL за последний день?
Или есть какие-то улучшения, которые я могу внести в систему, которые позволяют мне динамически получать URL-адреса top-k за последнюю минуту, последний день и последние часы?
Любая подсказка будет оценена!!
1 ответ
Если вы готовы согласиться на вероятностный ответ, который может содержать несколько неправильных записей, вам определенно следует заглянуть в структуру данных эскиза count-min. Он был специально разработан для оценки частых элементов в потоке, используя как можно меньше памяти, и большинство реализаций поддерживают очень эффективное с точки зрения времени и пространства приближение верхних k элементов из потока. Кроме того, структура позволяет настроить использование пространства, что делает ее идеальной для подобных ситуаций. IIRC Google использует это для определения своих самых частых поисковых запросов.
Есть несколько реализаций этой структуры данных, доступных онлайн.
Надеюсь это поможет!