巨大なテキストファイルの処理

StackOverflow https://stackoverflow.com/questions/1625299

  •  06-07-2019
  •  | 
  •  

質問

問題： 巨大な生のテキストファイル（3gigを想定）があるので、ファイル内の各単語を調べる必要があります ファイル内に単語が何回出現するかを調べます。

提案されたソリューション： 巨大なファイルを複数のファイルに分割すると、分割された各ファイルにはソートされた単語が含まれます。例えば、 <！> quot; a <！> quotで始まるすべての単語。 <！> quot; _a.dic <！> quot;に保存されます。ファイル。したがって、いつでも26を超えるファイルを実行することはありません。

このアプローチの問題は、

ストリームを使用してファイルを読み取ることができますが、スレッドを使用してファイルの特定の部分を読み取りたいと考えました。たとえば、別のスレッドで0〜1024バイトを読み取ります（少なくとも、ボックスに存在するプロセッサの数に基づいて4〜8のスレッドがあります）。これは可能ですか、それとも夢を見ていますか？

より良いアプローチはありますか

注：純粋なc ++またはcベースのソリューションである必要があります。データベースなどは許可されません。

役に立ちましたか？

解決

Kernighanの「プログラミングの実践」をご覧ください。およびPike、特に第3章。

C ++では、文字列とカウント（std::map<string,size_t>、IIRC）に基づいたマップを使用します。ファイルを読み取り（一度-大きすぎて複数回読み取ることはできません）、移動しながらそれを単語に分割し（「単語」の定義のために）、見つかった単語ごとにマップエントリのカウントをインクリメントします。

Cでは、自分でマップを作成する必要があります。 （またはDavid Hansonの<！> quot; Cインターフェースと実装 <！> quot ;。）

または、Perl、Python、またはAwk（これらはすべて、マップに相当する連想配列を持っています）を使用できます。

他のヒント

ファイルの一部を並行して読み取る複数のスレッドを使用することは、あまり役に立たないと思います。このアプリケーションは、実際の単語カウントではなく、ハードディスクの帯域幅と遅延にバインドされると予想されます。このようなマルチスレッドバージョンは、<！> quot; quasi-random <！> quot;通常、ファイルアクセスは<！> quot; linear file <！> quotよりも低速です。アクセス。

シングルスレッドバージョンでCPUが本当にビジーな場合、潜在的な速度が向上する可能性があります。 1つのスレッドがデータを大きなチャンクで読み取り、それらを限られた容量のキューに入れることができます。他の多くのワーカースレッドは、それぞれ独自のチャンクで動作し、単語をカウントできます。ワーカースレッドのカウントが終了したら、ワードカウンターをマージする必要があります。

最初-単語を保存するためのデータ構造を決定します。

当然の選択はマップです。しかし、おそらく Trie の方が役立つでしょう。各ノードで、単語のカウントを保存します。 0は、単語の一部にすぎないことを意味します。 ストリームを使用してトライに挿入し、文字ベースでファイルを読み取ることができます。

2番目-マルチスレッディングyesまたはno？ これは簡単に答えられません。データ構造が大きくなるサイズと、答えを並列化する方法によって異なります。

  1. シングルスレッド-簡単で実装が簡単。
  2. 複数のリーダースレッドと1つのデータ構造を持つマルチスレッド。次に、データ構造へのアクセスを同期する必要があります。トライでは、実際にいるノードをロックするだけでよいので、複数のリーダーが大きな干渉なしにデータ構造にアクセスできます。自己バランスツリーは、特にリバランスの場合は異なる場合があります。
  3. それぞれが独自のデータ構造を持つ複数のリーダースレッドを使用したマルチスレッド。各スレッドは、ファイルの一部を読み取りながら、独自のデータ構造を構築します。それぞれが終了したら、結果を結合する必要があります（簡単なはずです）。

考えなければならないことの1つは、開始する各スレッドの単語境界を見つける必要がありますが、それは大きな問題にはなりません（たとえば、各スレッドは、最初の単語境界まで開始し、そこから開始します）各スレッドが終了し、作業中の単語が終了します）。

2番目のスレッドを使用してデータを読み取った後、データを分析することはできますが、そうすることで多額の利益を得ることはないでしょう。複数のスレッドを使用してデータを読み取ろうとすると、データを改善するのではなく、ほぼ確実に速度が低下します。複数のスレッドを使用してデータを処理することは無意味です-処理は読み取りよりも何倍も高速になるので、追加のスレッドが1つだけであっても、制限はディスク速度になります。

かなりの速度を得るための1つの（可能性のある）方法は、通常のiostreamをバイパスすることです-一部はC FILE *を使用するのとほぼ同じくらい高速ですが、本当に高速なものは知りませんし、かなり遅いものもあります。 Cとは明らかに異なるI / Oモデルを持つシステム（Windowsなど）でこれを実行している場合は、少し注意してかなり多くを得ることができます。

問題は非常に単純です：読み込んでいるファイルは利用可能なキャッシュスペースよりも（潜在的に）大きいですが、キャッシュからは何も得られません。再度ファイルします（少なくとも賢明なことをすれば）。したがって、システムにキャッシングをバイパスし、データをできるだけ直接ディスクドライブから処理可能なメモリに転送するように指示する必要があります。 Unixライクなシステムでは、おそらくopen()とread()になります（そして、あまり多くは得られません）。 Windowsでは、これはCreateFileおよびReadFileであり、FILE_FLAG_NO_BUFFERINGフラグを<=>に渡します。正しく実行すると、おそらく速度が約2倍になります。

また、さまざまな並列構造を使用して処理を行うことを提唱するいくつかの回答を得ました。これらは根本的に間違っていると思います。恐ろしく愚かなことをしない限り、ファイル内の単語を数える時間は、単にファイルを読むのにかかるよりも数ミリ秒長くなります。

使用する構造は、たとえば1メガバイトのバッファを2つ持つことです。データを1つのバッファーに読み取ります。そのバッファをカウントスレッドに渡して、そのバッファ内の単語をカウントします。それが起こっている間に、データを2番目のバッファに読み込みます。それらが完了したら、基本的にバッファを交換して続行します。バッファ間で境界を越える可能性のある単語を処理するためにバッファをスワップする際に行う必要がある余分な処理が少しありますが、それはかなり簡単です（基本的に、バッファが白で終わらない場合）次のデータバッファで操作を開始するとき、あなたはまだ一言です。）

マルチプロセッサ（マルチコア）マシンでのみ使用されることが確実である限り、実際のスレッドを使用しても問題ありません。これがシングルコアマシンで実行される可能性がある場合は、代わりに、I / Oがオーバーラップした単一のスレッドを使用した方が良いでしょう。

他の人が示したように、ボトルネックはディスクI / Oになります。したがって、オーバーラップI / Oを使用することをお勧めします。これは基本的にプログラムのロジックを逆にします。 I / Oを実行するタイミングを決定するためにコードを調整する代わりに、オペレーティングシステムに、I / Oが少し終了したときにコードを呼び出すように指示するだけです。 I / O完了ポートを使用すると、 OSは、ファイルチャンクの処理に複数のスレッドを使用します。

cベースのソリューション？

perlはまさにこの目的のために生まれたと思います。

streamにはカーソルが1つしかありません。一度に複数のスレッドでストリームにアクセスする場合、どこで読みたいかわからないでしょう。読み取りはカーソル位置から行われます。

私がすることは、ストリームを読み取り、読み取りバイトを他のスレッドにディスパッチするスレッド（メインスレッドかもしれません）を1つだけ持つことです。

例：

  • スレッド#iは準備ができており、メインスレッドに次の部分を提供するように依頼します
  • メインスレッドは次の1Mbを読み取り、スレッド1に提供します
  • スレッド#iは1Mbを読み取り、必要に応じて単語をカウントします
  • スレッド#iは作業を終了し、次の1Mbを再度要求します。

この方法により、ストリーム読み取りとストリーム分析を分離できます。

探しているのはRegExです。 c ++正規表現エンジンのこのStackoverflowスレッドは以下を支援するはずです。

C ++：どの正規表現ライブラリを使用すればよいですか

まず、C / C ++がこれを処理する最善の方法ではないことを確信しています。理想的には、並列処理のためにmap / reduceを使用することもあります。

しかし、あなたの制約を仮定して、ここで私がやることがあります。

1）テキストファイルを小さなチャンクに分割します。単語の最初の文字でこれを行う必要はありません。たとえば、5000ワードのチャンクに分割します。擬似コードでは、次のようにします：

index = 0

numwords = 0

mysplitfile = openfile（index-split.txt）

while（bigfile <！> gt; <！> gt; word）

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2）共有マップデータ構造とpthreadを使用して新しいスレッドを作成し、各サブファイルを読み取ります。繰り返しますが、擬似コード：

maplock = create_pthread_lock（）

sharedmap = std :: map（）

すべてのindex-split.txtファイル：

spawn-new-thread(myfunction, filename, sharedmap, lock)

dump_map（sharedmap）

void myfunction（filename、sharedmap）{

localmap = std::map<string, size_t>();

file = openfile(filename)

while (file >> word)

    if !localmap.contains(word)
         localmap[word] = 0

    localmap[word]++

acquire(lock)
for key,value in localmap
    if !sharedmap.contains(key)
         sharedmap[key] = 0

    sharedmap[key] += value
release(lock)

}

構文は申し訳ありません。私は最近たくさんのpythonを書いています。

Cではなく、少しいですが、バングアウトするのにたった2分しかかかりませんでした：

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

-n
で各行をループします @F
で各行を-a単語に分割します 各$_単語はハッシュをインクリメントします%h
ENDのfileに到達すると、
sort頻度によるハッシュ$h{$b}<=>$h{$a}
2つの周波数が同一の場合、アルファベット順にソート$a cmp $b
頻度$h{$w}および単語$w
を印刷します 結果を「freq」ファイルにリダイレクトします

このコードは、580,000,000ワードの3.3GBテキストファイルで実行しました。
Perl 5.22は173秒で完了しました。

入力ファイルでは、すでに次のコードを使用して、句読点が取り除かれ、大文字が小文字に変換されています：
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
（144秒の実行時間）

単語カウントスクリプトは、awk：
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top