Самый быстрый способ индексировать большой отсортированный хэш-файл

Question

Я создаю индекс на основе файла для отсортированного haveibeenpwned пароля текстового файла, и мне стало интересно, какой самый быстрый способ сделать это?

Я подумал, что хороший способ построить быстро-способный индекс - это разбить отсортированный файл на 256 файлов, названных по первым двум шестнадцатеричным цифрам (т.е. FF.txt, FE.txt и т. Д.). Я обнаружил, что ripgrep rg примерно в 5 раз быстрее, чем grep на моем компьютере. Поэтому я попробовал что-то вроде этого:

for i in {255..0} 
do
    start=$(date +%s)
    hex="$(printf  '%02x' $i  | tr [:lower:] [:upper:])"
    rg "^$hex" pwned-passwords-ntlm-ordered-by-hash-v4.txt > ntlm/$hex-ntlm.txt
    echo 0x$hex completed in $(($(date +%s) - $start)) seconds
done

Это самое быстрое решение, которое я мог придумать. ripgrep может создать каждый файл за 25 секунд. Итак, я смотрю около 100 минут, чтобы создать этот индекс. Когда я делю работу пополам и запускаю их параллельно, каждая пара файлов создается за 80 секунд. Поэтому, кажется, лучше всего позволить ripgrep поработать над своей магией и работать последовательно.

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

Answer 1

Вы читаете файл 256 раз, каждый раз проводя полное сканирование файла. Рассмотрим подход, который читает файл один раз, записывая каждую строку в дескриптор открытого файла. Я думаю, что Python будет простым выбором реализации (если это ваша вещь). Вы можете оптимизировать, сохраняя файл открытым, пока не найдете новый шестнадцатеричный код в начале строки. Если вы хотите быть еще умнее, нет необходимости проходить отсортированный файл построчно. Основываясь на подсказке Чарльза Даффи, вы можете создать эвристику для выборки файла (используя seek()), чтобы перейти к следующему шестнадцатеричному значению. Как только программа обнаружит смещение в байтах следующего шестнадцатеричного значения, блок байтов может быть записан в новый файл. Однако, поскольку это помечено как 'bash', давайте оставим решение в этом домене установленным:

while 
  read line 
do
  hex=${line:0:2}
  echo $line >> ntlm/$hex-ntlm.txt
done < pwned-passwords-ntlm-ordered-by-hash-v4.txt

Answer 2

ripgrep, как и любой другой инструмент, который вообще способен работать с несортированными входными файлами, является неподходящим инструментом для этой работы. Когда вы пытаетесь выполнить сортировку входных данных, вы хотите что-то, что может разделить ваш входной файл, чтобы найти позицию в логарифмическом времени. Для достаточно больших входных данных даже медленная реализация O (log n) будет быстрее, чем высокооптимизированная O (n).

pts-line-bisect является одним из таких инструментов, хотя, конечно, вы также можете написать свой собственный. Вам нужно будет написать его на языке с полным доступом к системному вызову seek(), который не отображается в bash.