самые частые элементы
(эта запись может быть интересна программистам)
Иногда возникает ситуация, когда нужно найти самые частые элементы в длинном списке повторяющихся элементов, который желательно к тому же не хранить целиком. Например, представьте себе сервер, который обрабатывает поисковые запросы, и вы хотите знать, с начала работы сервера и до сих пор какие 10 запросов всречались чаще всего и сколько раз. Или: какие пользователи обращались к серверу чаще всего и сколько раз (top N users). Или: какого рода запросы/какие пользователи использовали больше всего памяти сервера (top N users by RAM).
Можно сохранять весь поток идентификаторов по мере их прихода, сортировать его (или держать сортированным) и брать самые частые. Но это может требовать очень много места. Можно делать сэмплинг, брать каждый элемент из потока с вероятностью 1/n. Но нужно брать вероятность так, чтобы гарантировать попадание в сэмпл самых частых элементов, и тогда все равно может оказаться много места.
Вот эта статья: Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding frequent items in data streams
описывает несложный алгоритм, который может пригодиться в хозяйстве. Мне, например, очень пригодился. Алгоритм использует двумерный массив хэш-значений, который позволяет оценивать примерно частоту каждого элемента и составить с помощью этих оценок список N самых частых элементов в один проход; величину ошибки можно ограничить дешево небольшим окном вокруг N-го элемента. Скажем, если вы хотите 10 самых частых запросов и ошибку в 10%, и "честный" 10-й по частоте запрос встречался 1000 раз, то все, кто встречался больше 1100 раз, "честно" попадут на свои места в топ-10, а из окна 900-1100 могут в топ-10 попасть не "честные", а какие-то другие элементы.
Самое главное - что памяти он использует пропорционально логарифмам всех важных величин - числа элементов, числа потенциальных разных элементов. Выходит очень экономно, так что дешево выходит даже память по байтам отслеживать (т.е. например, если юзер foo послал запрос который истратил 1M памяти, считать это концептуально 1,048,576 повторениями строки "foo", и в таком потоке находить чемпионов).
Update: ссылка из комментариев - обзор нескольких алгоритмов такого рода.
Иногда возникает ситуация, когда нужно найти самые частые элементы в длинном списке повторяющихся элементов, который желательно к тому же не хранить целиком. Например, представьте себе сервер, который обрабатывает поисковые запросы, и вы хотите знать, с начала работы сервера и до сих пор какие 10 запросов всречались чаще всего и сколько раз. Или: какие пользователи обращались к серверу чаще всего и сколько раз (top N users). Или: какого рода запросы/какие пользователи использовали больше всего памяти сервера (top N users by RAM).
Можно сохранять весь поток идентификаторов по мере их прихода, сортировать его (или держать сортированным) и брать самые частые. Но это может требовать очень много места. Можно делать сэмплинг, брать каждый элемент из потока с вероятностью 1/n. Но нужно брать вероятность так, чтобы гарантировать попадание в сэмпл самых частых элементов, и тогда все равно может оказаться много места.
Вот эта статья: Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding frequent items in data streams
описывает несложный алгоритм, который может пригодиться в хозяйстве. Мне, например, очень пригодился. Алгоритм использует двумерный массив хэш-значений, который позволяет оценивать примерно частоту каждого элемента и составить с помощью этих оценок список N самых частых элементов в один проход; величину ошибки можно ограничить дешево небольшим окном вокруг N-го элемента. Скажем, если вы хотите 10 самых частых запросов и ошибку в 10%, и "честный" 10-й по частоте запрос встречался 1000 раз, то все, кто встречался больше 1100 раз, "честно" попадут на свои места в топ-10, а из окна 900-1100 могут в топ-10 попасть не "честные", а какие-то другие элементы.
Самое главное - что памяти он использует пропорционально логарифмам всех важных величин - числа элементов, числа потенциальных разных элементов. Выходит очень экономно, так что дешево выходит даже память по байтам отслеживать (т.е. например, если юзер foo послал запрос который истратил 1M памяти, считать это концептуально 1,048,576 повторениями строки "foo", и в таком потоке находить чемпионов).
Update: ссылка из комментариев - обзор нескольких алгоритмов такого рода.