Получение наиболее частых предметов без учета каждого предмета

Question

Мне было интересно, существует ли алгоритм подсчета "наиболее часто встречающихся предметов" без необходимости вести подсчет каждого предмета? Например, скажем, я был поисковой системой и хотел отслеживать 10 самых популярных поисковых запросов. Чего я не хочу делать, так это вести счетчик каждого запроса, поскольку для меня может быть слишком много запросов (и большинство из них будут одиночными). Есть ли простой алгоритм для этого? Может быть, это что-то вероятностное? Спасибо!

Answer 1

Что ж, если у вас очень большое количество запросов (как, вероятно, будет делать поисковая система), то вы можете просто выполнить «выборку» запросов. Таким образом, вы можете получать 1000 запросов в секунду, но если вы просто сохраняете счет один в секунду, то в течение длительного периода времени вы получите ответ, который будет относительно близок к «реальному» ответу.

Так работает, например, профилировщик сэмплирования. Каждые n милисекунд он смотрит, какая функция выполняется в данный момент. За длительный период времени (несколько секунд) вы получите представление о «дорогих» функциях, потому что они чаще всего появляются в ваших примерах.

Вам все еще нужно делать «подсчет», но, делая периодические выборки, вместо подсчета каждого отдельного запроса вы можете получить верхнюю границу для объема данных, которые вы фактически должны хранить (например, максимум один запрос в секунду и т. д.)

Answer 2

Если вы хотите наиболее частые поиски в любой момент времени, вам не нужно иметь бесконечные счетчики, отслеживающие каждый отправленный запрос. Вместо этого вам нужен алгоритм для измерения количества представлений для любого данного запроса, деленного на заданный период времени. Это довольно простой алгоритм. Любой поиск, отправленный в вашу поисковую систему, например слово «кеш», сохраняется в течение фиксированного периода времени, называемого частотой обновления (длина вашей частоты обновления зависит от типа трафика, который получает ваша поисковая система, и количества «Топ-результаты», которые вы хотите отслеживать). Если период времени обновления обновлений истекает и поиск слова «кеш» не сохраняется, запрос удаляется из памяти. Если поиск по слову «кеш» продолжается, ваш алгоритм должен отслеживать скорость поиска слова «кеш». Для этого просто сохраните все поиски на «счетчике утечек». Каждая запись помещается на счетчик с датой истечения срока, после которой запрос удаляется. Ваши активные счетчики являются индикаторами ваших самых популярных запросов.

Answer 3

Вы хотите кеш, из которых есть много видов; увидеть википедию алгоритмы кэширования и Алгоритм замены страницы Старение.

Answer 4

Хранение каждого запроса было бы дорого, но необходимо, чтобы топ-10 были действительно топ-10. Вам придется обманывать.

Одной из идей является сохранение таблицы URL-адресов, счетчиков посещений и метки времени, проиндексированных по метке, а затем по метке времени. Когда таблица достигнет некоторого произвольного почти максимального размера, начните удалять записи нижнего уровня, которые старше указанного количества дней. Хотя старые, редкие запросы не будут учитываться, запросы, которые могут попасть в топ-10, должны попасть в таблицу из-за более высокой частоты запросов.

Другой идеей было бы написать 16-битную (или более) хеш-функцию для поисковых запросов. Иметь таблицу на 65536 записей, содержащую счетчики и URL. Когда поиск будет выполнен, увеличьте соответствующую запись в таблице и установите URL-адрес, если это необходимо. Однако такой подход имеет большой недостаток. Спам-бот может делать повторные запросы, такие как «дешевая виагра», возможно, заставляя законные запросы увеличивать счетчики спам-запросов, размещая свои сообщения на главной странице.