1GBなどの大容量ファイルの場合、wc -l
非常に遅くなります。特定のファイルの改行数を数えるより速い方法はありますか?
答え1
あなたは試すことができますCで書く:
#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
char buf[BUFSIZ];
int nread;
size_t nfound=0;
while((nread=read(0, buf, BUFSIZ))>0){
char const* p;
for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
}
if(nread<0) { perror("Error"); return 1; }
printf("%lu\n", nfound);
return 0;
}
たとえば、wcl.c
コンパイル、たとえば、gcc wcl.c -O2 -o wcl
実行して保存します。
<yourFile ./wcl
これは私のシステムで改行文字でいっぱいの1GBファイルを見つけました。370ミリ秒(実行を繰り返す)。 (バッファサイズを増やすと時間が少し増えますが、これは予想通りです。BUFSIZは最適値に近いはずです)。380ミリ秒私はから来ましたwc -l
。
Mmapingでより良い時間を過ごしました。280ミリ秒しかし、もちろん、実際のファイルに制限される制限があります(FIFOなし、端末入力なしなど)。
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main(){
struct stat sbuf;
if(fstat(0, &sbuf)<0){ perror("Can't stat stdin"); return 1; }
char* buf = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, 0/*stdin*/, 0/*offset*/);
if(buf == MAP_FAILED){ perror("Mmap error"); return 1; }
size_t nread = sbuf.st_size, nfound=0;
char const* p;
for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
printf("%lu\n", nfound);
return 0;
}
次のコマンドを使用してテストファイルを作成しました。
$ dd if=/dev/zero of=file bs=1M count=1042
いくつかのテスト改行を追加しました。
$ echo >> 1GB
そして16進エディタ。
答え2
への呼び出し数を減らすことで、@pskocikが提案した解決策を改善できますread
。一つあるたくさんBUFSIZ
1Gbファイルからブロックを読み取るための呼び出しの数。一般的なアプローチは、バッファサイズを増やすことです。
- 楽しんで、バッファサイズを10倍または100倍増やしてみてください。私のDebian 7では
BUFSIZ
8192です。元のプログラムでは、これは120,000の読み取り操作です。おそらく1Mbの入力バッファを100倍に減らす余裕があるでしょう。 - より最適化されたアプローチのために、アプリケーションは単一の読み取り操作を必要とするファイルほど大きなバッファを割り当てることができます。これは「小さい」ファイルには十分です(一部のリーダーのコンピュータには1 GB以上があります)。
- 最後に、割り当て自体を処理するメモリマップされたI / Oを試すことができます。
さまざまな方法をベンチマークするとき、Linuxなどの一部のシステムでは、コンピュータの未使用メモリの大部分をディスクキャッシュとして使用することを覚えています。しばらく前(約20年前、卑劣なFAQ)、私はテキストエディタでメモリ不足の状況を処理するために開発した(あまり良くない)ページングアルゴリズムの予期しない良い結果に混乱しました。私はプログラムがファイルを読み取るために使用されるメモリバッファで動作するので、非常に速く実行され、ファイルを読み書きするときに速度の違いしかないと説明しました。
同じことが当てはまりますmmap
(他の場合はFAQに含めるためにまだ私のやり方のリストにあり、開発者はディスクキャッシュが改善の実際の理由である非常に良い結果を報告しました)。ベンチマークを開発するには、パフォーマンスが良い(または悪い)理由を分析するのに時間と労力が必要です。
追加資料: