Comments 85
Забавно, порылся у себя в репах 5 летней давности, ничего не меняется в этом мире.
реализация на haskell
реализация на clojure
и там и там просто бинарный поиск, roaring bitmaps на тот момент в готовых либах не было, а
писать самому было лень ))
Сама задачка всплывала на хабре в коментах. Там кстати на php решение вроде тоже ссылка была.
реализация на haskell
реализация на clojure
и там и там просто бинарный поиск, roaring bitmaps на тот момент в готовых либах не было, а
писать самому было лень ))
Сама задачка всплывала на хабре в коментах. Там кстати на php решение вроде тоже ссылка была.
Да, популярная задача. На самом деле очень интересна цель конкретно в случае с php, а вообще я люблю более-менее практические задачи которые можно решить используя те или иные алгоритмы, они показательны.
Вот к примеру решение автора с редисом, вроде все хорошо придумал, но в реальности сетевая задержка между кластером с редисом и приложением будет ~1ms и то, если все будет в одном ДЦ, а он так увлёкся размером индекса, что и не учел этого. Вот тут то и кроется причина спора ниже в комментариях, у него есть четкое ограничение по времени и аптайму, но нет ограничение по памяти, в этом и есть ключ.
UFO just landed and posted this here
Известны ли ресурсы ведущие историю этой базы данных? Так чтобы можно было определить время попадания номера документа в перечень недействительных?
номер серии из 4 цифр и номер паспорта из 9 цифр
А том видим 6 цифр.
по 4 байта, т.е 520 миллионов байт (что как раз и даёт наверно около 42 мб)
Тут все тыкают на -тся и -ться. Пора в вычисления тыкать. Чем вы считаете?
log2(10^(4+9))=43.19 => 44 бит * 140e6 = 735Mbyte
log2(10^(4+6))=33.22 => 34 бит * 140e6 = 568Mbyte
log2(10^(4+9))=43.19 => 44 бит * 10e6 = 53Mbyte
log2(10^(4+6))=33.22 => 34 бит * 10e6 = 41Mbyte
64 бит * 10e6 = 77Mbyte
ps: Вот тут еще новый вид самообучающихся индексов реализовали.
А вот ещё вариант, местный, хабровский.
А не проще использовать Фильтр Блума?
Об этом есть в статье:
Для всего множества возможных серий и номеров потребуется 9999 х 999999 ~ 10^10 бит ~ 1.25ГБ. Это сопоставимо с размером исходного файла, но уже с поиском за O(1).
Фильтр Блума можно использовать как дополнение, но не как замену, т.к. в случае ложноположительного результата задача снова сведется к поиску в исходном датасете.
Можно подсчитать какая будет вероятность ложноположительного срабатывания для фильтра Блума размером 42MiB. По простой формуле p = (1-e^⁻kn/m)^k получаем
p = (1-e^⁻² 130M/42MiB)² = 0.272 (≈ каждый четвёртый)
что довольно много, потому что количество элементов в множестве велико. Чтобы достичь 99 перцентиля в 1мс потребуется около 150MiB фильтр. Хотя тут всё же можно использовать фильтр Блума для предпроверки, если проверять по серии, их уникальных в базе около трёх тысяч. Что с ничтожно малой вероятностью ложноположительного срабатывания займёт какие-то жалкие 20KiB объёма. А уже потом проверять по нашей сжатой базе.
Довольно интересный вывод можно сделать что в базе уже есть 130 миллионов недействительных паспортов, что составляет более 1% от всей мощности множества, и даже больше если учесть что регион и год потребляют лишние биты. Каждый тридцатый паспорт недействительный!
p = (1-e^⁻² 130M/42MiB)² = 0.272 (≈ каждый четвёртый)
что довольно много, потому что количество элементов в множестве велико. Чтобы достичь 99 перцентиля в 1мс потребуется около 150MiB фильтр. Хотя тут всё же можно использовать фильтр Блума для предпроверки, если проверять по серии, их уникальных в базе около трёх тысяч. Что с ничтожно малой вероятностью ложноположительного срабатывания займёт какие-то жалкие 20KiB объёма. А уже потом проверять по нашей сжатой базе.
Довольно интересный вывод можно сделать что в базе уже есть 130 миллионов недействительных паспортов, что составляет более 1% от всей мощности множества, и даже больше если учесть что регион и год потребляют лишние биты. Каждый тридцатый паспорт недействительный!
Зашел сюда, чтобы увидеть очевидное решение, был сильно удивлен реализацией автора.
Имеем «Пользовательская база 10 миллионов», для каждого пользователя нужно хранить 1 бит информации (включен в список или нет). Итого 10 000 000 бит или 1.25 мб. Такой объем можно запросто хранить в памяти.
Имеем «Пользовательская база 10 миллионов», для каждого пользователя нужно хранить 1 бит информации (включен в список или нет). Итого 10 000 000 бит или 1.25 мб. Такой объем можно запросто хранить в памяти.
А можно пойти ещё дальше и учитывая, что состояния всего два — включен или нет — только их и хранить. Тогда вообще в два бита уложимся.
Дано 10 000 000 чисел по 34 бита каждое, числа от 0 до 9 999 999 999
для любого 10 значного числа нужен ответ, входит оно в эти 10 миллионов чисел или нет.
В общем вы немного не поняли условия задачи.
для любого 10 значного числа нужен ответ, входит оно в эти 10 миллионов чисел или нет.
В общем вы немного не поняли условия задачи.
UFO just landed and posted this here
Ну если внимательней прочитать статью «Всего в списке около 130 миллионов записей»
С этого момента становится интересней?
А 10 миллионов влезет.
Сорри, не 10 000 000 а 130 000 000 по 34 бита из 10 миллиардов.
Думаю на этой ноте про хэш таблицы разговор стоит закончить.
С этого момента становится интересней?
А 10 миллионов влезет.
Сорри, не 10 000 000 а 130 000 000 по 34 бита из 10 миллиардов.
Думаю на этой ноте про хэш таблицы разговор стоит закончить.
UFO just landed and posted this here
Что в 200 раз больше чем в статье, тоесть на 2 порядка. Так то нынче и машины с терабайтом памяти не редкость, только с таким подходом…
UFO just landed and posted this here
Какая дальнейшая оптимизация? Вы о чем?
Я эту задачу решал 5 лет назад, первое решение это вечер за компом, 120 строк кода. Потом по необходимости добавил веб + прочие плюшки в итого выросло до 400 строк.
Без хэш таблиц, просто сортированный массив, 5 лет назад кстати оперативная память была сильно дороже, если быть точным, то на сервере где крутился фронт от сервиса было 8 гигов оперативы (это весь сервис, паспорта там 0.001% функционала), на бэкэнде было 16 гигов.
Если бы писал сейчас, тоже бы взял разреженные битмассивы, либы потому что сейчас есть, тогда их просто на том языке на котором писал не было.
Я эту задачу решал 5 лет назад, первое решение это вечер за компом, 120 строк кода. Потом по необходимости добавил веб + прочие плюшки в итого выросло до 400 строк.
Без хэш таблиц, просто сортированный массив, 5 лет назад кстати оперативная память была сильно дороже, если быть точным, то на сервере где крутился фронт от сервиса было 8 гигов оперативы (это весь сервис, паспорта там 0.001% функционала), на бэкэнде было 16 гигов.
Если бы писал сейчас, тоже бы взял разреженные битмассивы, либы потому что сейчас есть, тогда их просто на том языке на котором писал не было.
UFO just landed and posted this here
Если программист получает 100$ в час, то есть (после налогов?) 16k в месяц, тупо не знает алгоритмов и просто решает задачу всегда в лоб (16k в месяц это явно не аутсорсинг с Индии) Его руководителей, как и его, надо просто гнать.
2 — 3 часа это заняло у меня, я не профессиональный программист, для меня это просто хобби.
Ну и еще раз по комментарию выше:
0.001% это проверка паспортов ~ 10 гигов по вашим словам, памяти которая дешевле чем подумать.
с такой логикой как у вас, 1% это уже 10 * 1000 = 10TB оперативы
весь сервис с таким подходом, спокойно уместится в 1000TB оперативной памяти.
упс… Остапа понесло…
2 — 3 часа это заняло у меня, я не профессиональный программист, для меня это просто хобби.
Ну и еще раз по комментарию выше:
0.001% это проверка паспортов ~ 10 гигов по вашим словам, памяти которая дешевле чем подумать.
с такой логикой как у вас, 1% это уже 10 * 1000 = 10TB оперативы
весь сервис с таким подходом, спокойно уместится в 1000TB оперативной памяти.
упс… Остапа понесло…
На практике даже хеш таблица в памяти не нужна в типичном случае. РПС не настолько высок и критерии по производительности не так высоки. Сгодится просто табличка на любом sql сервере. В режиме kv по pk они все хорошо работают.
Если рпс слишком высок, то выделенный контейнер с хеш таблицей в памяти и примитивным АПИ на который все ходят. Или Редис какой. Храним одну копию. 10 гигов памяти по сравнения с сотней ходящих в нее серверов это копейки.
Программист должен знать когда надо оптимизировать код, а когда хватит просто правильной архитектуры. И как правило хорошей архитектуры хватает.
Если рпс слишком высок, то выделенный контейнер с хеш таблицей в памяти и примитивным АПИ на который все ходят. Или Редис какой. Храним одну копию. 10 гигов памяти по сравнения с сотней ходящих в нее серверов это копейки.
Программист должен знать когда надо оптимизировать код, а когда хватит просто правильной архитектуры. И как правило хорошей архитектуры хватает.
Парни, вы статью то прочитайте, паспорта положили в redis, там есть встроенная поддержка Roaring Bitmaps, из коробки, данный алгоритм в общем то скорей всего является оптимальным для этой задачи. И rps и тд все практически идеально.
И это в 40 мегабайтах, а вы все со своими хэштаблицами на 10 гигов…
Если убрать весь нефункциональный код типа скачать распарсить и тд., останется вызов двух команд redis:
«Используем команды SETBIT/GETBIT»
ну я уж не знаю…
И это в 40 мегабайтах, а вы все со своими хэштаблицами на 10 гигов…
Если убрать весь нефункциональный код типа скачать распарсить и тд., останется вызов двух команд redis:
«Используем команды SETBIT/GETBIT»
ну я уж не знаю…
Мы и говорим что практики просто взяли бы int64 ключ и не парились бы с битами. Расходы на железо настолько маленькие выходят что оно того не стоит.
А экономия на поддерже любого усложненного решения многократно окупит все эти расходы.
Куда положить таблицу в Редис или в sql зависит от РПС. Скорость и так и так будет достаточной для любого практического применения.
А экономия на поддерже любого усложненного решения многократно окупит все эти расходы.
Куда положить таблицу в Редис или в sql зависит от РПС. Скорость и так и так будет достаточной для любого практического применения.
Мне сильно любопытно, почему при таких маленьких расходах на железо процветает hetzner...)
Я вот не знаю кто в вашем понимании практики, последние лет 5 в основном сталкивался с большими данными, и там постоянная проблема, на одну машину не влезает (ну есть ограничения по памяти, тупо материка больше не поддерживает, никакая.)
а хадупы и тд уже сильно дороже, тупо аренда железа под хадуп на 700 терабайт реплицированного диска уже гдет по 50 — 70 к $ в месяц.
И вот слушаю я все эти память дешёвая, и нет слов у меня.
Я вот не знаю кто в вашем понимании практики, последние лет 5 в основном сталкивался с большими данными, и там постоянная проблема, на одну машину не влезает (ну есть ограничения по памяти, тупо материка больше не поддерживает, никакая.)
а хадупы и тд уже сильно дороже, тупо аренда железа под хадуп на 700 терабайт реплицированного диска уже гдет по 50 — 70 к $ в месяц.
И вот слушаю я все эти память дешёвая, и нет слов у меня.
Шардирование и уж тем более перешардирование данных это большая проблема. С бигдатой вообще много проблем.
Но тут мы говорим всего о 130 миллионах лонгов. Без тенденции на рост. Это очень далеко от бигдата. Это просто табличка. Не особо мутирующая при этом.
И работать с ней надо как с просто табличкой.
Силы лучше вон на те терабайты потратить. Там экономия и скорость работы заметнее будут.
Чтобы тут было интересно надо увеличить размер до Гугла и их id пользователей. У них их наверно миллиардов под 10. С тенденцией на рост. И просто так в память класть все уже больно.
Но тут мы говорим всего о 130 миллионах лонгов. Без тенденции на рост. Это очень далеко от бигдата. Это просто табличка. Не особо мутирующая при этом.
И работать с ней надо как с просто табличкой.
Силы лучше вон на те терабайты потратить. Там экономия и скорость работы заметнее будут.
Чтобы тут было интересно надо увеличить размер до Гугла и их id пользователей. У них их наверно миллиардов под 10. С тенденцией на рост. И просто так в память класть все уже больно.
Тут есть забавная штука, эти «паспорта» в реальной жизни и в бигдате встречаются очень часто, зовутся по другому, объемы сильно другие, а сама задача звучит так же. Только цифры на несколько порядков больше.
Вот эти 130 миллионов int64 можно рассматривать как 10 массивов с int32, и уже кратный разрыв по памяти и объему, а можно как разреженный битмэп, и там уже много порядков.
Реальный кейс:
есть N категорий, есть поток данных по этим категориям, в каждом сообщении есть идентификатор(уникальный), и поле с набором категорий
скорость потока 200k rps в секунду
сервис соответственно должен формировать для каждой категории множество идентификаторов
Далее нужно иметь возможность формировать множества по разным категориям, собственно все операции со множествами.
И хочется это иметь в разрезе времени, шаг 5 минут.
Типовой идентификатор int128
По сути та же задача, только цифры немного другие.
Вот эти 130 миллионов int64 можно рассматривать как 10 массивов с int32, и уже кратный разрыв по памяти и объему, а можно как разреженный битмэп, и там уже много порядков.
Реальный кейс:
есть N категорий, есть поток данных по этим категориям, в каждом сообщении есть идентификатор(уникальный), и поле с набором категорий
скорость потока 200k rps в секунду
сервис соответственно должен формировать для каждой категории множество идентификаторов
Далее нужно иметь возможность формировать множества по разным категориям, собственно все операции со множествами.
И хочется это иметь в разрезе времени, шаг 5 минут.
Типовой идентификатор int128
По сути та же задача, только цифры немного другие.
Так надо формулировать сразу правильно. А не 130 миллионов с атомарной заменой одной таблички на другую раз в день.
200к рпс это прям серьезно. Аналитика по таким потокам это еще серьезнее. Из плюсов аналитика совсем простая и за короткое время.
200к рпс, 5 минут. итого 60 миллионов событий. не хватает цифры с количеством уникальных id, но не важно пусть все уникальное. Надо держать окно в которое влазят эти 60 миллионов.
Итого мапа на 60 миллионов int128 без проблем. Держим данные для окна, все типично. Все старое сбрасываем в любое хранилище по вкусу. Оно уже рассчитанно, пожато и пусть себе лежит.
Обратные индексы по категориям тоже без проблем. У нас указатели, на размер id тут уже все равно.
Базы на таком потоке в реалтайме наедятся. Пишем велосипед инмемори.
Мапа гигов 10. Каждый обратный индекс это всего лишь массив указателей. 60 миллионов int64 это всего полгига памяти. Требования вроде выполняются. Есть небольшие накладные расходы на временные метки, но это все мелочи.
Итого в типичный сервер влезет пара сотен категорий. На 5 минутном окне. Хватит?
На практике, конечно, сразу пишем шардирование. Все равно пригодится рано или поздно.
Основные данные можно по всем шардам дублировать чтобы на сеть не тратится, категории храним по разным шардам. Координатор раздает кто что из категорий записывает. Все о чем координатор не знает на отдельный шард. Можно накрутить автоматику перешардирования. На 5 минутном окне она не очень страшная. Настройка по дефолту 3 шарда. 2 для категорий пополам и третий для всего что в них не попало.
Даже с двойным резервированием выглядит не очень страшно. Железа для долговременного хранения истории уйдет заметно больше чем для обработки входящего потока данных.
200к рпс это прям серьезно. Аналитика по таким потокам это еще серьезнее. Из плюсов аналитика совсем простая и за короткое время.
200к рпс, 5 минут. итого 60 миллионов событий. не хватает цифры с количеством уникальных id, но не важно пусть все уникальное. Надо держать окно в которое влазят эти 60 миллионов.
Итого мапа на 60 миллионов int128 без проблем. Держим данные для окна, все типично. Все старое сбрасываем в любое хранилище по вкусу. Оно уже рассчитанно, пожато и пусть себе лежит.
Обратные индексы по категориям тоже без проблем. У нас указатели, на размер id тут уже все равно.
Базы на таком потоке в реалтайме наедятся. Пишем велосипед инмемори.
Мапа гигов 10. Каждый обратный индекс это всего лишь массив указателей. 60 миллионов int64 это всего полгига памяти. Требования вроде выполняются. Есть небольшие накладные расходы на временные метки, но это все мелочи.
Итого в типичный сервер влезет пара сотен категорий. На 5 минутном окне. Хватит?
На практике, конечно, сразу пишем шардирование. Все равно пригодится рано или поздно.
Основные данные можно по всем шардам дублировать чтобы на сеть не тратится, категории храним по разным шардам. Координатор раздает кто что из категорий записывает. Все о чем координатор не знает на отдельный шард. Можно накрутить автоматику перешардирования. На 5 минутном окне она не очень страшная. Настройка по дефолту 3 шарда. 2 для категорий пополам и третий для всего что в них не попало.
Даже с двойным резервированием выглядит не очень страшно. Железа для долговременного хранения истории уйдет заметно больше чем для обработки входящего потока данных.
UFO just landed and posted this here
Ну и чтоб быть честными, 9 999 999 999
размерность как раз на 10 милиардов. Это не много, у гугла на несколько порядков больше размерность id.
размерность как раз на 10 милиардов. Это не много, у гугла на несколько порядков больше размерность id.
Не совсем верно. Redis не умеет Roaring Bitmaps из коробки, там честные нули. 40 мегабайт — это в Pilosa, там с битмапами всё хорошо. Но не ясно, что со стабильностью работы. Может кто-то расскажет, кто имел опыт?
А чего вы память в битах мерите то, там файл со строками умещается в 1.5гБАЙТА и хеш Мапы выкинули :( можно во первых разбить по серии (первый уровень) и уже номера второй ~500мб
Пока мой комментарий проходил модерацию понял, что 10 млн это похоже опечатка в условии. На самом деле пользовательская база 10 миллиардов. Тогда статья обретает смысл, хотя я бы поэкспериментировал с вариантами хранения бинарного дерева — по опыту коллег данные такого типа хорошо ужимаются до размеров, которые можно хранить в памяти.
Ну на самом деле выбор разреженных битовых массивов под эту задачу весьма не плох, думаю бинарное дерево больше места займет.
5 лет назад я делал просто сортированные массивы, по скорости таже константа, по месту 200 — 300 мегабайт, только там без внешних хранилищ.
5 лет назад я делал просто сортированные массивы, по скорости таже константа, по месту 200 — 300 мегабайт, только там без внешних хранилищ.
10 миллиардов паспортов… Недействительных. При населении планеты в 7.5 млрд.
И поиск за 1 мс…
И поиск за 1 мс…
Не знаю как насчет реализации в redis, но в оригинальных либах еще и операции со множествами поддерживаются, и тоже за константное?(не помню) время. Как пример использовал это в задачках вида: есть группа от 18 до 34 лет, есть группа любителей попкорна, есть группа любителей домашнего порно, есть группа мужчин нужно получить целевую аудиторию мужчин от 18 до 34 лет, которые любят домашнее порно и попкорн.
Собственно каждый субъект в группе это кука ))
В итого с кластера на 3 машинах с терабайтными ssd + полтерабайтными кусками оперативы перешли на 1 машину со 128 гигами. Ну и операции из разряда запустить на ночь стали реалтайм.
Собственно каждый субъект в группе это кука ))
В итого с кластера на 3 машинах с терабайтными ssd + полтерабайтными кусками оперативы перешли на 1 машину со 128 гигами. Ну и операции из разряда запустить на ночь стали реалтайм.
Ну, если считать паспорта — у человека 30 лет есть уже два номера (действительный и прошлый), 50 лет — уже три-четыре (был период обязательной смены паспортов, не привязанный к возрасту). И это не считая утерянных, смен фамилий/имени и т.д.
Может быть я пишу глупость, но мне кажется, алгоритм Bloom Filter так и напрашивается сюда в качестве решения задачи поиска.
1.25 Гб не такой большой объем чтобы хранить непосредственно сразу все допустимые варианты в памяти и иметь чтение и записать за O(1). И в условии про ограничения на память ничего нет.
Фильтр Блума даёт ложноположительные результаты (но не даёт ложноотрицательных) и с этим придётся что-то делать
Если множество всех серийных номеров паспортов конечное (10 млрд. всего), то есть способ построить фильтр блума без ложноположительных, перечислив их всех наперёд. Либо вот ещё подход, но я не вникал: medium.com/orbs-network/constructing-bloom-filters-without-false-positives-7aaf50b92f3b
Фильтр Блума так устроен, что для всех его элементов существует такой набор содержимого множества, который даёт ложноположительное срабатывание (если же это не так, это лишь значит, что шеш-функции выбраны неудачно и для некоторых элементов ложноположительные резальтаты уже будет давать катастрофически большое подмножество генерального множества) — если пытаться что-то хранить, что могло бы попасть в ложноположительные — то проще само множество хранить непосредственно без фильтра
Да, всё так. Только щас уже есть более эффективные cuckoo filter и xor filter. Учитывая, что множество всех запрашиваемых серийников паспортов конечно, можно и от ложноположительных избавиться, перечислив их все наперёд. Либо вот ещё подход, как сделать фильтр блума без ложноположительных срабатываний: medium.com/orbs-network/constructing-bloom-filters-without-false-positives-7aaf50b92f3b
Для решения задачи отлично подойдёт префиксное дерево https://ru.m.wikipedia.org/wiki/Префиксное_дерево
10 000 000 строк, каждая это 10 int8
я бы сказал, что я сильно сомневаюсь, что на основе префиксного дерева получится построить более эффективное решение этой задачи чем на основе разреженных битмассивов.
Я далеко не спец по алгоритмам, это скорей хобби, но было бы очень любопытно увидеть код и показатели стоимости данного алгоритма на этой задаче.
Текущие лучшие решения в статье и комментариях:
размер от 40 до 300 мегабайт
время доступа константа
количество строк кода (вместе с тривиальной веб мордой) от 400 строк кода.
память и cpu смысла нет расписывать, там копейки.
я бы сказал, что я сильно сомневаюсь, что на основе префиксного дерева получится построить более эффективное решение этой задачи чем на основе разреженных битмассивов.
Я далеко не спец по алгоритмам, это скорей хобби, но было бы очень любопытно увидеть код и показатели стоимости данного алгоритма на этой задаче.
Текущие лучшие решения в статье и комментариях:
размер от 40 до 300 мегабайт
время доступа константа
количество строк кода (вместе с тривиальной веб мордой) от 400 строк кода.
память и cpu смысла нет расписывать, там копейки.
Не в чистом виде: число узлов превысит число паспортов.
У меня получился гибрид: первые 8 символов — в префиксном дереве, остальные 2 — в битовых массивах в листьях.
Над преобразованием Tmp -> Node придётся подумать самостоятельно.
3_106_435 * sizeof(Node) == 49_702_960 байт
У меня получился гибрид: первые 8 символов — в префиксном дереве, остальные 2 — в битовых массивах в листьях.
normalize.rb
#!/bin/ruby
STDERR.puts Time.now
b = []
while s = gets
s.gsub! /\D/, ''
b << s.to_i if s.size == 10
end
STDERR.puts Time.now
b.sort!
STDERR.puts Time.now
b.each do | i |
print '%010d' % [i]
end
STDERR.puts Time.now$ ./normalize.rb < list_of_expired_passports.csv > normalized.txt
2021-02-06 03:37:34 +0300
2021-02-06 03:46:05 +0300
2021-02-06 03:47:08 +0300
2021-02-06 03:49:32 +0300
build_tree.rb
#!/bin/ruby
b = File.read 'normalized.txt'
N = Struct.new :digit, :first_child, :next_sibling
T = N.new
count = 0
Insert = -> t, c do
if t.first_child == nil
count += 1
return (t.first_child = N.new c)
end
t = t.first_child
while t.digit != c && t.next_sibling != nil
t = t.next_sibling
end
return (t.digit == c) ? t : (count += 1; t.next_sibling = N.new c)
end
STDERR.puts Time.now
(0...b.size).step 10 do | i |
t = T
b[i, 8].each_char do | c |
t = Insert.(t, c)
end
puts count if i % 1e8.to_i == 0
end
STDERR.puts Time.now
puts count$ ./build_tree.rb
2021-02-06 04:01:04 +0300
2021-02-06 04:49:37 +0300
3106435
Промежуточная C-структура:
typedef struct Tmp {
char digit;
Tmp *first_child;
Tmp *next_sibling;
uint8_t[16]
} Tmp;
Компактная финальная:
typedef struct Node {
uint8_t[16]; // 100 bitarray +
// 4 digit +
// 1 is_sibling_exists_flag +
// 23 index_in_Node_array
} Node;Над преобразованием Tmp -> Node придётся подумать самостоятельно.
3_106_435 * sizeof(Node) == 49_702_960 байт
Над преобразованием Tmp -> Node придётся подумать самостоятельно.github.com/alantudyk/Trie
За полгода никто так и не посчитал нужным предъявить мне за то, что я 100 млн. раз постучался по произвольному индексу в гигабайтную UTF-8 строку (build_tree.rb).
Тем временем, я хочу похвалить Ruby за то, что он смог отсортировать 100 млн. int'ов за 1 минуту (normalize.rb), это лишь в 4-5 раз медленнее, чем qsort() из glibc. Оптимизация работает так: перед сортировкой Ruby сканирует массив, и если все значения попадают в диапазон C-шного int'а, то копирует все значения в C-массив, вызывает на нём qsort(), и уже упорядоченные значения копирует обратно в изначальный Ruby-массив.
Да, причем его построение наиболее оптимально, на мой взгляд, следующий образом:
1) сортируются по числу вхождений серии
2) по ним строится дерево и маппинг битов на серии
3) по номерам создаем массив и в нем элементом будет битовая маска с записями всех серий с таким же номером
4) итого массив из 1000000 элементов
И уже по нему производим поиск.
Если не ошибаюсь, то в исходном файле есть записи хотя бы с одной серией для всех номеров от 000000 до 999999
1) сортируются по числу вхождений серии
2) по ним строится дерево и маппинг битов на серии
3) по номерам создаем массив и в нем элементом будет битовая маска с записями всех серий с таким же номером
4) итого массив из 1000000 элементов
И уже по нему производим поиск.
Если не ошибаюсь, то в исходном файле есть записи хотя бы с одной серией для всех номеров от 000000 до 999999
Можете подсказать, что это за значения O(1)?
Временная сложность алгоритма
Ну и дальше в кроличью нору вики.
Ну и дальше в кроличью нору вики.
Либо я неверно понял условие, либо задача вполне решается следующим образом:
-Принимаем формат паспорта за YYYY NNNNNN. При этом YYYY — это не абы что, а цифры примерно соответствующие году выдачи, то есть можно вычесть, скажем, 2000 и хранить только оставшиеся 6 бит (от 2000 до 2063 года). NNNNNN не сократить, это 20 бит.
-Итого имеем 26 бит, однозначно идентифицирующих документ. Для хранения всех паспортов одного года требуется 2^20 бит то есть 128 Кбайт. Таких массивов у нас 64 (по годам), то есть всего 64 * 128 Кбайт = 8 Мегабайт (это наши итоговые требования по памяти).
-Однажды делаем предварительный проход по базе паспортов и выставляем соответствующие биты.
-Приходит запрос. Вычисляем смещение умножением двух чисел, читаем один бит — получаем результат. На всё про всё вряд ли и микросекунда уйдёт.
Может я всё-таки неверно понял условие?
-Принимаем формат паспорта за YYYY NNNNNN. При этом YYYY — это не абы что, а цифры примерно соответствующие году выдачи, то есть можно вычесть, скажем, 2000 и хранить только оставшиеся 6 бит (от 2000 до 2063 года). NNNNNN не сократить, это 20 бит.
-Итого имеем 26 бит, однозначно идентифицирующих документ. Для хранения всех паспортов одного года требуется 2^20 бит то есть 128 Кбайт. Таких массивов у нас 64 (по годам), то есть всего 64 * 128 Кбайт = 8 Мегабайт (это наши итоговые требования по памяти).
-Однажды делаем предварительный проход по базе паспортов и выставляем соответствующие биты.
-Приходит запрос. Вычисляем смещение умножением двух чисел, читаем один бит — получаем результат. На всё про всё вряд ли и микросекунда уйдёт.
Может я всё-таки неверно понял условие?
Про серию вы ошибаетесь.
Год там и, правда, некоторым образом прослеживается — посмотрел на нескольких паспортах: последние две цифры серии соответствуют году выдачи, либо на единицу меньше или больше.
Но вот первые две цифры серии скорей всего связаны с регионом выдачи.
В разных регионах они разные, но при этом совпадают, если паспорта выданы в одном регионе.
Год там и, правда, некоторым образом прослеживается — посмотрел на нескольких паспортах: последние две цифры серии соответствуют году выдачи, либо на единицу меньше или больше.
Но вот первые две цифры серии скорей всего связаны с регионом выдачи.
В разных регионах они разные, но при этом совпадают, если паспорта выданы в одном регионе.
В самом деле, две первые — регион. Две вторые — примерно год (± 1). Значит придётся ещё 7 бит заложить под регион, а это увеличивает требования по памяти до 1 Гб.
Нет, у меня первые две цифры — не регион.
По-моему, разбор формата серий паспортов был на Хабре.
Серия характеризует бланк паспорта, год создания бланка и регион, к которому бланк относится.
Соответственно, если несколько лет бланк дожидался выдачи — год в серии не совпадает.
Если в одном регионе закончились бланки, их подвезли из другого — регион в серии не совпадает.
И да, регионы закодированы иначе, чем на автомобильных номерах и тому подобном.
Серия характеризует бланк паспорта, год создания бланка и регион, к которому бланк относится.
Соответственно, если несколько лет бланк дожидался выдачи — год в серии не совпадает.
Если в одном регионе закончились бланки, их подвезли из другого — регион в серии не совпадает.
И да, регионы закодированы иначе, чем на автомобильных номерах и тому подобном.
Да, вот здесь подробности https://habr.com/post/478538/
Когда заканчивается бланки, если это известно заранее, «заимствуют» не из других регионов, а «из будущего», из других же регионов заимствуют для оперативного разрешения нехватки. Если верить статье и если я правильно понял её текст, «залежаться» бланк может года на 3, а «телепортироваться в прошлое» лет на 5
UFO just landed and posted this here
За час наговнокодить базу в Редисе и апишку к ней вообще не вариант?
Такая апишка не вернёт ответ за 1мс. Можете проверить.
Я естесвенно проверил перед тем как писать.
От 1 от 2 миллисекунд. cli. Из кода значит можно быстрее и с гарантией в одну уложится.
От 1 от 2 миллисекунд. cli. Из кода значит можно быстрее и с гарантией в одну уложится.
bugm@bugmpk:~$ time redis-cli get var
«1»
real 0m0.001s
user 0m0.001s
sys 0m0.000s
Отсортировать, записать в файл и искать бинарным поиском. Почему нет ?
Мой первый комент, 2 разных языка, под капотом просто отсортированные массивы.
Время доступа константа, размер массивов на тот момент было около 300 мегов ( тогда список не валидных паспортов был всего 90 миллионов).
10 знаков это 10 массивов с int32 внутри.
Без битмэпов, тогда либ не было готовых.
Так что да ))
Но если бы писал сейчас реализовывал бы тоже на разреженных битмэпах, оно и эффективно да и алгоритм красивый )) Да и либы почти на всех языках есть, они уже даже способ хранения стандартизировали. В статье используется redis, там эта реализация битмэпов под капотом.
Время доступа константа, размер массивов на тот момент было около 300 мегов ( тогда список не валидных паспортов был всего 90 миллионов).
10 знаков это 10 массивов с int32 внутри.
Без битмэпов, тогда либ не было готовых.
Так что да ))
Но если бы писал сейчас реализовывал бы тоже на разреженных битмэпах, оно и эффективно да и алгоритм красивый )) Да и либы почти на всех языках есть, они уже даже способ хранения стандартизировали. В статье используется redis, там эта реализация битмэпов под капотом.
10-гигабайтный битмап в оперативной памяти. Очень неэкономно и очень быстро.
Странный вопрос, но как докер улучшит итоговый результат и по каким критериям?
На днях тоже наткнулся на это тестовое задание. Оно было менее лаконичное.
Если мы с автором поста решали одно и то же задание, то, на мой взгляд, это решение не полное решение задачи.
В тексте указано, что необходим самостоятельный сервис, который будет отвечать за 1мс. То есть этим сервисом предполагается пользоваться не только в рамках тех 10 млн пользователей. Иначе можно было бы распаковать файл, положить в хэш таблицу, пробежаться по своей базе, сделать проверки и profit.
Чтобы сервис отдавал ответ за 1мс, необходимо не только алгоритм определения валидности продумать, но и остальные расходы. В первую очередь сеть. Если вы развернёте на локальной машине почти любой веб сервер, то самый простой GET запрос с этой же машины будет выполняться больше 1мс. Это связано с тем, что мы неизбежно будем тратить время на тройное рукопожатие. Тем более в предложенном решении предлагается еще и ходить в редис, что по той же причине только удвоит затраты на сеть.
На мой взгляд, в задаче необходимо отказаться от промежуточного веб сервера, реализовав обработку подключений внутри своего сервиса, использовать персистентное HTTP подключение, а данные хранить в памяти процесса. При этом я согласен с автором в части структуры хранения данных.
Более полный текст задания
**Задача:** есть приложение с базой клиентов, порядка 10 млн. У всех заполнены данные паспортов, которые могут просрочиться, быть утеряны и т.д. В связи с этим нужна система для проверки валидности этих паспортов на основе данных ФМС.
Задание по сути — создание микросервиса. Не библиотеки, а именно самостоятельного сервиса.
**Требования:** время ответа на запрос 1ms, uptime 99%. Больше требований нет, остальное на своё усмотрение.
Задание по сути — создание микросервиса. Не библиотеки, а именно самостоятельного сервиса.
**Требования:** время ответа на запрос 1ms, uptime 99%. Больше требований нет, остальное на своё усмотрение.
Если мы с автором поста решали одно и то же задание, то, на мой взгляд, это решение не полное решение задачи.
В тексте указано, что необходим самостоятельный сервис, который будет отвечать за 1мс. То есть этим сервисом предполагается пользоваться не только в рамках тех 10 млн пользователей. Иначе можно было бы распаковать файл, положить в хэш таблицу, пробежаться по своей базе, сделать проверки и profit.
Чтобы сервис отдавал ответ за 1мс, необходимо не только алгоритм определения валидности продумать, но и остальные расходы. В первую очередь сеть. Если вы развернёте на локальной машине почти любой веб сервер, то самый простой GET запрос с этой же машины будет выполняться больше 1мс. Это связано с тем, что мы неизбежно будем тратить время на тройное рукопожатие. Тем более в предложенном решении предлагается еще и ходить в редис, что по той же причине только удвоит затраты на сеть.
На мой взгляд, в задаче необходимо отказаться от промежуточного веб сервера, реализовав обработку подключений внутри своего сервиса, использовать персистентное HTTP подключение, а данные хранить в памяти процесса. При этом я согласен с автором в части структуры хранения данных.
Если мы с автором поста решали одно и то же задание, то, на мой взгляд, это решение не полное решение задачи.
+1, из текста статьи:
Однажды, в качестве тестового задания на позицию PHP разработчика была предложена задача реализации сервиса проверки номеров паспортов граждан РФ на предмет нахождения в списке недействительных.
А в итоге была реализована библиотека, которая общается с редисом.
На мой взгляд, в задаче необходимо отказаться от промежуточного веб сервера, реализовав обработку подключений внутри своего сервиса, использовать персистентное HTTP подключение, а данные хранить в памяти процесса.
Имхо, http очень дорого в данном случае, и стоит использовать соединение на сокетах и какой-нибудь лёгкий бинарный протокол.
P.S. В статье ничего не написано про то, отдаёт ли реализация ответ за 1 ms, а это одно из основных требований.
P.P.S. Про экономию памяти было интересно :)
Имхо, http очень дорого в данном случае, и стоит использовать соединение на сокетах и какой-нибудь лёгкий бинарный протокол.
Главное в прод такое не тащить. Пока у вас не онлайн игры и прочее подобное с требованием к миллисекундам надо использовать только http.
Стандартность, удобность и фичастость окупится многократно при эксплуатации.
Главное в прод такое не тащить. Пока у вас не онлайн игры и прочее подобное с требованием к миллисекундам надо использовать только http.
Я писал про данный случай — где требование 1мс и вроде речь шла про язык php.
Лучше такое писать. А потом такое в проде видишь…
Надо переложить небольшой джейсон с любой приемлимой скоростью, а внутри чуть-ли не ассемблер. Ведь так же быстрее.
Или как тут. Надо хранить в памяти сервера (Одного сервера, не 100, не 1000 серверов. Может 2-3 для отказоустойчивости) что-то небольшое. В гигабайт влезет, если нормально сделать. Нет, надо применить битовую магию и ужать до 100 мегабайт. И в итоге код проще выкинуть и написать заново чем добавить новую нужную фичу.
Надо переложить небольшой джейсон с любой приемлимой скоростью, а внутри чуть-ли не ассемблер. Ведь так же быстрее.
Или как тут. Надо хранить в памяти сервера (Одного сервера, не 100, не 1000 серверов. Может 2-3 для отказоустойчивости) что-то небольшое. В гигабайт влезет, если нормально сделать. Нет, надо применить битовую магию и ужать до 100 мегабайт. И в итоге код проще выкинуть и написать заново чем добавить новую нужную фичу.
Так ведь и статья про мегабайты, а не про миллисекунды. О них как-нибудь в другой раз (спойлер: keep-alive и persistent connection творят чудеса).
Но даже в таком виде оно может 1мс.
Но даже в таком виде оно может 1мс.
Всё верно. Но это тема для отдельной статьи, первым комментарием к которой будет: «На Go это можно сделать проще/быстрее».
Собственно, реализация на Go от автора RGr.
Sign up to leave a comment.
Паспортный контроль, или Как сжать полтора гигабайта до 42 мегабайт