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

17

Учитывая файл 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.


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

Мик
источник
Сколько строк в файле F?
Peter.O
1
В F как минимум столько же строк, сколько в L.
miku

Ответы:

8

С 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;
    }
}
FloHimself
источник
2
Это самый эффективный ответ здесь. По крайней мере, так по моим тестам. В случае , если кому - то интересно, я собирал его , как: xsel -bo | cc -xc - -o cselect. И это просто сработало - ему нужны только две библиотеки.
mikeserv
1
Спасибо, это здорово! Надеюсь, вы не возражаете, но я завернул ваш код в небольшой инструмент .
мику
1
@miku Давай, я рад, что смог помочь. Я заметил, что вы увеличили LINE_MAXсвою версию, поэтому вы, вероятно, работаете с очень большими строками в ваших файлах. Я обновил А с помощью версии, getline()чтобы убрать ограничение размера строки.
FloHimself
@FloHimself, хорошо, еще раз спасибо :) Действительно, некоторые строки ввода могут превышать LINE_MAX, так что, getlineкажется, это правильно.
мику
10

Я хотел бы использовать 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"
Стефан Шазелас
источник
Точно, я попробовал хэш-карты, и они превысили бы память; битовые наборы купят вам больше запаса; но, используя тот факт, что входные данные отсортированы, вы можете полностью избавиться от этой проблемы.
мику
1
@Janis; это не просто случай хорошей практики кодирования: не используйте жесткие литералы кода - используйте вместо них переменные ... (более гибкие и менее подверженные ошибкам и более
легкие
1
@ StéphaneChazelas: Необходимо предварительно рамочную инициализацию n, в противном случае (как есть) он пропускает 1вL.txt
Peter.O
1
@ Peter.O, к сожалению, это то, к чему я пытался обратиться с помощью NR> = n, но это было неправильно. Должно быть лучше сейчас.
Стефан Шазелас
1
@Janis, идея заключалась в том, что если этот код должен быть встроен в command-in-questionсценарий, то вы не сможете вставить имя файла в код. -v list="$opt_x"также не работает из-за обработки обратной косой черты, выполняемой с помощью awk. Вот почему я использую ENVIRON вместо этого здесь.
Стефан Шазелас
10

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

небольшой входной тест

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 здесь .

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

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

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

Но это не самое быстрое решение. Самое быстрое решение, предлагаемое здесь, это программа на Си . Я назвал это 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
mikeserv
источник
1
Вы можете сделать это значительно быстрее (почти так же быстро , как у меня на многоядерных системах) с sed -ne'/:/!{n;p;}' | cut -d: -f2-вместоsed -ne'/:/!N;/\n/s/[^:]*://p'
Stéphane Chazelas
@ StéphaneChazelas - вы можете получить лучшие результаты, если вы переключите seds - sedя использую семейную реликвию sed- вы можете увидеть aliasзначение в timeрезультатах. Кстати, мой семейный пакет статически скомпилирован с библиотекой musl - реализация regex, для которой основан TRE . Когда я переключаю его на GNU sed- и запускаю его без cut- он добавляет целую секунду ко времени завершения (2,8 секунды) - составляет более трети. И это всего на 0,3 секунды быстрее, чем у вас в моей системе.
mikeserv
1
sort -mnв отличие от sort -nmk1,1может быть лучше, поскольку вам не нужно делать расщепление здесь (не проверено)
Стефан Шазелас
@ StéphaneChazelas - да, я думал то же самое, и я пробовал это во всех отношениях. -nis spec'd просто сделать первую числовую строку в строке, поэтому я решил, хорошо -mnили -nmи, по какой-то причине, единственный раз, когда она опускалась ниже 2 секунд во время завершения, это когда я добавлял все параметры как есть. Это странно - и это причина, по которой я вчера не взялся за -mдело - я знал, о чем я, но казалось, что это просто что-то вроде автооптимизации. Интересно, что у семейной реликвии sortесть -zопция длины строки, которая применяется только к -[cm]....
mikeserv
-nне первая числовая строка в строке . Она просто рассматривает строку как число, поэтому она abc 123будет равна 0. Поэтому она не может быть менее эффективной, чем с-t: -k1,1
Стефан Шазелас
9

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

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

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

Janis
источник
1
@miku; Да, это хорошее компактное решение. Но предостережение; не все awkмогут справиться с такими огромными наборами данных. - Я использую GNU awkи проблем нет; тест с 500 миллионами строк данных занял 7 минут.
Янис
1
Это довольно медленно (для сравнения) real 16m3.468s- user 15m48.447s- sys 0m10.725s. Он использовал 3,3 ГБ ОЗУ для тестирования 1/10 размера Lс 50 000 000 строк; и Fс 500 000 000 строк - по сравнению с временем для awk anser Стефана Шазеласа: real 2m11.637s- user 2m2.748s- sys 0m6.424s- Я не использую быстрый ящик, но сравнение интересно.
Peter.O
@ Peter.O; Спасибо за данные! Ожидается более медленная скорость, учитывая, что (в моем собственном тестовом примере) полмиллиарда строк хранятся в ассоциативном массиве. (Вот почему я прокомментировал «(+1)» выше для предложения Стефана.) - Хотя я был удивлен, что это сжатое решение все еще обрабатывает 1 миллион строк в секунду! Я думаю, что это делает этот шаблон кода (из-за его простоты!) Жизнеспособным вариантом, особенно в случаях с менее экстремальными размерами данных.
Янис
Это определенно жизнеспособное решение. На тестовых данных, которые я использовал (5 мил. Линий / 1,5 мил. Л), ваши были выполнены чуть более чем за 4 секунды - всего за секунду до ответа Стефана. Код , используемый для поколения тестового набора в моем ответе, но это в основном просто seqвыход , а затем меньше, случайным образом выбирается подмножество же в L .
mikeserv
1
Я только что сделал еще несколько измерений производительности с размером файла данных 500 миллионов строк и размером файла ключа 50 миллионов и соответственно. 500 миллионов строк, с примечательным наблюдением. При использовании меньшего ключевого файла время составляет 4 минуты (Стефан) против 8 минут (Янис), в то время как при увеличении ключевого файла это 19 минут (Стефан) против 12 минут (Янис).
Янис
3

Просто для полноты: мы можем объединить отличный сценарий 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;
        }
    }
}
meuh
источник
Это намного быстрее, чем awk. Это примерно так же быстро, как у меня - я тестировал оба три раза прямо сейчас, и каждый раз мой обрабатывал мой 5-миллионный тестовый набор линии за 1,8 ... секунды, а ваши 1,9 ... секунды каждый раз. Код testset gen находится в моем ответе, если вам интересно, но дело в том, что он очень хорош. Более того, результат правильный - я все еще не могу сделать awkработу ... Тем не менее, оба наших ответа опозорены FloHimself .
mikeserv
@mikeserv, у нас должны быть разные awks. В вашем примере я получаю 1,4 с gawk (4 с для Janis '), 0,9 с mawk, 1,7 с с помощью этого Perl-решения, 2,3 с с KOS', 4,5 с с вашим (GNU sed) и 1,4 с с вашим ( GNU sed) и мое предложенное улучшение (и 0,5 с для решения C).
Стефан Шазелас
@mikeserv, ах! конечно, с вашим подходом, язык имеет значение. При переходе с UFT-8 на C. с 4,5 с до 2,3 с
Стефан Шазелас
3

Я написал простой 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текущий номер строки соответствует содержимому массива по текущему индексу массива, он печатает текущую строку и увеличивает индекс

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

Учитывая стоимость выполнения назначений, стоимость сравнений и стоимость печати строк, учитывая 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 миллионов строк, содержащий случайные строки длиной 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
кос
источник
2

Это решение на 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
jrw32982 поддерживает Монику
источник
0
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 удаляет номер строки и «|».

meuh
источник
Боюсь, это не сработает на больших файлах. Требуется <10 строк. У меня была та же идея, и я попробовал, join L.txt <(nl F.txt )но она не будет работать с большими файлами. Добро пожаловать на сайт, кстати, не часто мы получаем такие четкие и хорошо отформатированные ответы от новых пользователей!
Тердон
@terdon, Да, позор, который join/ commне может работать с численно отсортированным вводом.
Стефан Шазелас
@terdon: Я проследил за вашим лидерством (теперь удалено) и попытался join -t' ' <(<L.txt awk '{printf("%010s\n",$0)}') <(<F.txt awk '{printf("%010s %s\n",NR,$0)}') | cut -d' ' -f2-- это было медленно! - и даже когда я подавал подготовленные файлы с подходящими 0-клавишными клавишами join -t' ' L.txt F.txt | cut -d' ' -f2- , он все еще был медленным (не считая времени на подготовку) - медленнее, чем awkответ @Janis (где я разместил комментарий относительно фактического времени, взятого для обоих его и @ StéphaneChazelas 'ответ
Peter.O
@ Peter.O да. Я попробовал подобный подход, который избегает одного из действий, но я не мог найти способ заставить это и работать и стоить это.
Тердон
@terdon и другие: Фактическое время замены процессаjoin + было против Стефана Шазеласа с использованием 50 миллионов строк, 500 миллионов строк. awk printf real 20m11.663s user 19m35.093s sys 0m10.513sreal 2m11.637s user 2m2.748s sys 0m6.424sLF
Peter.O
0

Для полноты еще одна попытка 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 ...

Цифровая травма
источник
Хорошо, но почему мы добавляем все нули? Я пытаюсь почувствовать это. Кроме того, nlэто очень круто, но вы не можете надежно использовать его на непроверенных данных. Одна из вещей, которая делает его таким крутым, это его логический -d разделитель страниц . По умолчанию, если на входе есть какая-либо строка, состоящая только из строк :\` (но без завершающей могилы) 1, 2, 3 или три раза подряд, ваш счет будет немного сумасшедшим. Эксперимент с этим - это довольно опрятно. Особенно взгляните на то, что происходит, когда nl` читает строку с 1 строкой-разделителем, а затем еще раз с w / 3 или 2
mikeserv
0

Так как принятый ответ находится на 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)
AlexG
источник