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

stereolaiho

Суть задачи:

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

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

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

 

mkramer

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

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

 

roboformation

“Более оптимальные” чем что?

 

Дюран

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

 

Chushkin

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

 

Дюран

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

 

artoodetoo

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

Первое, надо оценить возможность работы в памяти целиком. 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, а можно оформить в функию, это уже непринципиально, ящетаю.

 

Chushkin

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

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

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

 

artoodetoo

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

 

artoodetoo

Я провел эксперимент со своими кусками и 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

 

artoodetoo

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

 

Chushkin

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

 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *