Суть задачи: "Есть файл, в котором 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: <?php $substr = $argv[1]; $f = fopen(...); while ($part = fread($f, 500000000)) { if (strpos($part, $substr) !== false) die('YES'); } 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: <?php function randomHex40() { $binary = random_bytes(20); return bin2hex($binary); } $f = fopen('./bigfile.txt', 'w'); for ($i = 0; $i < 75000000; $i++) { fwrite($f, randomHex40()."\n"); } fclose($f); findsubstring.php PHP: <?php if ($argc != 2 || !preg_match('/^[\da-f]{20}$/', $argv[1])) { die("Usage: php findsubstring.php hexadecimal20\n"); } $substr = $argv[1]; $f = fopen('./bigfile.txt', 'r'); while ($part = fread($f, 512500000)) { echo '.'; if (strpos($part, $substr) !== false) die("YES\n"); unset($part); } die("NO\n"); $ time php findsubstring.php d1f59d95d7947eec2f2f
что характерно, уменьшение размера куска в 10 или 100 раз очень слабо влияет на итоговое время выполнения ))) видимо критична скорость чтения с диска, она даёт основной расход времени. на более шустром SSD возможно я бы уложился в секунду
Цитата: "В индексе N символов из найденного регуляркой" это и есть подробности. 3-4-5 символов, сколько влезет. Даже пара символов из хеша ускорит поиск в разы. Другое дело, что я не знаю готового решения для такой индексации. Может оно и есть. А может придётся самому изобретать.