Сообщение Уникальные запросы от 17.09.2018 18:19
Изменено 17.09.2018 19:22 SergeCpp
Уникальные запросы
Здравствуйте, 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 милл. двухбитовых полей. И сложение с насыщением (00-01-10-11-11-11-...) -- потом считаем единички.
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 милл. двухбитовых полей. И сложение с насыщением (00-01-10-11-11-11-...) -- потом считаем единички.
Уникальные запросы
Здравствуйте, 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-...) -- потом считаем единички.
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-...) -- потом считаем единички.