9

これは本質的に、この質問のより制約されたバージョンです。

多数の行を含む非常に大きなテキストファイルがあるとします。

一定の確率でファイルからランダムに行を選択する必要がありますが、制約があります。

  • これはソフトリアルタイムアプリケーションであるため、ファイル全体を反復処理することはできません。選択には一定の時間がかかるはずです。
  • メモリの制約により、ファイルをキャッシュできません。
  • ファイルは実行時に変更できるため、ファイルの長さを一定と見なすことはできません。

私の最初の考えは、lstat()呼び出しを使用して合計ファイルサイズをバイト単位で取得することです。fseek()次に、ランダムなバイトオフセットに直接アクセスするために使用でき、ファイルのランダムな部分へのO（1）アクセスのようなものを取得します。

問題は、次の改行を読んでそれを1日と呼ぶようなことはできないということです。これは、長い行に偏った分布が生成されるためです。

この問題を解決するための私の最初の考えは、最初の「n」の改行（必要に応じてファイルの先頭に折り返す）まで読み、次にこの小さいセットから均一な確率で行を選択することです。ファイルの内容はランダムに並べられていると考えるのが安全です。したがって、このサブサンプルは長さに関して均一である必要があります。また、開始点はすべての可能な点から均一に選択されているため、ファイルからの均一な選択を次のように表す必要があります。全体。したがって、疑似Cでは、アルゴリズムは次のようになります。

 lstat(filepath, &filestat);
 fseek(file, (int)(filestat.off_t*drand48()), SEEK_SET);
 char sample[n][BUFSIZ];
 for(int i=0;i<n;i++)
     fgets(sample[i], BUFSIZ, file); //plus some stuff to deal with file wrap around...
 return sample[(int)(n*drand48())];

これは特にエレガントな解決策のようには思えませんし、均一になるとは完全には確信していません。そのため、もっと良い方法があるのではないかと思います。何かご意見は？

編集：さらに検討すると、開始点は長い単語の中にある可能性が高く、したがって均一ではないため、私の方法は均一ではないと確信しています。トリッキー！

4

3 に答える 3

2

ファイルからランダムな文字を選択します（前述のようにrandとseekを使用）。ここで、関連する改行を見つける代わりに、あなたが指摘したようにそれが偏っているので、私は次のアルゴリズムを適用します：


Is the character a newline character?
   yes - use the preceeding line
   no  - try again

これがどのように線の均一な分布以外に何を与えることができるか私にはわかりません。効率は、ラインの平均の長さに依存します。ファイルの行が比較的短い場合、これは機能する可能性がありますが、OSでもファイルを実際にプリキャッシュできない場合は、物理ディスクのシークに多額の費用がかかる可能性があります。

于 2012-11-21T20:11:19.170 に答える
2

驚くほどうまく機能する解決策が見つかりました。自分自身と他の人のためにここに文書化します。

このコード例は、実際には 1 秒あたり約 80,000 回の描画を行い、ほとんどの実行でファイルの平均行長と一致する有効数字 4 桁になります。対照的に、相互参照された質問の方法を使用すると、毎秒約 250 の描画が得られます。

基本的に、ファイル内のランダムな場所をサンプリングし、それを破棄して、行の長さに反比例する確率で再度描画します。これにより、長い単語の偏りが解消されます。平均して、このメソッドは、1 つを受け入れる前に、ファイル内の平均行長と同じ数の描画を行います。

いくつかの注目すべき欠点:

  • 行の長さが長いファイルでは、描画ごとに拒否される回数が多くなり、これが大幅に遅くなります。

  • 行の長さが長いファイルには、rdraw 関数で 50 よりも大きな定数が必要です。これは、行の長さが大きな変動を示す場合、実際にはシーク時間がはるかに長くなることを意味するようです。たとえば、テストした 1 つのファイルで BUFSIZ に設定すると、描画速度が 1 秒あたり約 10000 描画に低下しました。ただし、ファイル内の行をカウントするよりもはるかに高速です。

    int rdraw(FILE* where, char *storage, size_t bytes){
    int offset = (int)(bytes*drand48());
    int initial_seek = offset>50?offset-50:0;
    fseek(where, initial_seek, SEEK_SET);
    int chars_read = 0;
    while(chars_read + initial_seek < offset){
            fgets(storage,50,where);
            chars_read += strlen(storage);
    }
    return strlen(storage);
}

int main(){
    srand48(time(NULL));
    struct stat blah;
    stat("/usr/share/dict/words", &blah);
    FILE *where = fopen("/usr/share/dict/words", "r");
    off_t bytes = blah.st_size;
    char b[BUFSIZ+1];

    int i;
    for(i=0;i<1000000; i++){
            while(drand48() > 1.0/(rdraw(where, b, bytes)));
    }

}
于 2012-11-21T15:00:39.803 に答える
1

ファイルが最終的にのみ変更される (より多くの行が追加される) 場合、一様確率でアルゴリズムを作成できます。

準備: 各 n: 行のオフセットを含むインデックス ファイルを作成します。固定幅形式を使用して、位置を使用して所有しているレコードを判別できるようにします。

  1. インデックス ファイルを開き、最後のレコードを読み取ります。ftellレコード番号を決定するために使用します。

  2. 大きなファイルを開き、fseek手順 1 で取得したオフセットに移動します。

  3. 大きなファイルを最後まで読み取り、改行の数を数えます。これで、大きなファイルの合計行数がわかりました。

  4. 手順3で取得した行数まで乱数を発生させます。

  5. fseekインデックス ファイル内の適切なレコードにアクセスして読み取ります。

  6. fseek大きなファイルの適切なオフセットに。残りの改行をスキップします。

  7. 行を読んでください！

例

n=100 を選択し、大きなファイルに 367 行が含まれているとします。

索引ファイル:

00000000,00004753,00009420,00016303

  1. インデックス ファイルには 4 つのレコードがあるため、大きなファイルには少なくとも 300 レコード (100* (4-1)) が含まれます。最後のオフセットは 16303 です。

  2. 大きなファイルを開き、fseek16303 に移動します。

  3. 残りの行数 (67) を数えます。

  4. [0-366] の範囲で乱数を生成します。112だったとしましょう。

  5. 112/100 = 1 余りは 12 です。オフセット 1 のインデックス ファイル レコードを読み取ります。結果は 4753 です。

  6. fseek大きなファイルで 4753 に変更し、11 (12-1) 行をスキップします。

  7. 12行目を読んでください。

出来上がり！

編集：

対象ファイルのコメントが変わっているのを見ました。ターゲット ファイルがめったに変更されない場合でも、これは実行可能なアプローチである可能性があります。ターゲット ファイルを切り替える前に、新しいインデックス ファイルを作成する必要があります。nターゲット ファイルが行数を超えて大きくなったときに、インデックス ファイルを更新することもできます。

于 2012-11-20T17:37:15.200 に答える