☰

行番号によるファイルのフィルタリング

tag-icon • tag-icon text-processing filter high-performance
行番号によるファイルのフィルタリング

行ごとに負以外の整数を持つファイルLとテキストファイルFが与えられた場合、行番号がファイルLに現れるFの行だけを維持する簡単な方法はありますか？

例:

$ 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

5億以上のアイテムを持つファイルLを処理できるコマンドを探しています。ファイルLは数値でソートされます。

注：私は半分を実装していますが、command-in-questionここでもいくつかのUnixツールを使用できるかどうか疑問に思います。

更新：すべての答えに感謝します。今日はたくさん学びました！複数の回答を受け入れたいが不可能です。

現在の回答から最速のソリューションを選択してスタンドアロンツールに入れました。フィルタライン。

答え1

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
    • 次の作業の目的は、linenoを./F使用して./Lファイル全体をインラインでスタックすることです。[0-9]:
    • したがって、UTF-8に関連する場合よりも、128個の可能なセットの中からこれらの11個の文字を見つける方が簡単です。
  • grep -n ''
    • これで文字列が挿入されます。LINENO:stdinで - または<./F。
  • sort -t: -nmk1,1 ./L -
    • sort入力ファイルのソートをまったく無視し、代わりに(正しい)事前ソートされていると仮定し、ソートされた順序で-mソートします。デフォルトでは、可能なコロン文字以外のすべての項目は-numerically無視されます-k1,1。-t:
    • 完了するには一時スペースが必要な場合がありますが、（一部のシーケンスがどのくらい離れて発生する可能性があるかによって異なります）、適切な位置合わせに比べて多くの必要はなく、逆追跡がまったく発生しないため、非常に高速です。
    • sort./Lの対応する行がlinenoの直前にあるストリームを出力します./F。./Lの行は短いため、常に最初にリストされます。
  • sed /:/d\;n
    • 現在の行がコロンと一致すると、出力から削除され/:/ます。dそれ以外の場合は、現在の行とn次の行が自動的に印刷されます。
    • したがって、出力をsed次にトリミングします。sortただコロンと次の行と一致しない、または./L次の行にのみ一致する連続行のペア。
  • cut -sd: -f2-
    • cut -s-d:区切り文字列の1つ以上を含まない入力行を出力から抑制することで、./L行が完全に切り捨てられます。
    • これを行う行の場合、:コロンで区切られた最初のフィールドが消え、-f挿入されたすべての linenocutも同様です。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

...その中に500万個の行を入れ/tmp/F、その中にランダムに選択された150万個の行を/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

（そこにバックスラッシュを追加しました）

これは現在提供されているすべてのソリューションの中で最も高速ですが、上記で作成されたデータセットと比較して最も高速ではありません。他の人のうちの1人だけが2位の競争に近く、それはMeuhのものでした。perl ここ。

これは決してもともと提供された解決策ではありませんでした。他の人が提供したアドバイス/インスピレーションのおかげで、実行時間は3分の1に短縮されました。遅い解決策については、投稿履歴をご覧ください。（ところでなぜ？）。

また、私のシステムのマルチCPUアーキテクチャと、このパイプラインで各プロセスの同時実行でなかった場合は、他の答えのいくつかがより良いかもしれないことに注意する価値があります。これらのすべては、それぞれ独自のプロセッサコアで同時に動作し、データを渡し、全体の小さな部分を完成させます。本当に素敵です。

しかし、最速の解決策は...

しかし、これが最速の解決策ではありません。間違いなくここで提供される最も速い解決策は次のとおりです。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

答え2

私は使用しますが、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"

答え3

私は以下を使用しますawk：

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

アップデート：パフォーマンス測定を行いました。比較は非常に高速で、ハッシュテーブルを構築するために必要な作業を過度に補償するため、このバージョンは非常に大きなデータセットに対してよりよく拡張されるようです（指定された要件の場合）。 。

答え4

完全性のために、Stéphane Chazelasの答えにある素晴らしいawkスクリプトとkosの答えにあるPerlスクリプトを組み合わせることができますが、リスト全体をメモリに保持せずに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;
        }
    }
}

関連情報