LINUX.ORG.RU

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

 , ,


1

3

Имеется гигантский файл на миллионы строк. Кто подскажет, как максимально быстро выбрать строку под конкретным номером, к примеру под номером 3000000.

Мои варианты:

1. sed

sed -n 3000000p big_file
не нравится, выполняет по time на моем файле
real	0m3.630s
user	0m0.408s
sys	0m0.056s

2. awk

awk 'FNR==3000000{print}' big_file
еще хуже
real	0m4.049s
user	0m0.416s
sys	0m0.064s

Есть еще варианты?


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

anonymous ()
Ответ на: комментарий от anonymous

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

valet ()

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

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

valet ()

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

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

#!/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
Tanger ★★★★★ ()
Последнее исправление: Tanger (всего исправлений: 1)
Ответ на: комментарий от Tanger

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
Tanger ★★★★★ ()
Ответ на: комментарий от Tanger

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

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

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

valet ()
head -3000000 big_file | tail -1
anonymous ()
Ответ на: комментарий от valet

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

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

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

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

vodz ★★★★★ ()
Последнее исправление: vodz (всего исправлений: 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
Deleted ()

awk 'FNR==3000000{print}' big_file

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

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

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

das_tier ★★★★★ ()
Ответ на: комментарий от yoghurt

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

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

valet ()
Ответ на: комментарий от valet

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

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

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

valet ()
Ответ на: комментарий от valet

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

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

vodz ★★★★★ ()
Последнее исправление: vodz (всего исправлений: 1)

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.