Задачка, чтобы показать, что язык/технология не важны

[zhuravl]

Вынесено отсюда.

Смысл задачи в том, чтобы показать, что язык и технология не важны. Не важно на чем написана программа: на модном golang (а может ассемблере, java) или на javascript/ruby/visual basic в конце концов. Всего лишь нужен правильный алгоритм и структура данных для решения.

Само решение не публикую, уверен что на привете быстро напишут ответ. Но если не напишут, то расскажу.

===

Задача: есть база данных в txt-формате, публично доступная с информацией о невалидных паспортах. Ее можно скачать, размер базы данных в несжатом виде примерно 2 гигабайта. В этой базе записи с 10-цифровыми номерами паспортов, которые не валидны. Пример записей:

9876543215
9876543210
9876543212
...

Вы разрабатываете код для портативного устройства-сканера с ограниченной памятью и диском (1Гб свободного места), которое работает под ОС linux. Ваша задача - написать код, который будет работать как можно быстрее. Для простоты это должна быть консольная программа, которая принимает один аргумент - номер паспорта, выдает "1" на выходе если паспорт валидный и "0", если паспорт не валидный (т.е. содержится в этой базе).

Подумайте и скажите что вы сделаете для того, чтобы программа работала максимально быстро. Какие алгоритмы будете использовать, какие структуры данных и вспомогательные средства (если потребуется).

[Dweller]

2 ГБ это 200 млн записей?
Тогда двоичный поиск по массиву где отсортированные "якорные" номера будут идти через каждые 1000 номеров, а 1000 номеров будут закодированы как incremental index, в нем уже будет метод перебора.

[Pantigalt]

Подумайте и скажите что вы сделаете для того, чтобы программа работала максимально быстро. Какие алгоритмы будете использовать, какие структуры данных и вспомогательные средства (если потребуется).

1. Мы не можем разместить все числа в оперативной памяти (памяти ограничено). Из этого следует что размещать надо на диске.
Примечание: Если памяти было бы много то наверное самым быстрым способом было бы размещать все в памяти и делать что то типа хэш-таблицы.
2. Размер записей в несжатом виде 2 Гб. Следовательно записей не больше 200 миллионов. Так как у нас всего 1 Гб то на хранение одного номер не может тратится больше 5 байтов. С другой стороны номера состоят из 10 цифр (10 миллиардов), это чуть больше 4 миллиарда (число из 4 байтов). Следовательно мы можем разместить все числа на диске.
3. Так как диск медленный по сравнению с оперативной памятью нам нужно к нему как можно меньше обращаться. Это приводит нас к стандартному решению типа B-tree. Далее очевидно поиск по B-дереву.

А вообще надо размещать на сервере где нет таких жесткий ограничений

[DropAndDrag]

1. 2 ГБ / 10 (байт в цифре) * 4.25 байта (10 цифр -> 34 бита) < 1 ГБ. так что можно запихать в память 34 бита отсортированный массив и там уж бинарным поиском. (у Patigalt вариант 2 такой же, но про побитное размещение не написано)
2. если оставшегося места на программу не хватит, то создал бы кучу маленьких файлов
- название 9 цифр, а в файле до 10 однозначных цифр, которые невалидные паспорта
- название 8 цифр, а в файле до 100 двухзначных цифр, которые невалидные паспорта
придется обращаться к диску, но считывать очень мало.

[Pantigalt]

1. 2 ГБ / 10 (байт в цифре) * 4.25 байта (10 цифр -> 34 бита) < 1 ГБ. так что можно запихать в память 34 бита отсортированный массив и там уж бинарным поиском. (у Patigalt вариант 2 такой же, но про побитное размещение не написано)

1 Гб как я понял из постановки задачи относится только к диску. Размер ОЗУ неизвестен.
Хотя если был бы хотя бы 1.25 миллиардов бит (всего лишь примерно на 25% больше чем в вашем примере) то можно было бы сделать 10 миллиардный массив битов и хранить в нем флаг валидности номера. Было бы супер быстро за гарантированное константное время.

В общем можно предложить смешанный вариант.

1. 10 миллиардов вариантов номеров разбить на 5 миллиардов пар чисел, скажем {0,1}..{8,9}..{9876543214, 9876543215}...
2. Хранить в ОЗУ этот массив, битовое значение и индекс вместе будут указывать на то являются ли оба числа валидными номерами (значение 0). если хотя бы одно число невалидно то ставим 1.
3. Если хотя бы одно число невалидно лезем на диск и сверяем там (используя B-дерево например).
4. Соотношение валидных к невалидным вариантов 50 к 1, следовательно только 2-4 процента времени будет лезть на диск.
5. Если разбивать не на 2 а на N то можно уменьшить размер требуемой памяти за счет увеличения обращений к диску.
При N>50 (~50 Мб) не имеет особого смысла применять этот метод.

[DropAndDrag]

и действительно 1 ГБ на диске ...
если обычной памяти выше крыши, то на диске держать tar и все дела.

[valchkou]

1) отсортировать номера на нормальном железе, разбить на много мелких файлов и запаковать.
+ создаем 1 индекс файл, который будет хранить {range: fileName} pairs
2) скопировать все это барахло на ущербное железо.
3) индекс файл загрузить в память в Tree like collection(TreeMap)
4) по входному номеру,тексту находим range: fileName
5) загружаем, распаковываем соотв файл в память в Set (hashtable)
6) return set.contains(value)
7) оставляем файл(TreeMap) в памяти пока хватает места.

[Krys-Krys]

Хорошая задачка для начала разговора и чтобы посмотреть как кандидат мыслит. Но далеко не определяющая. Есть очень много теоретиков, кто прекрасно решает проблемы в теории, но вот на компе и строчки кода написать не сможет, т к в глаза не видел сей код.

[valchkou]

а если устройство умеет подключаться к интернету, то задача упрощается до 3х строчек.
и никаких файлов, коллекций, структур, велосипедов не потребуется.

[Krys-Krys]

Cчас в Бэй Эрии очень модно спрашивать алгоритмы всякие. Причем я могу понять компании типа Гугла и т д, которые решают сложные задачи. Но когда приходишь в "Рога и Копыта" (что 95% работодателей) и у тебя спрашивают только такие задачки, это немного удивляет... По крайней мере меня.

[zhuravl]

Все правильно практически, в реальности задача была решена следующим способом. Перед закачкой данных в устройсто они сортируются (для того, чтобы они были при пригодны для алгоритма binary search). Для удобства данные разбиваются на 9 файлов, где номер файла - первая цифра паспорта. Остальные цифры просто пакуются в DWORD. Ну а дальше при помощи binary search довольно просто прочесть данные с диска за несколько операций. Программка на python справлялась с этим на ура.

[mskmel]

программа работала максимальнобыстро

Для удобства данные разбиваются на 9 файлов, где номер файла - первая цифра паспорта. Остальные цифры просто пакуются в DWORD. Ну а дальше при помощи binary search довольно просто прочесть данные с диска за несколько операций. Программка на python справлялась с этим на ура.

В общем то задачка решена, но как по мне костыль. Почему 9, а не 99?
Если все номера паспортов начинаются с числа 1 например, или просто неравномерное распределение, то будет тормозить на отдельных номерах паспортов.

На источнике сделать:

Code: Select all

for l in $(zcat /tmp/passports.gz | sort | uniq)
do
    fp=$(echo $l | md5sum - | cut -c 1-2)
    echo $l >> $fp.passports
done

gzip $fp.passports*

"Консольная программа" на недокомпьютере

Code: Select all

echo -n "Pass #"; read N; fp=$(echo $N | md5sum - | cut -c 1-2); zcat $fp.passports.gz  | grep -q $N && echo 1 || echo 0

Да, это не красивые бинарные поиски, но распаковать\погрепать 1MB архив это доли секунды почти на всём, что может запустить Linux.

PS: md5sum - может быть не быстро так много раз, и вообще не уверен на счёт скорости подготовительной части

[nightmare2]

Все правильно практически, в реальности задача была решена следующим способом. Перед закачкой данных в устройсто они сортируются (для того, чтобы они были при пригодны для алгоритма binary search). Для удобства данные разбиваются на 9 файлов, где номер файла - первая цифра паспорта. Остальные цифры просто пакуются в DWORD. Ну а дальше при помощи binary search довольно просто прочесть данные с диска за несколько операций. Программка на python справлялась с этим на ура.

A почему просто не загрузить данные в БД, проиндексировать.
Написать сервис, который будет проверять номер и возвращать 0/1.
Это даст дополнительные преимущества:
1. Всегда свежая инфа по поддельным номерам.
2. Сервер будет запоминать все запросы для последующего анализа (когда, где, кто запросил).
3. Менту будет труднее просто взять на лапу и отпустить владельца липового паспорта.
4. Возможность мониторинга определенных номеров.
5. Возможность мониторинга отдельных ментов.
6. ...

Допускаю, что интернет есть не везде и в этом случае нужна локальная копия.
Здесь все упрется в возможности девайса, но в любом случае, система должна накапливать информацию и синхронизироваться с сервером.
ИМХО.

[viewbelle]

перед обращением на диск, сделала бы проверку на фильтре блума, сидящем в оперативке.

[zhuravl]

A почему просто не загрузить данные в БД, проиндексировать.

requirements были такие.

[Dweller]

Все правильно практически, в реальности задача была решена следующим способом. Перед закачкой данных в устройсто они сортируются (для того, чтобы они были при пригодны для алгоритма binary search). Для удобства данные разбиваются на 9 файлов, где номер файла - первая цифра паспорта. Остальные цифры просто пакуются в DWORD. Ну а дальше при помощи binary search довольно просто прочесть данные с диска за несколько операций. Программка на python справлялась с этим на ура.

И правда, с 5 байтами на 34-битное число можно уже ничего не упаковывать
Я бы усложнил задачу так чтобы было 3 байта или даже 2 байта в среднем на число, например, 600 МБ или 400 МБ диска

[ALV00]

Все же надо уточнять при постановке, какое решение нужно: теоретическое или практическое. А то вы сначала сказали, что языки не важны и т.д. и потом привели решение, привязанное к файловой системе.

[zhuravl]

А то вы сначала сказали, что языки не важны и т.д. и потом привели решение, привязанное к файловой системе.

язык это не файловая система

[viewbelle]

Вы поставили задачу так:
> Подумайте и скажите что вы сделаете для того,
> чтобы программа работала максимально быстро

- а оказывается, вам было достаточно, чтобы программа работала приемлемо быстро

а) зачем вообще обращаться к диску, если во большом проценте случаев можно без этого обойтись?

б) почему вы не принимаете во внимание, что чтение с диска все равно осуществляется страницами, причем если накопитель - магнитный диск, то на random read тратится заметно больше времени, чем на последовательное чтение. Очевидно, гигабайт, записанный на диск, надо делить не на 9 файлов, а на сотни.

[zhuravl]

Ну в нашем случае работало достаточно быстро. Если вы сделаете максимально быстро, скажите мне, я сделаю быстрее. Задачки составлять не мастер, так что извиняйте)

[SaintDog666]

Вынесено отсюда.
Вы разрабатываете код для портативного устройства-сканера с ограниченной памятью и диском (1Гб свободного места), которое работает под ОС linux. Ваша задача - написать код, который будет работать как можно быстрее.

Работа со сканером занимает конечное время. Число записей не большое... так что. Условие "работать как можно быстрее" - бессмысленно. Даже самое кривое решение в лоб будет рабочим. Это если рассматривать задачу в контексте нейкого рабочего процесса. Юзкейсы? Не, не слышали )

[Boriskin]

б) почему вы не принимаете во внимание, что чтение с диска все равно осуществляется страницами, причем если накопитель - магнитный диск, то на random read тратится заметно больше времени, чем на последовательное чтение. Очевидно, гигабайт, записанный на диск, надо делить не на 9 файлов, а на сотни.

Более того, даже оперативка читается блоками, поэтому для максимальной производительности рекомендуется организовывать хранение данных последовательно в памяти (аля массив), а не случайно (аля дерево или мэп). Чувак из МС на 2014 билде рассказывал о реальном примере того, как переорганизация хранения данных в массив с мэпки увеличила реальную скорость проги в 5-6 раз.

[Pantigalt]

б) почему вы не принимаете во внимание, что чтение с диска все равно осуществляется страницами, причем если накопитель - магнитный диск, то на random read тратится заметно больше времени, чем на последовательное чтение. Очевидно, гигабайт, записанный на диск, надо делить не на 9 файлов, а на сотни.

Более того, даже оперативка читается блоками, поэтому для максимальной производительности рекомендуется организовывать хранение данных последовательно в памяти (аля массив), а не случайно (аля дерево или мэп). Чувак из МС на 2014 билде рассказывал о реальном примере того, как переорганизация хранения данных в массив с мэпки увеличила реальную скорость проги в 5-6 раз.

Все уже давно изобрели разработчики DB.
B-tree где размер узла = размер страницы (например 4к). Это такое 1000 узловое дерево а не бинарное.
В итоге для поиска любой записи не больше 3 чтений диска.
В варианте который я предлагал выше (смешанный) там вообще 98% времени к диску вообще не обращаемся.

[Boriskin]

Все уже давно изобрели разработчики DB.

Это все очень круто, но далеко не всегда применимо.

[Мальчик-Одуванчик]

Похоже весь спектр задач так называемого "динамического программирования" подходит под это условие.