Быстрый способ извлечения строк из большого файла с 80 миллиардами строк

Один вкладыш с использованиемsed:

sed -nf <(sed 's/$/p/' linenumberfile) contentfile

Чтобы сохранить первоначальный порядок в linenumberfile, вы можете выполнить

sed -nf <(sed 's/$/p/' linenumberfile) contentfile | paste <(nl linenumberfile | sort -n -k 2,2) - | sort -n -k 1,1 | cut -f 3-

Пояснение:

sed 's/$/p/' linenumberfile

генерирует сценарий sed, который печатает указанную строку. Затем сценарий передается в другойsed(с -n, чтобы подавить стандартную печать пространства шаблонов )для фактической печати. Поскольку sedобрабатывает файл содержимого построчно, вывод будет в том же порядке, что и в файле содержимого. Обратите внимание, что это однопроходный -процесс , поэтому я ожидаю, что скорость будет приемлемой.

Чтобы ускорить процесс, можно изменить pна {p;b}и добавить qв конец сгенерированного сценария sed.

Чтобы сохранить порядок строк в файле номеров строк, nlиспользуется для добавления «номеров строк» ​​в файл номеров строк. Итак, файл с номером строки

4
5
2

станет

1 4
2 5
3 2

В первом столбце записан исходный порядок в файле номеров строк.

Файл с «номера строк» ​​затем sorted и pasted на выходе sed, чтобы сделать

3 2    content_of_line2
1 4    content_of_line4
2 5    content_of_line5

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

1 4    content_of_line4
2 5    content_of_line5
3 2    content_of_line2

Наконец, cutиспользуется для удаления двух дополнительных столбцов.

Сравнительный анализ

Кажется, что sedлучше всего подходит для нескольких строк, но perl— это путь для 10000 строк, как указано в вопросе.

$ cat /proc/cpuinfo | grep -A 4 -m 1 processor
processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 60
model name  : Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

$ wc -l linenumber
10 linenumber

$ wc -l content
8982457 content

$ file content
content: ASCII text

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"    
real    0m0.791s
user    0m0.661s
sys     0m0.133s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.061s
user    0m2.908s
sys     0m0.152s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.706s
user    0m1.582s
sys     0m0.124s

$./genlinenumber.py 100 > linenumber
$ wc -l linenumber
100 linenumber

$ time bash -c "sed -nf <(sed 's/$/p/' linenumber) content > /dev/null"
real    0m3.326s
user    0m3.164s
sys     0m0.164s

$ time bash -c "awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' linenumber content > /dev/null"
real    0m3.055s
user    0m2.890s
sys     0m0.164s

$ time bash -c "./ln.pl linenumber content > /dev/null"
real    0m1.769s
user    0m1.604s
sys     0m0.165s

Если требуется сохранить порядок строк, можно использовать команду после первой |, так как время незначительно.

$./genlinenumber.py 10000 > linenumber
$ wc -l linenumber
10000 linenumber

$ time bash -c "./ln.pl linenumber content > extract"
real    0m1.933s
user    0m1.791s
sys     0m0.141s

$ time bash -c "paste <(nl linenumber | sort -n -k 2,2) extract | sort -n -k 1,1 | cut -f 3- > /dev/null"
real    0m0.018s
user    0m0.012s
sys     0m0.005s

micha@linux-micha: /tmp
$ cat numbers.txt
1
2
4
5

micha@linux-micha: /tmp
$ cat sentences.txt
alpha
bravo
charlie
delta
echo
foxtrott

micha@linux-micha: /tmp
$ awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' numbers.txt sentences.txt
alpha
bravo
delta
echo

Вот альтернативный метод и небольшой бенчмаркинг, добавленный к этому в ответе Weijun Zhou .

join

Предполагая, что у вас есть файл data, из которого вы хотите извлечь строки, и файл line_numbers, в котором перечислены номера строк, которые вы хотите извлечь, если порядок сортировки вывода не важен, вы можете использовать:

join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | cut -d ' ' -f 2-

Это пронумерует строки вашего файла data, соединит его с файлом padded_line_numbersв первом поле (по умолчанию )и распечатает общие строки (, исключая само поле соединения, что вырезано ).

joinтребует, чтобы входные файлы были отсортированы по алфавиту. Вышеупомянутый файл padded_line_numbersдолжен быть подготовлен путем заполнения слева -каждой строки вашего файла line_numbers. Например.:

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers >padded_line_numbers

Опции и аргументы -w 12 -n rzпредписывают nlвыводить 12-значные числа с ведущими нулями.

Если порядок сортировки вывода должен совпадать с порядком сортировки вашего файла line_numbers,вы можете использовать:

join -1 2 -2 1 <(nl padded_line_numbers | sort -k 2,2) \
    <(nl -w 12 -n rz data) |
    sort -k 2,2n |
    cut -d ' ' -f 3-

Где мы нумеруем файл padded_line_numbers, сортируем результат в алфавитном порядке по его второму полю, соединяем его с пронумерованным файлом dataи численно сортируем результат по исходному порядку сортировки padded_line_numbers.

Подстановка процессов здесь используется для удобства. Если вы не можете или не хотите полагаться на него и, скорее всего, не хотите тратить память, необходимую для создания обычных файлов для хранения промежуточных результатов, вы можете использовать именованные каналы :

mkfifo padded_line_numbers
mkfifo numbered_data

while read rownum; do
    printf '%.12d\n' "$rownum"
done <line_numbers | nl | sort -k 2,2 >padded_line_numbers &

nl -w 12 -n rz data >numbered_data &

join -1 2 -2 1 padded_line_numbers numbered_data | sort -k 2,2n | cut -d ' ' -f 3-

Сравнительный анализ

Поскольку особенностью вашего вопроса является количество строк в вашем dataфайле, я подумал, что было бы полезно протестировать альтернативные подходы с сопоставимым объемом данных.

Для тестов я использовал файл данных размером 3,2 миллиарда строк. Каждая строка представляет собой всего 2 байта мусора, поступающего из openssl enc, шестнадцатеричный -, закодированный с помощью od -An -tx1 -w2и с удаленными пробелами с помощью tr -d ' ':

$ head -n 3 data
c15d
061d
5787

$ wc -l data
3221254963 data

Файл line_numbersбыл создан путем случайного выбора 10 000 чисел от 1 до 3 221 254 963 без повторений с использованием shufиз GNU Coreutils:

shuf -i 1-"$(wc -l <data)" -n 10000 >line_numbers

Средой тестирования был ноутбук с четырехъядерным -процессором i7 -2670QM Intel, 16 ГиБ памяти, хранилищем SSD, GNU/Linux, bash5.0 и инструментами GNU.
Единственным измерением, которое я измерил, было время выполнения с помощью встроенной оболочки time.

Вот думаю:

• Решение sedиз ответа Weijun Zhou .
• Решение awkиз ответа Миши .
• Решение perlиз ответа Вюртеля .
• Решение joinвыше.

perlкажется, самый быстрый:

$ time perl_script line_numbers data | wc -l
10000

real    14m51.597s
user    14m41.878s
sys     0m9.299s

awkпроизводительность выглядит сопоставимой:

$ time awk 'FNR==NR { seen[$0]++ }; FNR!=NR && FNR in seen' line_numbers data | wc -l
10000

real    29m3.808s
user    28m52.616s
sys     0m10.709s

join, тожекажется сопоставимым:

$ time join <(sort padded_line_numbers) <(nl -w 12 -n rz data) | wc -l
10000

real    28m24.053s
user    27m52.857s
sys     0m28.958s

Обратите внимание, что отсортированная версия, упомянутая выше, почти не имеет снижения производительности по сравнению с этой.

Наконец, sedкажется значительно медленнее :Я убил его примерно через девять часов:

$ time sed -nf <(sed 's/$/p/' line_numbers) data | wc -l
^C

real    551m12.747s
user    550m53.390s
sys     0m15.624s

Я бы использовал для этого Perl-скрипт. Я придумал это:

#!/usr/bin/perl

# usage: thisscript linenumberslist.txt contentsfile

unless (open(IN, $ARGV[0])) {
        die "Can't open list of line numbers file '$ARGV[0]'\n";
}
my %linenumbers = ();
while (<IN>) {
        chomp;
        $linenumbers{$_} = 1;
}

unless (open(IN, $ARGV[1])) {
        die "Can't open contents file '$ARGV[1]'\n";
}
$. = 0;
while (<IN>) {
        print if defined $linenumbers{$.};
}

exit;

Это сначала считывает список номеров строк, которые нас интересуют, в ассоциативный массив, где номера строк являются ключом.chompудаляет новую строку в конце строки, $_— это сама строка.

Затем открывается файл данных, и когда номер строки является существующим ключом в массиве номеров строк, строка печатается.

$.— это счетчик номеров строк perl, который увеличивается при каждой прочитанной строке. Поскольку это считается по файлам, я сбрасываю его на ноль, прежде чем читать какие-либо строки файла данных.

Вероятно, это можно было бы написать намного больше в стиле "perl", но я предпочитаю, чтобы это было немного более читабельным.

Если список строк, которые вы хотите извлечь, очень велик, это может быть не самый эффективный способ, но я считаю, что Perl часто удивительно эффективен в таких вещах.

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