"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит
100000 и не меньше, чем 50000.
Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
Для плюсов
Ограничение времени
2 секунды
Ограничение памяти
500Kb
Формат ввода
В первой строке указано число
n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из
n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит
1000 символов.
Формат вывода
Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Здравствуйте, SomeOne_TT, Вы писали:
SO_>Не дает покоя нерешенная задачка. SO_>Возможно, вы покажете, как она решается? SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые. SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит SO_>100000 и не меньше, чем 50000. SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени SO_>2 секунды
SO_>Ограничение памяти SO_>500Kb
SO_>Формат ввода SO_>В первой строке указано число SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит SO_>1000 символов.
SO_>Формат вывода SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Точность 5%, т.е. все можно не анализировать, а взять например каждый 10 запрос или сравнивать только начало строк.
Считаем crc32 от строки, масштабируем результат, чтоб от 0 до 512 кб было и устанавливаем соотв. байт. В конце считаем число ненулевых. Можно по битам (чтоб точнее), битов будет 500 тыс * 8 = 4 миллиона примерно. Строку можно к нижнему регистру.
Здравствуйте, SergeCpp, Вы писали:
SC>Здравствуйте, SomeOne_TT.
SC>Считаем crc32 от строки, масштабируем результат, чтоб от 0 до 512 кб было и устанавливаем соотв. байт. В конце считаем число ненулевых. Можно по битам (чтоб точнее), битов будет 500 тыс * 8 = 4 миллиона примерно. Строку можно к нижнему регистру.
Не вижу разницы с моим подходом.
Максимум 100к уников, для 500к памяти это по 5 байт на хэш, а запросов-то 500к...
либо надо извращаться и как-то хитро моделировать хэш функцию с учетом энтропии алфавита и
максимальной длины значения (1к),либо правильный ответ все же учитывает распределение
частот уников/не уников в домене запросов.
Здравствуйте, SomeOne_TT.
SC>>Считаем crc32 от строки, масштабируем результат, чтоб от 0 до 512 кб было и устанавливаем соотв. байт. В конце считаем число ненулевых. Можно по битам (чтоб точнее), битов будет 500 тыс * 8 = 4 миллиона примерно. Строку можно к нижнему регистру.
SO_>Не вижу разницы с моим подходом.
Вы свой подход не описали, лишь туманно что-то сказали вскользь.
SO_>Максимум 100к уников, для 500к памяти это по 5 байт на хэш, а запросов-то 500к...
Не нужно никаких байт на хэш, я же ясно написал.
А 500 К запросов, или больше, написано же: "Гарантируется, что правильный ответ не превосходит
100000", то есть уникальных в 500 тыс байтов (или в 4 мил. битов) будет не более 100 тыс.
Для чего эти биты? А если все crc32 наши образуют компактные кластеры, тогда при 500 тыс. будет слишком много коллизий и наши 100 тыс. макс. образуют всего тыс. 50 разных. А при побитовом уже разрежённее будет. 4 млрд (crc32 max) делим на 1000 получаем 4 милл. для битов.
P. S. Если под уникальными имеются в виду те, что только один раз были, то 2 милл. двухбитовых полей (тогда crc32 делим на 2 тыс.). И сложение с насыщением (00-01-10-11-11-11-...) -- потом считаем единички.
Здравствуйте, SomeOne_TT, Вы писали:
SO_>Не дает покоя нерешенная задачка. SO_>Возможно, вы покажете, как она решается? SO_>(найти ее можно при регистрации на сайте яндекс блица по ссылке https://contest.yandex.ru/contest/8470/problems/K/)
SO_>"Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые. SO_>Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит SO_>100000 и не меньше, чем 50000. SO_>Решение засчитывается, если ответ отличается от правильного не более, чем на 5%. "
SO_>Для плюсов
SO_>Ограничение времени SO_>2 секунды
SO_>Ограничение памяти SO_>500Kb
SO_>Формат ввода SO_>В первой строке указано число SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит SO_>1000 символов.
SO_>Формат вывода SO_>Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Что значит неверно? Не уложился в заданное время? память? точность?
Посчитать хеш 500 МБ строк (для получения точного ответа) за 2 секунды, может и не получаться... если диск тормозит.
Возможно, ты ее решил не оптимально, но тогда нужны критерии оптимальности: минимизируем время работы при заданной точности и доступной памяти?
Или оптимизируем точность при фиксированном времени? Или память?
Если не уложился в память:
Возможно, на их компиляторе char не 8-битный, используй std::uint8_t/std::uint64_t для организации битового массива.
Возможно, они считают память, захваченную процессом целиком, с учетом памяти стека, файловых буферов, etc... В этом случае нельзя самому аллоцировать 500 кб, уменьши размер массива до 256kB.
Возможно, стоит посмотреть в сторону более низкоуровневых функций чтения из файла, для уменьшения размеров буферов чтения....
(Последнее — врядли понадобится).
Если не уложился в точность:
Оцени поправку, связанную с коллизиями хеш функций, попробуй две хеш функции (фильтр Блума).
Все равно, большая часть времени, скорее всего, расходы на чтение из файла.
Если не уложился во время:
Дописывай в конец каждой прочитанной строки — нули. Это позволит при расчете хеша рассматривать строку ка массив uint64_t, а не байт. (Что в 8 раз быстрее).
Не обрабатывай весь файл данных, обработай сколько успеешь за 1.9 секунды. Далее — экстраполируй статистику.
Здравствуйте, Chorkov, Вы писали:
C>Если не уложился в память: C>Если не уложился в точность: C>Если не уложился во время:
Всё это, безусловно, замечательно и хорошо.
Но не стоит забывать, что даже тщательно оптимизированная пузырьковая сортировка на больших последовательностях всё равно будет работать медленнее какой-нибудь небрежно написанной реализации quicksort.
Так и тут: вместо того, чтобы выкраивать такты и байты, можно просто взять высокоуровневый алгоритм получше. Их много известно: Count-distinct problem.
Здравствуйте, SomeOne_TT, Вы писали:
SO_>n ≤ 500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из SO_>n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит SO_>1000 символов.
Всего у нас есть 500Кб, то есть, 500 000 байт (примерно). Или 4 000 000 бит (примерно).
И нам дано до 500 000 строк.
Совпадение? Не думаю.
Если у нас есть идеальная хеш-функция, отображающая строки на 0..500000, то задача выглядит очень просто:
— заполнить битовый массив нулями
— для каждой строки выставить соответствующий бит
— посчитать количество выставленных битов (причём это можно сделать сразу)
По условиям задачи допускаются коллизии не более чем в 5% случаев. (Или как-то надо пересчитать формулу — из количества FR+FA в вероятность коллизии... сейчас лень думать).
Предположим, что наше наивное решение (мы взяли хеш-функцию наобум) вылетело из этих ограничений. Функция оказалась слишком неидеальной.
Что можно сделать?
1) Отображать не на 500 000, а на 4 000 000.
2) Взять 8 разных хеш-функций, отображающих на 500 000 каждая. Считать коллизией факт одновременно 8 коллизий по каждой из них.
SO_>Я решал ее "в лоб" хэшируя запросы, но, очевидно, это неверно — совершенно не используется информация про распределение запросов.
Сжатие данных — это, конечно, здорово, но наш битовый массив покрывает байтовые строки длиной до 7. (8**7 = 2млн). Это значит, что 1000-байтовые строки придётся сжимать в 142 раза.
Мы точно это сможем?
Поэтому, на первом этапе, я бы не стал париться и считал бы, что обычные хеш-функции справляются со своей задачей по устранению неравномерности распределения.
Здравствуйте, Кодт, Вы писали:
К>Поэтому, на первом этапе, я бы не стал париться и считал бы, что обычные хеш-функции справляются со своей задачей по устранению неравномерности распределения.
Ещё можно случайную подвыборку переданных запросов брать и по ней как-то судить о всём распределении.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Перекуём баги на фичи!
