За последние 24 часа нас посетил 20561 программист и 1125 роботов. Сейчас ищут 663 программиста ...

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

Тема в разделе "PHP для новичков", создана пользователем stereolaiho, 22 июл 2021.

Метки:
  1. stereolaiho

    stereolaiho Новичок

    С нами с:
    22 июл 2021
    Сообщения:
    1
    Симпатии:
    0
    Суть задачи:

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

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

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

    mkramer Суперстар
    Команда форума Модератор

    С нами с:
    20 июн 2012
    Сообщения:
    8.548
    Симпатии:
    1.754
    20 шестнадцатиричных цифр в нижнем регистре
    Т.е. если твой скрипт 1000 раз дёрнули с разными данными, то не имеет права давать ложные положительные ответы, но имеет право дать 5 неправильных отрицательных ответов
     
  3. roboformation

    roboformation Активный пользователь

    С нами с:
    30 авг 2020
    Сообщения:
    162
    Симпатии:
    40
    "Более оптимальные" чем что?
     
  4. Дюран

    Дюран Активный пользователь

    С нами с:
    9 мар 2018
    Сообщения:
    250
    Симпатии:
    19
    Так тебе и задача - алгоритм изобрести, так чтобы ответ давало менее чем за секунду и ресурсов тратило не более указанных.
    Или ты что, думал через - strpos?
    Как правда с этими ограничениями по ресурсам тестировать...
    В виртуалке так подгадать чтобы диска было свободного 800, процессоры, а памяти в php выставить...
     
  5. Chushkin

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Решение - только через предварительную индексацию файла. После этого можно хоть 100 запросов в секунду.
     
  6. Дюран

    Дюран Активный пользователь

    С нами с:
    9 мар 2018
    Сообщения:
    250
    Симпатии:
    19
    Ну вопрос и будет - как это лучше сделать.
    Проблемы тут что
    1. На индексацию не более 5 сек
    2. Объем диска для индекса ограничен.
    А ведь там по скромной прикидке
    20 байт проверочная строка
    20 их комбинаций в каждой строке, 75 млн строк,
    28 гигабайт инфы
     
  7. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

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

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

    Chushkin Активный пользователь

    С нами с:
    17 дек 2010
    Сообщения:
    1.062
    Симпатии:
    91
    Адрес:
    Мещёра, Центр, Болото N3
    Не получится у вас без индекса при исходных данных и отсутсвии супер-пупер компа, хоть ты тресни.

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

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

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    насколько просто? ты учёл что хеши длиннее чем искомая подстрока?
    80-битное число (20 шестнадцатеричных цифр) даёт нам довольно много вариантов. на вскидку, индекс не влезет в лимит по диску.
    ну или как-то надо хитро действовать. поэтому прошу подробностей.
     
    #9 artoodetoo, 26 июл 2021
    Последнее редактирование: 26 июл 2021
  10. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    Я провел эксперимент со своими кусками и 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 hexadecimal20\n");
    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("YES\n");
    12.   unset($part);
    13. }
    14. die("NO\n");
    $ time php findsubstring.php d1f59d95d7947eec2f2f
     
  11. artoodetoo

    artoodetoo Суперстар
    Команда форума Модератор

    С нами с:
    11 июн 2010
    Сообщения:
    11.068
    Симпатии:
    1.231
    Адрес:
    там-сям
    что характерно, уменьшение размера куска в 10 или 100 раз очень слабо влияет на итоговое время выполнения )))
    видимо критична скорость чтения с диска, она даёт основной расход времени. на более шустром SSD возможно я бы уложился в секунду
     
  12. Chushkin

    Chushkin Активный пользователь

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