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

$ cat /var/log/file | sort | uniq

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 отсортирован, можно использовать соединение. Просто нумеруйте каждую строку в 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. К сожалению, для переформатирования нумерации в L.txt необходимо использовать sed.

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

Это решение 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>);
  }
' -- L F

grep -n | сортировать | 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 , единственные символы, о которых нам действительно нужно беспокоиться, - это цифры ASCII [0-9] и двоеточие : .
  • По этой причине легче беспокоиться о поиске этих 11 символов в наборе из 128 возможных, чем если бы UTF-8 использовался иначе.
• grep -n ''
  • Это вставляет строку LINENO: в заголовок каждой строки в stdin - или <./ F .
• sort -t: -nmk1,1 ./L -
  • sort вообще игнорирует сортировку своих входных файлов, и вместо этого (правильно) предполагает, что они предварительно отсортированы и -m выдвигает их в -числовом порядке сортировки, игнорируя практически все, кроме возможной -k1,1 st, встречающейся -t: символ двоеточия.
  • Хотя для этого может потребоваться некоторое временное пространство (в зависимости от того, насколько далеко друг от друга могут располагаться некоторые последовательности) , это не потребует многого по сравнению с правильной сортировкой, и будет очень быстро, потому что включает нулевой возврат.
  • sort выведет один поток, в котором любые строки в ./ L будут непосредственно предшествовать соответствующим строкам в ./ F . Строки ./ L всегда идут первыми, потому что они короче.
• sed /: / d \; n
  • Если текущая строка соответствует /: / двоеточию d , удалите ее из вывода. В противном случае автоматически распечатайте текущую и n внешнюю строку.
  • Итак, sed сокращает вывод sort до только пар последовательных строк, которые не соответствуют двоеточию и следующей строке - или только до строка из ./ L , а затем следующая.
• cut -sd: -f2-
  • cut -s подавляет из вывода те из его входных строк, которые не содержат хотя бы одной из его -d: строк исключения - и так ./ L строки полностью обрезаются.
  • Для тех строк, которые это делают, их первая : разделенная двоеточием -f ield вырезана - и так же все grep вставлены льняные диски.

small input test

seq 5 | sed -ne'2,3!w /tmp/L
        s/.*/a-z &\& 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 <==
a-z 1& 0-9
a-z 4& 0-9
a-z 5& 0-9

==> /tmp/F <==
a-z 1& 0-9
a-z 2& 0-9
a-z 3& 0-9
a-z 4& 0-9
a-z 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,5 мил случайно выбранных строк из этого в / 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

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

Среди решений, предлагаемых в настоящее время здесь, это самое быстрое из всех, кроме одного, если сравнивать его с набором данных, созданным выше на моей машине . Из остальных только один был близок к тому, чтобы претендовать на второе место, и это perl здесь 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 l f\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-скрипт:

Использование: 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 ++;
    }
}

• Loads F.txt
• Loads L.txt
• Сохраняет каждую строку L.txt в массив
• Считывает F.txt построчно, отслеживая его текущий номер строки и текущий индекс массива; увеличивает номер текущей строки F.txt ; если номер текущей строки F.txt совпадает с содержимым массива в текущем индексе массива, он печатает текущую строку и увеличивает индекс

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

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

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

Использование файла с 10 миллионами строк F.txt , содержащего случайные строки длиной 50 символов и 10 миллионов строк. -линии L.txt файл, содержащий числа от 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

Я бы использовал awk , но не сохранял бы все содержимое 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

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

Поскольку принятый ответ написан на языке 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)