4

与えられた：

  • 数百万行を含むファイルa.txt（たとえば、1行に1文）（2.6 GB！
  • b.txtペアの830k行を含むファイル[word1] [word2]

質問：

巨大なテキストファイル内の830kタプル（w1、w2）ごとに、各word1をword2に最も効率的に置き換える方法は？

sed、perl、pythonなどの単純なメソッドは、そうするのに数週間かかるでしょう。その大量の置換を実行する（おそらく並列化ベースの）方法はありますか？

4

5 に答える 5

5

私はPythonでそれを行いますが、アルゴリズムが適切であれば、他の言語でも機能します。全体の秘訣は、単語のペア (ファイル b.txt) をメモリに保持し、1 回のパスで大きなファイルを処理することです。I/O は RAM からの読み取りよりもはるかに遅い操作であるため、このアプローチのパフォーマンスは O(file1) + O(file2) になります。

擬似コード:

myMap = {}
for line in fileB:
  myMap[1st word of line] = 2nd word of line

for line in fileA
  for word in line
    if myMap contains word
      replace word with myMap[word]

これが最速だと思います。

于 2009-04-15T16:22:34.317 に答える
0

ペアをメモリにロードしてからファイルをストリーミングするというidrosidの回答に同意します。本当に大量のデータ (大量の Gb) を持っていて、必要な速度でこれを実行するためのマシン リソースがない場合は、Amazon の新しい Elastic Hadoop サービスが優れたソリューションになります。小さなファイルで動作する単純な実行可能ファイルを取得したら、Hadoop の Map Reduce フレームワークを使用して、それを大量のデータにスケールアップするのは非常に簡単です。

于 2009-04-15T16:27:39.513 に答える
0

ファイルを小さなチャンクに分割します。メモリ内またはディスク上でビットをシフトするだけで、大量のメモリ空間を消費している可能性があります。

これは、単一の文字列ではなく、文字列の配列を連結/置換する方がはるかに高速であることに似ています。

唯一の秘訣は、ファイル内のブレークを配置する場所が適切に一致していないことを確認することです。これは比較的簡単です。実際、行ごとに実行できる場合は、さらに優れており、一致をチェックする必要はありません。

また、PERL に数週間かかることも奇妙に感じます。それを 1 時間以内に処理できることを示唆する事例証拠がいくつかあります。

実際、彼らは 2 番目のリンクで 2 分かかる 1GB のファイルについて話しています。

また、置換操作がファイルのコピー操作よりも大幅に時間がかかるとは思いません。結局のところ、ファイルのチャンクを取得し、それらを移動するときにビットの一部を置き換えるだけです。それらをコピーする速度に近い速度でオンザフライで置き換えることができるはずです（既にメモリにあるため）

于 2009-04-15T16:14:57.577 に答える
0

検索/置換ペアのリストを [単語 1] を検索する単語で並べ替えます

次に、ファイルを読み、各行を単語に分割し、単語のリストで置換する各単語を探します (バイナリ検索のような効率的な方法を使用します)。

それは達成可能でなければなりません。

于 2009-04-15T16:19:15.710 に答える
-1

SQLでやります。

2つの列（データライン、シーケンス）を持つテーブルを作成し、その中にa.txtを配置します（テーブル行ごとに1行）

次に、2つの列（word1とword2）を含む2番目のテーブルを作成し、b.txtをそのテーブルに読み込みます（ここでも、テーブル行ごとに1行）

table2に基づいてtable1を更新する更新ステートメントを生成します

SQLステートメントを実行します

完了したら、最初のテーブルをファイルに戻します

于 2009-04-15T16:14:24.180 に答える