☰

大規模なコードディレクトリから文字列リストを効率的に取得する方法

tag-icon • tag-icon grep performance search
大規模なコードディレクトリから文字列リストを効率的に取得する方法

文字列のリストがあり、各文字列ごとに大きなソースコードディレクトリに表示されることを確認したいと思います。

私が望むものを提供するGNU grepソリューションを見つけました。

for key in $(cat /tmp/listOfKeys.txt); do
    if [ "$(grep -rio -m 1 "$key" . | wc -l)" = "0" ]; then
        echo "$key has no occurence"; 
    fi
done

ただし、一致するものを早期に見つけても、常にディレクトリの下のすべてのファイルをgrepするため、非効率的です。検索する必要があるキーも多く、検索する必要があるファイルも多すぎるため、そのまま機能しません。

「標準」Unixツールを使用してこれを効率的に実行する方法を知っていますか？

答え1

少なくとも、次のように単純化できます。

set -f # needed if you're using the split+glob operator and don't want the
       # glob part

for key in $(cat /tmp/listOfKeys.txt); do
   grep -riFqe "$key" . ||
    printf '%s\n' "$key has no occurrence"
done

これにより、最初の発生後に検索が停止され、キーが正規表現key（または可能なオプションgrep）と見なされなくなります。

ファイルを複数回読み取ることを防ぎ、キーのリストが1行に1つのキーであると仮定するには（上記のコードのように区切られたスペース/タブ/改行の代わりに）GNUツールを使用できます。

find . -type f -size +0 -printf '%p\0' | awk '
  ARGIND == 2 {ARGV[ARGC++] = $0; next}
  ARGIND == 4 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' RS='\0' - RS='\n' /tmp/listOfKeys.txt

keyaが表示されている場合は検索を停止し、すべてのキーが見つかったら停止し、ファイルを一度だけ読むように最適化されています。

キーがにあるとしますlistOfKeys.txt。キーは小文字で出力されます。

上記のGNUismは、NULで区切られたレコードを処理する機能-printf '%p\0'と同じです。最初の2つの問題は、次のように解決できます。ARGINDawk

find . -type f -size +0 -exec printf '%s\0' {} + | awk '
  step == 1 {ARGV[ARGC++] = $0; next}
  step == 2 {a[tolower($0)]; n++; next}
  {
    l = tolower($0)
    for (i in a) if (index(l, i)) {
      delete a[i]
      if (!--n) exit
    }
  }
  END {
    for (i in a) print i, "has no occurrence"
  }' step=1 RS='\0' - step=2 RS='\n' /tmp/listOfKeys.txt step=3

3番目の問題も同様のトリックを使用して解決できます。これしかし、おそらく努力する価値はないでしょう。バラより裸足IOソリューション問題を完全に迂回する方法を探しています。

答え2

GNU grep（そして私が知っているほとんどのバリエーション）は、-f正確に必要なことをするオプションを提供します。このfgrepバリアントは、入力行を正規表現ではなく通常の文字列として扱います。

fgrep -rio -f /tmp/listOfKeys.txt .

一致するものが1つ以上あるかどうかをテストするには、-qオプションを追加してください。 Stéphaneのコメントに基づいてどの文字列が必要かを知る必要がある場合いいえ見つけたら、-hオプションを追加してから、一般的なawkイディオムを介してパイプします。

fgrep -h -rio -f /tmp/listOfKeys.txt . |
awk '{$0=tolower($0)}; !seen[$0]++' |
fgrep -v -i -x -f - /tmp/listOfKeys.txt

2番目は、fgrep最初の出力（大文字と小文字を区別しない一意の出力）を取得し、fgrep意味を変更し、キーファイルに一致しない文字列を表示します。

答え3

Stéphane Chazelasのgawkメソッドの移植可能なPOSIX互換翻訳：

find . -type f -exec cat {} + |
awk '
    FNR==NR {keys[tolower($0)]; n++; next}
    {
        s = tolower($0)
        for (k in keys) 
            if (index(s, k)) {
                delete keys[k]
                if (!--n)
                    exit
            }
    }
    END {
        for (k in keys) print k, "has no occurrence"
    }
' /tmp/listOfKeys.txt -

名前が常に内容より長いという点でソースファイルが異常でない限り、パイプを介して転送されるデータが少ないため、Stéphaneのソリューションはより効率的です（ここではカーネルを介した2つのプロセスのバッファ間コピーが含まれます）。

関連情報