c++ - 非常に大きなテキスト ファイルに直接かつ効率的にアクセスする方法は?

Question

データ マイニング技術のために読みたい非常に大きなテキスト ファイル (+10GB) があります。そのために、MPI で並列技術を使用して、多くのプロセスが同じファイルにまとめてアクセスできるようにします。
実際、各プロセスが N 行を読み取るようにしたいのです。ファイルは構造化されていないため (フィールド数は同じですが、各フィールドには異なる数の文字を含めることができます)、ファイルを解析する義務があり、それは並列ではなく、多くの時間がかかります。行を解析してカウントせずに、特定の行数に直接アクセスする方法はありますか? 助けてくれてありがとう。

Answer 1

ファイルにインデックスが付けられていない場合、直接的な方法はありません。

インデックスを作成する価値があるかもしれません（一度スキャンしてすべての行末を見つけ、各行または行のチャンクのオフセットを保存します）。ファイルを複数回処理する必要があり、ファイルが変更されない場合、インデックス作成のコストは、以降の実行でインデックスを使用することの容易さによって相殺される可能性があります。

それ以外の場合、すべてのジョブがまったく同じ数の行/アイテムを持つ必要がない場合は、それをごまかすことができます。
与えられたオフセット（たとえば1G）を探し、最も近いラインセパレーターを探します。十分なブレークポイントが見つかるまで、オフセット2Gなどで繰り返します。

次に、識別した各チャンクで並列タスクを実行できます。

Answer 2

A few other options beyond what has been mentioned here that will not require scanning the whole file:

1. make a master process that pushes lines via pipes/fifos to child processes that do the actual processing. This might be a bit slower but if say 90% of the time spent in the subprocesses is the actual crunching of texts, it should be ok.

2. A stupid but effective trick: say you have N processes, and you can tell each process by argv or something it's "serial number" e.g. processor -serial_number [1|2|3...N] -num_procs N, they can all read the same data, but process only lines that have lineno % num_procs == serial_number. it's a bit less efficient because they will all read the entire data, but again, if they only work on every Nth line, and that is what consumes most of the time, you should be fine.

Answer 3

いいえ、ありません。不明なデータを読み通さない限り、改行文字がいくつあるかは誰にもわかりません。この問題の複雑さはO（n）であるため、少なくとも1回はファイル全体を読み取る必要があります。次に、ファイル内の改行文字がある場所を記録するインデックステーブルを作成することをお勧めします。これはすべてのプロセスで使用でき、fseekを使用するとさらにアクセスを大幅に高速化できます。