Comments 58
А зачем вся эта свистопляска с номерами и сериями? Просто собрать из них 10-значный номер, по ним индексировать и искать.
И не забыть сделать реверсивный индекс — будет работать быстрее.
По-моему можно просто сделать 1 колонку с 10-значным номером PRIMARY KEY без индексов
При создании PK всегда создается индекс, происходит это не явно.
С номерами паспортов проблема в том, левая часть последовательности чисел меняется реже чем правая(как с номерами телефонов +7915 и т.д. ), что приводит к несбалансированности бинарного дерева индекса. В таких случаях идеально использовать реверсивный индекс.
С номерами паспортов проблема в том, левая часть последовательности чисел меняется реже чем правая(как с номерами телефонов +7915 и т.д. ), что приводит к несбалансированности бинарного дерева индекса. В таких случаях идеально использовать реверсивный индекс.
Ради интереса сделал таблицу с одной колонкой с 10-значным номером и PRIMARY KEY, в итоге таблица получилась 2,4 ГБ.
Просто собрать из них 10-значный номер, по ним индексировать и искать.
Ну просто сделать, что оно работало конечно можно, только места это занимать будет ещё больше. А работать еще и медленее
Для 10-значного номера вы какой тип данных предлагаете BigInt? Т.е. 8 байт, вместо 5 байт. Также в индексе будут 8 байтные значение вместо 3 байтных.
Я не понял, с базой вы по сети работали, а файл лежит не в расшаренной папке, а локально на компе, да?
Предлагаю файлик bench.php из архива посмотреть, там автор на каждый запрос делает соединение к базе данных =)
Даже не знаю как это можно прокомментировать… 30+ лет вроде бы автору…
Даже не знаю как это можно прокомментировать… 30+ лет вроде бы автору…
Хмммм, невнимательно прочитал статью, но «пакетного» поиска в том файле нет.
Там в статье на которую вы ссылаетесь (надо было дать статью на ветку обсуждений) файлик в 1Gb, говорят. Если БД сможет его прожевать, то даже с переподключением будет быстрее работать, чем перечитывание этого файла для каждого запроса поиска. Что именно вы хотели доказать?
Там в статье на которую вы ссылаетесь (надо было дать статью на ветку обсуждений) файлик в 1Gb, говорят. Если БД сможет его прожевать, то даже с переподключением будет быстрее работать, чем перечитывание этого файла для каждого запроса поиска. Что именно вы хотели доказать?
Что-то у вас плохо с внимательностью. У меня БД была с кучей памяти, она могла всё включая данные и индексы положить в память, но тут чисто алгоритмически мой вариант на порядок проще. Мне в индексе вообще не нужен поиск, так как я сразу по номеру определяю смещение, а MySQL нужно сначала найти нужный элемент индекса (да он не перебором всего индекса делается, но это существенно медленнее, чем сделать один fseek). Да банально сравните размер индекса в моем варианте 4 МБ и у MySQL 900 МБ.
Если бы еще на Си тестил, то разница скорее всего еще больше была.
Если бы еще на Си тестил, то разница скорее всего еще больше была.
Осталось подождать пока тот же кодес перепишут на С и посмотреть на производительность…
Ну на Go тоже было бы интересно.
Держите.
Разница какая-то не слишком большая, 300к в батче жуёт за 1.393с (215362 п/с против 212116 у автора).
То ли я оптимизировать разучился, то ли спать надо по ночам… Пойду на профайлер помедитирую.
Разница какая-то не слишком большая, 300к в батче жуёт за 1.393с (215362 п/с против 212116 у автора).
То ли я оптимизировать разучился, то ли спать надо по ночам… Пойду на профайлер помедитирую.
Также на ассемблере, алгоритм оптимизировать с учётом особенностей работы с накопителями разных типов (диски, ssd).
В чём смысл разделения на серию\номер? Можно хранить как одно число, это позволит немного упростить код.
Если уж сказали в заголовке про «бинарное», то и задачу следовало бы решать на уровне битов.
То есть, создаем битовое поле с размерностью [9999 999999] бит, в котором у недействительных паспортов биты инверсные.
При практической реализации для такого поля применимо прозрачное сжатие данных.
На а поиск сводится к поиску бита в данном поле.
То есть, создаем битовое поле с размерностью [9999 999999] бит, в котором у недействительных паспортов биты инверсные.
При практической реализации для такого поля применимо прозрачное сжатие данных.
На а поиск сводится к поиску бита в данном поле.
Не путайте бинарный (двоичный) файл и битовую карту. По сути бинарный файл, это не текстовый файл, данные в который записываются в определенном формате.
Битовая карта для всех вариантов паспортов не очень подходит из-за размеров, она будет размером почти в 1,2 ГБ. Да можно сжать, но это замедляет работу.
Битовая карта для всех вариантов паспортов не очень подходит из-за размеров, она будет размером почти в 1,2 ГБ. Да можно сжать, но это замедляет работу.
Упаковал в такую структуру: каждая серия в виде биткарты (125 кб), при сохранении пакуется deflate
Файл:
1. Индекс серий, т.е. 10000 смещений где какая серия начинается
2. Сами биткарты.
Размер файла получился 25 Мб
Соответственно проверка — извлекаем биткарту нужной серии, распаковываем и проверяем бит соответствующий номеру.
Можно не паковать, тогда скорость проверки будет максимальна (два чтения) но размер 125 кб * кол-во серий, Сколько серий упоминается точно не помню, вроде ~5000, если так, то 625 Мб. Архиватором наверно пожмется до тех же 25 Мб
Если места на диске не жалко, то можно сразу занять 1,25 Гб (одна большая биткарта под все номера) и проверка будет в одно чтение одного байта.
Файл:
1. Индекс серий, т.е. 10000 смещений где какая серия начинается
2. Сами биткарты.
Размер файла получился 25 Мб
Соответственно проверка — извлекаем биткарту нужной серии, распаковываем и проверяем бит соответствующий номеру.
Можно не паковать, тогда скорость проверки будет максимальна (два чтения) но размер 125 кб * кол-во серий, Сколько серий упоминается точно не помню, вроде ~5000, если так, то 625 Мб. Архиватором наверно пожмется до тех же 25 Мб
Если места на диске не жалко, то можно сразу занять 1,25 Гб (одна большая биткарта под все номера) и проверка будет в одно чтение одного байта.
Статья хоть и интересная, но ее можно было бы назвать «Сравнение велосипеда и автомобиля.» Смотрите, велосипед не надо заправлять и он может ехать быстрее чем машина по лесу!
Но велосипед и авто решают разные задачи.
В любом случае велосипед не даст вам конкурентного доступа, масштабирования и т.д., изменения данных без блокировок и много много другого.
Считаю, что такое сравнение хоть и интересное, но не корректное. Делать категоричные вывод точно не стоит.
Но велосипед и авто решают разные задачи.
В любом случае велосипед не даст вам конкурентного доступа, масштабирования и т.д., изменения данных без блокировок и много много другого.
Считаю, что такое сравнение хоть и интересное, но не корректное. Делать категоричные вывод точно не стоит.
Вообще, статья о том, что гвозди можно и микроскопом забивать, но можно и более узкоспециализированным инструментом.
А в чем проблема с конкурентным доступом к файлу только на чтение, который обновляется в лучшем случае раз в день? Зачем в данном случае изменять данные без блокировок? Сгенерил новую базу, перевел симлинк на новый файл, или вы предлагаете еще искать изменения в CSV файле, чтобы добавить в MySQL только их? Кроме того базы заливались с помощью LOAD DATA в пустую таблицу, добавление данных с помощью INSERT будет заметно медленнее.
Кроме того, вы забываете, что MySQL был в идеальных условиях, на мощном тестовом сервере с кучей оперативки, и никаких обращений к нему кроме тестовых, а что будет когда таблицы будут вываливаться из кэша?
А в чем проблема с конкурентным доступом к файлу только на чтение, который обновляется в лучшем случае раз в день? Зачем в данном случае изменять данные без блокировок? Сгенерил новую базу, перевел симлинк на новый файл, или вы предлагаете еще искать изменения в CSV файле, чтобы добавить в MySQL только их? Кроме того базы заливались с помощью LOAD DATA в пустую таблицу, добавление данных с помощью INSERT будет заметно медленнее.
Кроме того, вы забываете, что MySQL был в идеальных условиях, на мощном тестовом сервере с кучей оперативки, и никаких обращений к нему кроме тестовых, а что будет когда таблицы будут вываливаться из кэша?
Очень хорошо начали с анализа данных и построения индекса по сериям вручную. Но закончили чтением километровой строки и поиском в ней данных. Вроде бы да — до 200 серий на один номер, поэтому не так страшно. Но можно еще улучшить. Серия — это число от 0000 до 9999, можно сделать один массив размером в 10000 / 8 = 1250 байт. Каждый бит в массиве соответствует своей серии. Проверка паспорта — проверка бита.
Этот массив будет очень сильно разреженным. Его хорошо сожмет zlib. Такие сжатые куски и держать в файле на диске. При чтении нужно будет считать очень мало данных и быстро на лету разжать.
Если не связываться с битовыми картами. То записываем все серии в виде 16-битных чисел, сортируем и с помощью деления пополам (bisect) очень быстро за логарифмическое время находим нужное. Можно использоват стандартный модуль, можно даже руками сделать: проверили первое число на вхождение, проверили последнее, затем прыжок в середину массива, опять смотрим больше-меньше и прыжок в нужную часть.
Этот массив будет очень сильно разреженным. Его хорошо сожмет zlib. Такие сжатые куски и держать в файле на диске. При чтении нужно будет считать очень мало данных и быстро на лету разжать.
Если не связываться с битовыми картами. То записываем все серии в виде 16-битных чисел, сортируем и с помощью деления пополам (bisect) очень быстро за логарифмическое время находим нужное. Можно использоват стандартный модуль, можно даже руками сделать: проверили первое число на вхождение, проверили последнее, затем прыжок в середину массива, опять смотрим больше-меньше и прыжок в нужную часть.
Вот тут немного странное место:
Представьте, что вы ищете серию 1234, и в списке серий есть такие:
0012 3400 1234
Если я верно помню php, то будет найдено первое вхождение подстроки 1234, но поскольку оно не на границе, то паспорт будет считаться валидным, а следующее вхождение серии проверено не будет.
// Поиск в списке серий
echo ($pos = strpos($series, $seria)) !== false && $pos % 2 == 0 ? 'INVALID' : 'VALID';
Представьте, что вы ищете серию 1234, и в списке серий есть такие:
0012 3400 1234
Если я верно помню php, то будет найдено первое вхождение подстроки 1234, но поскольку оно не на границе, то паспорт будет считаться валидным, а следующее вхождение серии проверено не будет.
UFO just landed and posted this here
Взбрела мне глупая мысль в голову.
А что если использовать номер паспорта и серию как индекс байта в файле, и проверять байт по индексу 1 или 0
9999999999 / 8 / 1024 / 1024 / 1024 = 1.164 гигабайта — размер файла для всех возможных паспортов.
А если возвращаться к Вашему примеру, то файл можно делать только для действительных паспортов. размер файла в байтах равен серии и номеру последнего. Если в запросе серия и номер больше файла, то паспорт недействителен. Ну а если меньше, то номер и серию делим на 8, получаем индекс байта и читаем из файла, позицию бита получаем из остатка от деления. Значение бита и будет действителен ли паспорт или нет.
А что если использовать номер паспорта и серию как индекс байта в файле, и проверять байт по индексу 1 или 0
9999999999 / 8 / 1024 / 1024 / 1024 = 1.164 гигабайта — размер файла для всех возможных паспортов.
А если возвращаться к Вашему примеру, то файл можно делать только для действительных паспортов. размер файла в байтах равен серии и номеру последнего. Если в запросе серия и номер больше файла, то паспорт недействителен. Ну а если меньше, то номер и серию делим на 8, получаем индекс байта и читаем из файла, позицию бита получаем из остатка от деления. Значение бита и будет действителен ли паспорт или нет.
Опечатался, индекс не байта, а бита и размер файла в битах.
Ну да, тут основная проблема, что возможных паспортов на 2 порядка больше, чем недействительных, плюс сильно неравномерное распределение, Есть серии для которых около 600 тысяч номеров, почти половина серий, для которых меньше 100 номеров. Всего серий используется 3043.
Именно так и надо решать эту задачу.
Для экономии места можно кластеризовать файл с битовой маской присутствия. Хотя в нормальных OS итак поддерживаются sparse файлы и реальный занимаемый объем на FS будет значительно меньше.
Если сделать mmap на этот 1.164GiB файлик или считать его в память то скорость проверки будет на порядки большей чем любое другое решение.
Для экономии места можно кластеризовать файл с битовой маской присутствия. Хотя в нормальных OS итак поддерживаются sparse файлы и реальный занимаемый объем на FS будет значительно меньше.
Если сделать mmap на этот 1.164GiB файлик или считать его в память то скорость проверки будет на порядки большей чем любое другое решение.
С академической точки зрения — интересно и полезно для обучения навыков програмирования.
С практической, учитывая нынешнюю копеечную стоимость железа (если сравнивать со стоимостью оплаты разработчика), извиняюсь за тавтологию — непрактично.
Кроме того на практике файл еще и обновлять часто бы пришлось — новые номера, ликвидированные старые и т.д.
С практической, учитывая нынешнюю копеечную стоимость железа (если сравнивать со стоимостью оплаты разработчика), извиняюсь за тавтологию — непрактично.
Кроме того на практике файл еще и обновлять часто бы пришлось — новые номера, ликвидированные старые и т.д.
А как вы обошли проблему с буквенными сериями? Там зоопарк того, что не кодируется в 2 байта (и вообще в число) — «06ОД», «23АГ», «8ЕР5», «X-АН»…
Мало того, ещё и формат записи разный — встречаются и «6-ОД» и «06ОД».
Мало того, ещё и формат записи разный — встречаются и «6-ОД» и «06ОД».
Ааааа! Я придумал, как находить бесплатную рабочую силу для решения разнообразных задач. Допустим, нужно научиться быстро проверять действительность паспорта. Ну или что-нибудь ещё. Пишем, скажем, плохое решение на некоем языке X (ну или вообще ничего не пишем). Затем вклиниваемся в холивар «X vs Y» и говорим там: «Есть такая-то задача, нужно минимизировать CPU, базы данных использовать нельзя, я написал на X, получилось плохо. А если бы написал на Y, получилось бы лучше. Значит, X сосёт». Можно придумать другие варианты. В результате начинается срач, люди начинают сами бесплатно выкладывать свои решения на разных языках, ещё стараются друг друга переплюнуть, строго соблюдают поставленные условия («никаких БД»), считают такты и пр. Каждый стремится доказать превосходство своего языка. В результате мы получаем много хороших решений на разных языках и остаётся только выбрать :)
Пинг chemistmail :)
Пинг chemistmail :)
Да ладно, прочитал по диагонали. Алгоритм так и не увидел.
Могу другую задачку подкинуть, повеселее.
Могу другую задачку подкинуть, повеселее.
Есть SET размер, Word32 * 255 (1095216660225), по сути битовый массив
Нужно:
1) его хранить, и место имеет очень большое значение
2) функция set :: i -> SET -> SET, 90% операций
3) функция get :: i -> SET -> Bool
4) функция size :: SET -> n, сколько всего записей в этом set
5) AND, OR, в общем полный спектр логических операций :: OP -> SET -> SET -> SET
6) конвертация в список, или в массив :: SET -> [i]
7) создание из списка :: [i] -> SET
А паспорта уже не интересны.
Нужно:
1) его хранить, и место имеет очень большое значение
2) функция set :: i -> SET -> SET, 90% операций
3) функция get :: i -> SET -> Bool
4) функция size :: SET -> n, сколько всего записей в этом set
5) AND, OR, в общем полный спектр логических операций :: OP -> SET -> SET -> SET
6) конвертация в список, или в массив :: SET -> [i]
7) создание из списка :: [i] -> SET
А паспорта уже не интересны.
Вопрос в том, что нужно на самом деле. То есть не как воспринял задачу программист — а что нужно бизнесу. У разработчиков часто бывает желание обобщить задачу, добавить чуть-чуть до красивого сферического коня в вакууме. Вроде бы мелочь, но задача становится в 100 раз сложнее или нерешаемой.
По описанию очень похоже на задачу подсчета уникальных значений в огромном сете.
Вопросы:
1. Насколько точно надо считать? Какая ошибка допустима?
2. Насколько быстро надо считать?
3. Сколько памяти?
4. Точно ли нужно получать элементы? По одиночке и списком?
А то может оказаться, что лучшее решение вероятностный алгоритм HyperLogLog, на русском описанный тут. Тогда совсем небольшого кол-ва памяти будет достаточно для очень больших множеств.
По описанию очень похоже на задачу подсчета уникальных значений в огромном сете.
Вопросы:
1. Насколько точно надо считать? Какая ошибка допустима?
2. Насколько быстро надо считать?
3. Сколько памяти?
4. Точно ли нужно получать элементы? По одиночке и списком?
А то может оказаться, что лучшее решение вероятностный алгоритм HyperLogLog, на русском описанный тут. Тогда совсем небольшого кол-ва памяти будет достаточно для очень больших множеств.
Сколько процентов множества занято? Условно говоря, если ожидается что там будет порядка десятков тысяч значений, то какая-нибудь хешмапа+связанный список могут оказаться самым простым и эффективным вариантом. Если будет занято процентов 30% то проще хранить подряд. Не такие космические цифры: 240 ≈ 1012, то есть примерно 1Тбит данных или 125Гбайт. Даже если тупо хранить битмапу такого размера, это не страшно — сейчас на любом ноуте можно встретить такой SSD-диск или даже больше. Mmap файла и вперед. Ось сама все подгрузит, закеширует, когда нужно выгрузит назад.
Занято от 0 до 30%.
таких битмапов сейчас 4000, а может быть еще больше.
Ошибки не допустимы, считать нужно точно и быстро, получать элементы по одиночке и списком. Собственно все операции я описал.
Железка: 128G оперативки, 1T диска ssd, 8 cpu.
Весь требуемый функционал описан выше, к нему rest api для полноты ощущений и все.
таких битмапов сейчас 4000, а может быть еще больше.
Ошибки не допустимы, считать нужно точно и быстро, получать элементы по одиночке и списком. Собственно все операции я описал.
Железка: 128G оперативки, 1T диска ssd, 8 cpu.
Весь требуемый функционал описан выше, к нему rest api для полноты ощущений и все.
А поток запросов на запись и чтение какой?
Какое чтение ожидается: Сколько примерно % будет попадать в сет, и сколько мимо?
Какое чтение ожидается: Сколько примерно % будет попадать в сет, и сколько мимо?
Запись в районе 90%, около 2000 запросов в секунду.
Стандартные инструменты смотрели? Например, redis?
Редис не пойдет. Объем данных не позволит.
Тут битмапы надо, плюс обвязку.
Что то типа такого: https://github.com/RoaringBitmap/roaring
на 400000000 записей получается в районе 40 мегабайт.
Тут битмапы надо, плюс обвязку.
Что то типа такого: https://github.com/RoaringBitmap/roaring
на 400000000 записей получается в районе 40 мегабайт.
В редисе есть битмапы. Объём данных позволит, судя по доке.
хм, спасибо. По идее должно хватить.
Я посмотрел: «на самом деле все уже украдено изобретено до нас».
Итого — в пределах одного хоста mmap может оказаться самой компактной и быстрой операцией. А может и нет. Нужно смотреть на распределение битов, как вы их будете писать. Если, например, вы знаете, что первые 2 байта намного вариативнее, чем последние 2, то можно писать байты задом наперед — так, чтобы использовать меньше 4КБ-страниц памяти и снизить нагрузку на систему.
$ truncate -s 5G mmap.txt
$ ls -al mmap.txt
-rw-rw-r-- 1 user user 5368709120 Авг 24 17:34 mmap.txt
# создали файл размером 5ГБ
# на диске он занимает всего 4КБ !
$ du -h mmap.txt
4K mmap.txt
# поработаем с ним
$ python
>>> import mmap
>>> f=open('mmap.txt', 'r+')
>>> m=mmap.mmap(f.fileno(), 0)
# запишем в 3 разные места файла что-нибудь
>>> m[1234567] = 'C'
>>> m[0x3030] = chr(0xff)
>>> m[0x10:0x14] = 4 * b'Z'
# далее жмем Ctrl+Z, и не закрывая или синкая файл, идем его изучать
[1]+ Stopped python
$ ls -l mmap.txt
-rw-rw-r-- 1 user user 5368709120 Авг 24 18:13 mmap.txt
# файл имеет все тот же размер в 5ГБ
$ du -h mmap.txt
12K mmap.txt
# но на диске его "раздуло" аж до 12 КБ !
# то есть умная файловая система хранит только те страницы памяти,
# в которые была произведена какая-то запись.
# Все остальные страницы памяти и место в файле выделено только виртуально.
# файл можно сжать с помощью bzip2 - поскольку он почти пустой, то сожмется в 12КБ.
# но! после распаковки новый файл будет занимать на диске настоящие 5ГБ.
# Дело в том, что bunzip2 честно запишет все 0х00 байты в файле, и ось так же честно перенесет их на диск.
# Конечно, приложив допусилия, это можно отфильтровать.
Итого — в пределах одного хоста mmap может оказаться самой компактной и быстрой операцией. А может и нет. Нужно смотреть на распределение битов, как вы их будете писать. Если, например, вы знаете, что первые 2 байта намного вариативнее, чем последние 2, то можно писать байты задом наперед — так, чтобы использовать меньше 4КБ-страниц памяти и снизить нагрузку на систему.
И да, язык тут роли не играет от слова совсем.
Sign up to leave a comment.
Поиск недействительных паспортов или учимся готовить бинарные файлы