Помогите решить задачку (обработка 75млн sha-1 хешированных строк)

Суть задачи:

«Есть файл, в котором 75 миллионов sha1 хэшированных строк, полученных из /dev/urandom.
На вход скрипт получает строку, соответствующую регулярному выражению ^[da-f]{20}$.
Необходимо написать функцию, которая проверит, есть ли в любой из строк в файле данная последовательность.
Скрипту доступно 512 Мб памяти и 800 Мб диска (не считая самого файла, он уже записан на диск) и 4 ядра по 900 МГц.
Заказчику скрипт поставляется в шифрованном виде, вместе с микрокомпьютером соответствующий характеристикам выше.
Максимальное время ответа 1 секунда.
На 1000 запросов допустимо 0 ложноположительных и 5 ложноотрицательных ответов.»

Скажу сразу что меня вогнало в ступор:
— плохо знаю регулярки, расшифруйте плиз ^[da-f]{20}$
— что имеется ввиду под «0 ложноположительных и 5 ложноотрицательных ответов» в привязке к тысяче вопросов? Вообще не понял о чём здесь идёт речь
— ну, и самое главное, вот эти характеристики микрокомпьютера которые указаны, я так понял указаны они неспроста, есть какие-то более оптимальные пути обработки 75млн строк за 1 секунду?

Заранее извиняюсь за банальность вопросов, с php совсем недавно работаю и хочется понять откуда подступиться к решению задачи

 

20 шестнадцатиричных цифр в нижнем регистре

Т.е. если твой скрипт 1000 раз дёрнули с разными данными, то не имеет права давать ложные положительные ответы, но имеет право дать 5 неправильных отрицательных ответов

 

«Более оптимальные» чем что?

 

Так тебе и задача — алгоритм изобрести, так чтобы ответ давало менее чем за секунду и ресурсов тратило не более указанных.
Или ты что, думал через — strpos?
Как правда с этими ограничениями по ресурсам тестировать…
В виртуалке так подгадать чтобы диска было свободного 800, процессоры, а памяти в php выставить…

 

Решение — только через предварительную индексацию файла. После этого можно хоть 100 запросов в секунду.

 

Ну вопрос и будет — как это лучше сделать.
Проблемы тут что
1. На индексацию не более 5 сек
2. Объем диска для индекса ограничен.
А ведь там по скромной прикидке
20 байт проверочная строка
20 их комбинаций в каждой строке, 75 млн строк,
28 гигабайт инфы

 

Чуваки, разве не очевидно что сложность процитированного задания и уровень компетенций ТСа _слишком_ различаются. Вы тут толковые коментарии пишете, но он их не воспримет. Эти коментарии имеют ценность только для вашего общения друг с другом.

Первое, надо оценить возможность работы в памяти целиком. 75 млн хешей sha1 это не менее 3Gb. В оговоренный RAM не лезет.

Далее, формат входного параметра задан как регулярка, но это НЕ значит что нам необходим regexp для задачи, это просто понятное грамотному прогеру описание: 20 шестнадцатеричных цифр. Ищем такую подстроку в файле. Я думаю тут важно что подстроку, а не полное совпадение со строкой.

Допускается некоторое количество ложноотрицательных ответов, это хорошо. Потому что если я буду считывать файл большими кусками и искать в куске подстроку (через strpos, он чертовски быстр), то нужный фрагмент может оказаться рассеченным на границе кусков. И тогда я его не найду. Очевидно кусков должно быть не более 6 (5 границ). Размер куска примерно 500млн байт. Это немного меньше 512Мб RAM. Штош, можно попытаться )))

Напрашивается примерно такой код:
«проверит, есть ли в любой из строк в файле данная последовательность.»

PHP:

1. <?php
2. $substr = $argv[1];
3. $f = fopen(…);
4. while ($part = fread($f, 500000000)) {
5.   if (strpos($part, $substr) !== false) die(‘YES’);
6. }
7. die(‘NO’);

выводит YES если есть нужная подстрока в любой из строк и NO иначе. можно было бы возвращать errorlevel для проверки в bash, а можно оформить в функию, это уже непринципиально, ящетаю.

 

Не получится у вас без индекса при исходных данных и отсутсвии супер-пупер компа, хоть ты тресни.

>> 1. На индексацию не более 5 сек
Глупости. -> Сколько надо.

>> как это лучше сделать.
Всё просто. У тебя есть условие: ^[da-f]{20}$
Создаёшь по ней индекс. В индексе N символов из найденного регуляркой и указатель на начало строки. N — столько, чтобы индекс был в памяти.
Далее поиск только по индексу, плюс чтение этих строк с диска, плюс уточняющий поиск по найденным строкам.
Поиск по индексу — очень быстро (RAM), чтение — быстро (SSD), уточняющий поиск — быстро (тот же strpos, например). Итого десятки запросов в секунду гарантированы.

 

насколько просто? ты учёл что хеши длиннее чем искомая подстрока?
80-битное число (20 шестнадцатеричных цифр) даёт нам довольно много вариантов. на вскидку, индекс не влезет в лимит по диску.
ну или как-то надо хитро действовать. поэтому прошу подробностей.

 

Я провел эксперимент со своими кусками и strpos() на файле из 75млн случайных строк — каждая строка это 40 символьное 16- ричное число + перевод строки. Консольному PHP 8 установил memory_limit 512M
Скрипту не надо нового дискового пространства, кроме того что уже занято файлом.
Максимальное время выполнения 1.8 сек. Это на старом i7 4 ядра 2.2Ггц в мобильном исполнении. Я считаю это неплохо, но видимо не является решением. Просто как инфа для размышления.

makebigfile.php

PHP:

1. <?php
2.  
3. function randomHex40()
4. {
5.   $binary = random_bytes(20);
6.   return bin2hex($binary);
7. }
8.  
9. $f = fopen(‘./bigfile.txt’, ‘w’);
10. for ($i = 0; $i < 75000000; $i++) {
11.   fwrite($f, randomHex40().«n«);
12. }
13. fclose($f);

findsubstring.php

PHP:

1. <?php
2.  
3. if ($argc != 2 || !preg_match(‘/^[da-f]{20}$/’, $argv[1])) {
4.   die(«Usage: php findsubstring.php hexadecimal20n«);
5. }
6.  
7. $substr = $argv[1];
8. $f = fopen(‘./bigfile.txt’, ‘r’);
9. while ($part = fread($f, 512500000)) {
10.   echo ‘.’;
11.   if (strpos($part, $substr) !== false) die(«YESn«);
12.   unset($part);
13. }
14. die(«NOn«);

$ time php findsubstring.php d1f59d95d7947eec2f2f

 

что характерно, уменьшение размера куска в 10 или 100 раз очень слабо влияет на итоговое время выполнения )))
видимо критична скорость чтения с диска, она даёт основной расход времени. на более шустром SSD возможно я бы уложился в секунду

 

Цитата: «В индексе N символов из найденного регуляркой» это и есть подробности.
3-4-5 символов, сколько влезет. Даже пара символов из хеша ускорит поиск в разы.
Другое дело, что я не знаю готового решения для такой индексации. Может оно и есть. А может придётся самому изобретать.