November 2nd, 2014

moose, transparent

самые частые элементы

(эта запись может быть интересна программистам)

Иногда возникает ситуация, когда нужно найти самые частые элементы в длинном списке повторяющихся элементов, который желательно к тому же не хранить целиком. Например, представьте себе сервер, который обрабатывает поисковые запросы, и вы хотите знать, с начала работы сервера и до сих пор какие 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: ссылка из комментариев - обзор нескольких алгоритмов такого рода.
moose, transparent

скучная запись с банальной концовкой

У меня испортилась предпоследняя пара наушников Sony MDR-W08L, единственных, с которыми мне удобно ходить, которые не спадают, не мешают, дают лучший звук и вообще лучше всех:

sony-mdr-w08l

А Сони перестала их выпускать. Теперь их не найти. Пару лет назад я купил в тель-авивском магазине последние две пары, что у них были. И вот первая из них перестала работать. Открываю вторую, последнюю.

Двадцать лет ими пользовался (с перерывами, но всегда возвращался).

Все когда-нибудь кончается.