これは、ファイル(または必要に応じてファイルのサブセット)で実行できるbashスクリプトです。キーファイルをますます大きなブロックに分割し、ブロックごとにgrep操作を試行します。操作のタイミングは調整されています。現在、各grep操作のタイミングと、すべてのサブ式を処理する合計時間です。出力は数秒です-多少の努力でmsを取得できますが、問題が発生しているため、その粒度が必要になる可能性はほとんどありません。次の形式のコマンドを使用して、ターミナルウィンドウでスクリプトを実行します
./timeScript keyFile textFile 100 > outputFile
これにより、検索キーが保存されるファイルとしてkeyFile、キーを検索するファイルとしてtextFile、初期ブロックサイズとして100を使用して、スクリプトが実行されます。各ループで、ブロックサイズは2倍になります。
2番目の端末で、コマンドを実行します
tail -f outputFile
これにより、他のプロセスの出力がファイルに記録されます。outputFile
3番目のターミナルウィンドウを開き、そのウィンドウで実行することをお勧めしtop
ます。プロセスが使用しているメモリとCPUの量を確認できます。繰り返しになりますが、大量のメモリが消費されている場合は、状況がうまくいかないというヒントが得られます。
これにより、物事がいつ減速し始めるかを知ることができるはずです-これがあなたの質問への答えです。「マジックナンバー」はないと思います。おそらくマシン、特にファイルサイズとメモリの量によって異なります。
スクリプトの出力を取得して、grepに通すことができます。
grep entire outputFile
最終的には要約だけになります-ブロックサイズと所要時間、例:
Time for processing entire file with blocksize 800: 4 seconds
これらの数値を相互にプロットする(または単に数値を調べる)と、アルゴリズムが最適な場合と速度が低下する場合がわかります。
コードは次のとおりです。大規模なエラーチェックは行いませんでしたが、うまくいったようです。明らかに、最終的なソリューションでは、grepの出力を使用して何かを行う必要があります(wc -l
一致する行の数を確認するために行ったパイプの代わりに)...
#!/bin/bash
# script to look at difference in timing
# when grepping a file with a large number of expressions
# assume first argument = name of file with list of expressions
# second argument = name of file to check
# optional third argument = initial block size (default 100)
#
# split f1 into chunks of 1, 2, 4, 8... expressions at a time
# and print out how long it took to process all the lines in f2
if (($# < 2 )); then
echo Warning: need at leasttwo parameters.
echo Usage: timeScript keyFile searchFile [initial blocksize]
exit 0
fi
f1_linecount=`cat $1 | wc -l`
echo linecount of file1 is $f1_linecount
f2_linecount=`cat $2 | wc -l`
echo linecount of file2 is $f2_linecount
echo
if (($# < 3 )); then
blockLength=100
else
blockLength=$3
fi
while (($blockLength < f1_linecount))
do
echo Using blocks of $blockLength
#split is a built in command that splits the file
# -l tells it to break after $blockLength lines
# and the block$blockLength parameter is a prefix for the file
split -l $blockLength $1 block$blockLength
Tstart="$(date +%s)"
Tbefore=$Tstart
for fn in block*
do
echo "grep -f $fn $2 | wc -l"
echo number of lines matched: `grep -f $fn $2 | wc -l`
Tnow="$(($(date +%s)))"
echo Time taken: $(($Tnow - $Tbefore)) s
Tbefore=$Tnow
done
echo Time for processing entire file with blocksize $blockLength: $(($Tnow - $Tstart)) seconds
blockLength=$((2*$blockLength))
# remove the split files - no longer needed
rm block*
echo block length is now $blockLength and f1 linecount is $f1_linecount
done
exit 0