Фильтровать файл по номеру строки

Учитывая файл L с одним неотрицательным целым числом в строке и текстовым файлом F, какой бы быстрый способ сохранить только те строки в F, номер строки которых отображается в файле L?

Пример:

$ cat L.txt 1 3 $ cat F.txt Hello World Hallo Welt Hola mundo $ command-in-question -x L.txt F.txt Hello World Hola mundo 

Я ищу команду, которая может обрабатывать файл L с 500 миллионами или более записей; файл L сортируется численно.

Примечание. Я нахожусь на полпути к реализации для command-in-question но мне просто интересно, можно ли использовать некоторые инструменты Unix здесь.


Обновление: Спасибо за все ответы, я многому научился сегодня! Я хотел бы принять еще один ответ, но это невозможно.

10 Solutions collect form web for “Фильтровать файл по номеру строки”

С C опусканием значимых сообщений об ошибках:

 #include <stdio.h> #include <stdlib.h> int main (int argc, char *argv[]) { FILE *L; FILE *F; unsigned int to_print; unsigned int current = 0; char *line = NULL; size_t len = 0; if ((L = fopen(argv[1], "r")) == NULL) { return 1; } else if ((F = fopen(argv[2], "r")) == NULL) { fclose(L); return 1; } else { while (fscanf(L, "%u", &to_print) > 0) { while (getline(&line, &len, F) != -1 && ++current != to_print); if (current == to_print) { printf("%s", line); } } free(line); fclose(L); fclose(F); return 0; } } 

Я бы использовал awk , но не хранил весь контент L.txt в памяти и не делал ненужных хеш- L.txt ;-).

 list=L.txt file=F.txt LIST="$list" awk ' function nextline() { if ((getline n < list) <=0) exit } BEGIN{ list = ENVIRON["LIST"] nextline() } NR == n { print nextline() }' < "$file" 

Я бы использовал awk :

 awk 'NR==FNR {a[$1]; next}; FNR in a' L.txt F.txt 

Обновление: я сделал показатели производительности; похоже, эта версия еще лучше масштабируется с очень большими наборами данных (как в случае с заявленными требованиями), так как сравнение происходит очень быстро и перекомпенсирует усилия, необходимые для создания хеш-таблицы.

grep -n | sort | sed | cut

 ( export LC_ALL=C grep -n '' | sort -t: -nmk1,1 ./L - | sed /:/d\;n | cut -sd: -f2- ) <./F 

Это должно работать довольно быстро (некоторые временные тесты включены ниже) с вводом любого размера. Некоторые замечания о том, как:

  • export LC_ALL=C
    • Поскольку следующая операция заключается в том, чтобы получить весь файл ./F ./L строку с файлом ./L lineno, единственными символами, о которых нам действительно нужно будет беспокоиться, являются цифры ASCII [0-9] и : двоеточие.
    • По этой причине более просто беспокоиться о том, чтобы найти эти 11 символов в наборе из 128 возможных, чем если бы это касалось UTF-8.
  • grep -n ''
    • Это вставляет строку LINENO: в начало каждой строки в stdin – или <./F
  • sort -t: -nmk1,1 ./L -
    • sort не учитывает сортировку своих входных файлов вообще, и вместо этого (правильно) предполагает, что они предварительно заданы и -m erges их в -numerically отсортированном порядке, игнорируя в основном что-либо, кроме любого возможного -k1,1 st, встречающегося -t: двоеточия.
    • Хотя для этого может потребоваться некоторое временное пространство (в зависимости от того, насколько далеко могут произойти некоторые последовательности) , он не будет требовать многого по сравнению с правильным типом, и он будет очень быстрым, потому что он включает в себя нулевой обратный отсчет.
    • sort будет выводить один поток, где любое lineno в ./L будет непосредственно предшествовать соответствующим строкам в ./F . ./L всегда на первом месте, потому что они короче.
  • sed /:/d\;n
    • Если текущая строка соответствует значению /:/ двоеточие, выведите его из вывода. В противном случае автоматически распечатайте текущую и n строку.
    • Таким образом, sed sort только для последовательных пар линий, которые не соответствуют двоеточию и следующей строке – или только к линии из ./L а затем к следующей.
  • cut -sd: -f2-
    • cut -s uppresses выводит из своих входных строк, которые не содержат по крайней мере одну из своих строк -d: elimiter – и поэтому. / ./L линии полностью обрезаны.
    • Для тех линий, которые делают, их первое : двоеточие с разделителем-срезом cut – и, следовательно, все вставленные в grep lineno.

малый входной тест

 seq 5 | sed -ne'2,3!w /tmp/L s/.*/az &\& 0-9/p' >/tmp/F 

… генерирует 5 строк ввода образца. Затем…

 ( export LC_ALL=C; </tmp/F \ grep -n '' | sort -t: -nmk1,1 ./L - | sed /:/d\;n | cut -sd: -f2- )| head - /tmp[FL] 

… печать …

 ==> standard input <== az 1& 0-9 az 4& 0-9 az 5& 0-9 ==> /tmp/F <== az 1& 0-9 az 2& 0-9 az 3& 0-9 az 4& 0-9 az 5& 0-9 ==> /tmp/L <== 1 4 5 

более крупные приуроченные тесты

Я создал пару довольно больших файлов:

 seq 5000000 | tee /tmp/F | sort -R | head -n1500000 | sort -n >/tmp/L 

… которые помещают 5 мил линий в /tmp/F и 1.5mil случайно выбранные строки этого в /tmp/L Затем я сделал:

 time \ ( export LC_ALL=C grep -n '' | sort -t: -nmk1,1 ./L - | sed /:/d\;n | cut -sd: -f2- ) <./F |wc - l 

Он напечатал:

 1500000 grep -n '' \ 0.82s user 0.05s system 73% cpu 1.185 total sort -t: -nmk1,1 /tmp/L - \ 0.92s user 0.11s system 86% cpu 1.185 total sed /:/d\;n \ 1.02s user 0.14s system 98% cpu 1.185 total cut -sd: -f2- \ 0.79s user 0.17s system 80% cpu 1.184 total wc -l \ 0.05s user 0.07s system 10% cpu 1.183 total 

(Я добавил туда обратную косую черту)

Среди предлагаемых в настоящее время решений это самый быстрый из всех из них, но один из них, когда он противоположен набору данных, сгенерированному выше на моей машине. Из других только один приблизился к соперничеству за второе место, и это был peru meuh.

Это отнюдь не оригинальное решение – оно сократило треть времени выполнения благодаря советам / вдохновению, предлагаемым другими. Смотрите историю сообщений для более медленных решений (но почему?) .

Кроме того, стоит отметить, что некоторые другие ответы могут очень хорошо справляться, если бы не архитектура с несколькими процессорами моей системы и одновременное выполнение каждого из процессов в этом конвейере. Все они работают одновременно – каждый на своем собственном процессорном ядре – обходит данные и делает свою небольшую часть целого. Это довольно круто.

но самое быстрое решение …

Но это не самое быстрое решение. Самое быстрое решение, предлагаемое здесь, с рук, – это программа C. Я назвал его cselect . После копирования его в свой буфер обмена X я скомпилировал его так:

 xsel -bo | cc -xc - -o cselect 

Затем я сделал:

 time \ ./cselect /tmp/L /tmp/F | wc -l 

… и результаты были …

 1500000 ./cselect /tmp/L /tmp/F \ 0.50s user 0.05s system 99% cpu 0.551 total wc -l \ 0.05s user 0.05s system 19% cpu 0.551 total 

Просто для полноты: мы можем объединить отличный скрипт awk в ответе Стефана Хазеласа и скрипта perl в ответе kos, но не сохраняя весь список в памяти, в надежде, что perl может быть быстрее awk. (Я изменил порядок аргументов в соответствии с исходным вопросом).

 #!/usr/bin/env perl use strict; die "Usage: $0 lf\n" if $#ARGV+1 != 2; open(L,$ARGV[0]) or die "$ARGV[0]: $!"; open(F,$ARGV[1]) or die "$ARGV[1]: $!"; while(my $number = <L>){ #chop $number; while (<F>) { if($. == $number){ print; last; } } } 

Я написал простой скрипт Perl для этого:

Usage: script.pl inputfile_f inputfile_f

 #!/usr/bin/env perl $number_arguments = $#ARGV + 1; if ($number_arguments != 2) { die "Usage: script.pl inputfile_f inputfile_l\n"; } open($f, '<', $ARGV[0]) or die "$ARGV[0]: Not found\n"; open($l, '<', $ARGV[1]) or die "$ARGV[1]: Not found\n"; @line_numbers = <$l>; while ($line = <$f>) { $count_f ++; if ($count_f == @line_numbers[$count_l]) { print $line; $count_l ++; } } 
  • Загружает F.txt
  • Загружает L.txt
  • Сохраняет каждую строку L.txt в массив
  • Считывает F.txt по F.txt , отслеживая текущий номер строки и текущий индекс массива; увеличивает F.txt текущей строки F.txt ; если F.txt текущей строки F.txt соответствует содержимому массива в текущем индексе массива, он печатает текущую строку и увеличивает индекс

Соображения затрат и сложности :

Учитывая затраты на выполнение присвоений, затраты на сравнение и стоимость печати строк, учитывая, что N 1 является числом строк в F.txt и N 2 в качестве количества строк в L.txt , цикл while выполняется не более N 1 раз, что приводит к присвоениям 2N 1 + N 2 (очевидно, предполагая N 1 > N 2 ), сравнениям 2N 1 и N 2 отпечаткам; при равном стоимости каждой операции общая стоимость запуска цикла while равна 4N 1 + 2N 2 , что приводит к сложности сценария O (N).

Тестирование входного файла на 10 миллионов строк :

Используя файл F.txt размером в 10 миллионов строк, содержащий случайные строки F.txt 50 символов и файл L.txt размером в 10 миллионов строк, содержащий числа от 1 до 10000000 (наихудший сценарий):

 ~/tmp$ for ((i=0; i<3; i++)); do time ./script.pl F.txt L.txt > output; done real 0m15.628s user 0m13.396s sys 0m2.180s real 0m16.001s user 0m13.376s sys 0m2.436s real 0m16.153s user 0m13.564s sys 0m2.304s 

Это решение perl быстрее, чем другие awk или perl-решения на 20% или около того, но явно не так быстро, как решение в C.

 perl -e ' open L, shift or die $!; open F, shift or die $!; exit if ! ($n = <L>); while (1) { $_ = <F>; next if $. != $n; print; exit if ! ($n = <L>); } ' -- LF 
 cat <<! >L.txt 1 3 ! cat <<! >F.txt Hello World Hallo Welt Hola mundo ! cmd(){ L=$1 F=$2 cat -n $F | join $L - | sed 's/[^ ]* //' } cmd L.txt F.txt Hello World Hola mundo 

Поскольку L.txt отсортирован, вы можете использовать join. Просто запишите каждую строку в файле F.txt, присоедините два файла, затем удалите номер строки. Больших промежуточных файлов не требуется.

Фактически, вышесказанное будет искажать ваши строки данных, заменив все пробелы на одно пространство. Чтобы сохранить целостность строки, вам нужно выбрать в качестве разделителя какой-либо символ, который не отображается в ваших данных, например «|». Затем cmd

 cmd(){ L=$1 F=$2 cat -n $F | sed 's/^ *//;s/\t/|/' | join -t'|' $L - | sed 's/[^|]*|//' } 

Первый sed удаляет ведущие пробелы из вывода cat -n и заменяет вкладку. Второй sed удаляет номер строки и «|».

Для полноты, еще одна попытка решения join :

 sed -r 's/^/00000000000000/;s/[0-9]*([0-9]{15})/\1/' /tmp/L | join <( nl -w15 -nrz /tmp/F ) - | cut -d' ' -f2- 

Это работает путем форматирования столбца номера строки, в котором соединение работает как фиксированная длина с ведущими нулями, так что цифры всегда равны 15 цифрам. Это обходит проблему присоединения, не улавливая нормальный порядковый порядок сортировки, так как столбец теперь фактически был вынужден сортировать слова. nl используется для добавления номеров строк в этом формате в файл F.txt. К сожалению, sed необходимо использовать для переформатирования нумерации в L.txt.

Этот подход, похоже, работает нормально в тестовых данных, полученных с использованием метода @ mikeserv. Но он все еще очень медленный – решение c на 60 раз быстрее на моей машине. около 2/3 времени проводится в sed и 1/3 в join . Возможно, есть лучшее выражение sed …

Поскольку принятый ответ на C, я решил, что это нормально, чтобы бросить решение python здесь:

 # Read mask with open('L.txt', 'r') as f: mask = [int(line_num) for line_num in f.read().splitlines()] # Filter input file filtered_lines = [] with open('F.txt', 'r') as f: for i, line in enumerate(f.read().splitlines()): if (i+1) in mask: filtered_lines.append(line) # Write newly filtered file with open('F_filtered.txt', 'w') as f: for line in filtered_lines: f.write('%s\n' % line) 

Если использовать внешнюю библиотеку, например numpy, решение будет выглядеть еще более элегантным:

 import numpy as np with open('L.txt', 'r') as f: mask = np.array([int(line_num)-1 for line_num in f.read().splitlines()]) with open('F.txt', 'r') as f: lines = np.array(f.read().splitlines()) filtered_lines = lines[mask] with open('F_filtered.txt', 'w') as f: for line in filtered_lines: f.write('%s\n' % line) 
  • Отфильтруйте файл .CSV на основе 5-го значения столбца файла и распечатайте эти записи в новый файл
  • Awk и отбрасывание несовпадающих токенов в строке?
  • Использование rsync с опцией verbose и фильтрацией отображаемой информации
  • Поиск файлов в алфавитном порядке перед заданной строкой
  • Диапазон tcpdump ip
  • find-like tool для поиска (рекурсивно) в папках MailDir по размеру, отправителю, получателю, расширению имени вложения и т. д.
  • использование регулярных выражений в exim-фильтрации
  • Почтовая фильтрация с procmail в системе postfix / dovecot с виртуальными пользователями
  • ddwrt to openwrt; блокировка имени хоста или домена на основе адреса mac
  • Как отфильтровать строки вывода команды, которые происходят в текстовом файле?
  • Домены DNS в белом списке
  • Interesting Posts

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

    cron script: dovecot: непризнанная услуга

    Использование wget, Какая правильная команда для получения gzip-версии вместо фактического HTML

    Как разбить несколько столбцов на два столбца на основе первого столбца

    Как сделать и применить (патч) одну сторону diff?

    Выполняет ли cron выполнение асинхронно?

    На какой частоте обновляется / var / log / wtmp?

    Почему я не могу делать визуальный режим при использовании visudo?

    df сильно колеблется

    WebDAV + davfs – копирование больших файлов

    Установите Arch Linux на внешний жесткий диск с помощью виртуальной машины?

    IFS Kernel Panic при первой загрузке

    Umount сетевые диски с системойd перед выключением

    Порт 80 отказался от Linux (Ubunt 12.04)

    Присоедините два текстовых файла к порядку ведения 1-го столбца и неустранимые строки из 1-го файла

    Linux и Unix - лучшая ОС в мире.