Самый быстрый способ вывода строки из большого файла по номеру

На си накатать.

Это точно будет быстрее? Альтернативы попроще чем-то более стандартным нет?

Попробовал на python - еще хуже вышло

real	0m8.603s
user	0m0.876s
sys	0m0.344s

Создать индекс: номер строки → позиция в файле, по нему выбирать.

Создать индекс: номер строки → позиция в файле, по нему выбирать.

Поддерживаю. Только как это нормально сделать?

Наговноскриптил такое.

#!/bin/bash
# usage ./createIndex <data_file> <index_file> 
FILE=$1
INDEXFILE=$2
grep -Enra --byte-offset "^" $FILE | grep -Eao "^[0-9]*:[0-9]*" | awk -F':' '{ printf("%.18d:%.20d\n", $1, $2); }' > $INDEXFILE


#!/bin/bash
# usage ./getLine <data_file> <index_file> <linenum>
FILE=$1
INDEXFILE=$2
LINENUM=$[ $3 - 1 ];
L_OFFSET=$[ $LINENUM * 40 + 1 ];
OFFSET="$(tail -c +$L_OFFSET $INDEXFILE | head -n 1 | awk -F':' '{print $2 + 1;}')"
tail -c +$OFFSET $FILE | head -n 1

Проверил на больших (1.5G) бинарных файлах.

~ $ time head -n 2904776 data.binary | tail -n 1  # SSD
o_2~R.96`ÑæÄkO<Óié2CýT

real	0m0.477s
user	0m0.393s
sys	0m0.376s

$ time sed -n 2904776p data.binary
o_2~R.96`ÑæÄkO<Óié2CýT 

real	0m0.731s
user	0m0.544s
sys	0m0.188s


 $ time ./getLine data.binary lines.txt 2904776
o_2~R.96`ÑæÄkO<Óié2CýT 

real	0m0.011s
user	0m0.004s
sys	0m0.014s

UPD: номера строк же не используются.

#!/bin/bash
# usage ./createIndex <data_file> <index_file> 
FILE=$1
INDEXFILE=$2
grep -Ea --byte-offset "^" $FILE | grep -Eao "^[0-9]*" | awk '{ printf("%.19d\n", $1); }' > $INDEXFILE

#!/bin/bash
# usage ./getLine <data_file> <index_file> <linenum>
FILE=$1
INDEXFILE=$2
LINENUM=$[ $3 - 1 ];
L_OFFSET=$[ $LINENUM * 20 + 1 ];
OFFSET="$( echo $(tail -c +$L_OFFSET $INDEXFILE | head -n 1) + 1 | bc)"
tail -c +$OFFSET  $FILE | head -n 1

Ого, ты крутой, твой способ рабочий! Спасибо!

real	0m0.121s
user	0m0.000s
sys	0m0.000s

Единственный минус, что есть предварительная операция по созданию индекса, которая выполняется правда 1 раз, что не является проблемой.

Это точно будет быстрее?

Написать для вас - нет, Работать, если написать нормально - безусловно. Тот же sed (написанный на C) не может дать максимальной скорости по причине своей универсальности, то есть не точно заточенностью под вашу узкую задачу.

Единственный минус, что есть предварительная операция по созданию индекса, которая выполняется правда 1 раз, что не является проблемой.

Ну можно ещё писать строками фиксированного размера. И тогда условие - 1 раз будет не обязательным, можно будет менять такой файл произвольно.

Нужно быть осторожным с ключом -n у sed'а и не забывать завершать обработку файла.

$ file tst.txt 
tst.txt: ASCII text
$ wc -lc tst.txt 
  25709551 1979635355 tst.txt
$ time sed '3000000!d;q' tst.txt 
UyazaWZWySxJZTTbNJuyNPCc7alMAFmgGu+FgP0UEO4Nd9FdKoOUl68vQEf6dkAVCYROU8gtl6GT

real    0m0,143s
user    0m0,114s
sys     0m0,029s
$ time sed -n '3000000!d;p;q' tst.txt  
UyazaWZWySxJZTTbNJuyNPCc7alMAFmgGu+FgP0UEO4Nd9FdKoOUl68vQEf6dkAVCYROU8gtl6GT

real    0m0,140s
user    0m0,104s
sys     0m0,037s
$ time sed -n '3000000p' tst.txt   
UyazaWZWySxJZTTbNJuyNPCc7alMAFmgGu+FgP0UEO4Nd9FdKoOUl68vQEf6dkAVCYROU8gtl6GT

real    0m1,169s
user    0m0,901s
sys     0m0,269s

awk 'FNR==3000000{print}' big_file

Теперь запусти с mawk

Да, интересно посмотреть, насколько это будет быстрей.

Ого, mawk действительно крут

real	0m0.470s
user	0m0.376s
sys	0m0.088s

у mawk есть некоторые оптимизации, и он скорее всего не делает лишнюю работу - например, не бьет ввод на колонки, если доступ к полям не используется, как в этом коде, и скорее всего не продолжает работу если условия паттернов больше заведомо не выполнятся.

Да, но все равно метод от Tanger предварительного индексирования рулит, после этого выборки по номеру просто по нулям по времени. Пока быстрее этого ничего и нет.

Вот на C, работает быстрее: https://github.com/tarwirdur/line_break_indexer

Пока быстрее этого ничего и нет.

В смысле «пока»? Предварительное индексирование - общеизвестный метод с известными проблемами и в ТЗ должно быть озвучено - допустимы ли такие проблемы.

Спасибо! Это работает, прчием еще быстрее!

valet, а какую практическую задачу ты решаешь?

Строки разделяются LF? Тогда их все искать и считать придется.