15

Cを使用してテキストファイルでランダムな行を返す最良の方法は何ですか? <stdio.h>ニンテンドーDS自作用なので、標準I/Oライブラリ( )を使う必要があります。

説明:

  • ファイルのヘッダーを使用して行数を保存しても、私がやりたいことはうまくいきません。
  • できるだけランダムにしたい（各行が他のすべての行と同じ確率で選択される場合に最適です。）
  • プログラムの実行中にファイルが変更されることはありません。（これはDSなので、マルチタスクではありません。）
4

8 に答える 8

29

各行を読み、乱数を使用してその行を保持するか無視するかを選択します。最初の行では、1:1 のオッズを維持する必要があります。2 番目の場合は、1:2 のオッズが必要です。

count = 0;
while (fgets(line, length, stream) != NULL)
{
    count++;
    if ((rand() * count) / RAND_MAX == 0)
        strcpy(keptline, line);
}

これが適切なランダム性を持っているかどうかは確認していませんが、一見すると正しいように見えます。

整数オーバーフローは、比較のコーディング方法ですぐに問題になることが指摘されており、私も独自に同じ結論に達しました。修正方法はいろいろあると思いますが、最初に思いついたのは次の方法です。

if ((rand() / (float)RAND_MAX) <= (1.0 / count))
于 2008-10-24T02:01:54.080 に答える
8

マークの答えは、2 つの問題を除いてほぼ正しいです。

  1. 行が文字数よりも長い場合length - 1(改行を含む)、whileループはcount同じ行に対して少なくとも 2 回インクリメントします: 最初のlength - 1文字に対して 1 回、次のlength - 1文字に対して 1 回、などです。
  2. の計算によりrand() * count、整数オーバーフローが発生する可能性があります。

最初の問題を解決するには、(データが読み取られずに I/O エラーまたは EOF を示す)fgets返されるか、ゴミ箱バッファーに改行が含まれるまで、ゴミ箱バッファーを呼び出すことができます。NULL

count = 0;
while (fgets(line, length, stream) != NULL)
{
    char *p = strchr(line, '\n');
    if (p != NULL) {
        assert(*p == '\n');
        *p = '\0'; // trim the newline
    }
    else { // haven't reached EOL yet. Read & discard the rest of the line.
#define TRASH_LENGTH 1024
        char trash[TRASH_LENGTH];
        while((p = fgets(trash, TRASH_LENGTH, stream)) != NULL) {
            if ((p = strchr(trash, '\n')) != NULL) // reached EOL
                break;
        }
    }
    assert(strchr(line, '\n') == NULL); // `line` does not contain a newline
    count++;
    // ...

浮動小数点演算が利用できない場合、2番目の問題は@tvanfossonの提案で解決できます。

int one_chance_in(size_t n)
{
    if (rand() % n == 0) // `rand` returns an integer in [0, `RAND_MAX`]
        return 1;
    else
        return 0;
}

ただし、が 1 であると仮定されたとしても、 は一様で離散的な確率変数rand() % nではないことに注意してください。私のマシンでは 2147483647 であるため、差は 4.66 × 10 -10ですが、C 標準では少なくとも 32767 (3.05 × 10 -5差) である必要があるだけです。rand()rand() % n == 0RAND_MAXnRAND_MAXRAND_MAX

また、なぜこのスキームが機能するのか疑問に思っている人には (私のように)、mkeptline行ある場合に最初の行が残る確率を計算して一般化すると役立つかもしれません: ループの最初の反復では、最初の行がコピーされる確率は 1/1 です。ループの 2 回目の繰り返しで、2 行目が最初の行を上書きしない確率は 1/2 です。3 回目の反復で、3 行目が最初の行を上書きしない確率は 2/3 です。続けて、最後の行が最初の行を上書きしない確率は ( m - 1)/ mです。したがって、最初の行が残る確率はkeptlinekeptlineすべての行を反復した後は次のとおりです。

1/1 × 1/2 × 2/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m = 1/ m

2行目が残る確率は次のkeptlineとおりです。

1/2 × 2/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m = 1/ m

3行目が残る確率keptlineは次のとおりです。

1/3 × 3/4 × ... × ( m - 2)/( m - 1) × ( m - 1)/ m = 1/ m

これらはすべて 1/ mです。

于 2010-05-28T23:44:29.183 に答える
6

この方法が優れている理由は次のとおりです。

i) 大きなコストをかけずにランダムな線を生成し続けることができます

ii) ファイルを合計 1 回 + 必要なランダムな行ごとに一度に 1 行だけ読み取る必要があります。余分な読み取りデータは、ファイルのサイズに等しいだけです。

iii) ファイル内の位置に関係なく、各行に公平な機会を与えます。

iv) ファイル内の長さに関係なく、各行に公平な機会を与えます。

提案:

2パスアルゴリズムをお勧めします。実際には、1 パス + N 行です。N は、必要なランダム行の数です。

行数と各行の開始位置を計算するために使用する最初のパス。

次に、0 から行数 - 1 までの乱数を取得します。行インデックスであるその乱数を使用して、その行インデックスの開始位置を取得します。その位置にシークします。

その後、必要な読み取りはあと 1 回だけで、正確なサイズがわかります。(次の行の開始インデックスまで)

行数と各行のインデックスを保存する方法:

行数を格納するには、明らかに int を使用できます。

ベクトルを使用できる場合は、各行のインデックスをベクトルに追加できます。そうでない場合は、存在すると思われる最大行数でintの配列を作成できます。次に、その配列にインデックスを付けます。

その他の回答:

別の回答では、1 からファイルのサイズまでの乱数を選択してから、最も近い改行を使用できると述べています。しかし、これはうまくいきません。たとえば、非常に長い 1 つの行とそれほど長くない他の行があるとします。その場合、分布が不均一になります。

于 2008-10-24T02:01:11.680 に答える
3
  1. ファイルの長さを取得します。
  2. ファイル内のランダムな位置を選択します。
  3. その位置にシークします。
  4. 改行文字が見つかるまで繰り返します。
  5. 改行文字が見つからない場合は、先頭に戻ります。
  6. gets() を使用して行を読み取ります。
于 2008-10-24T02:02:13.300 に答える
0

生成するすべての乱数の最大値を維持しながら、行ごとに1つのスケーリングされていない乱数を生成するだけです。最大値を更新するたびに、選択した行を現在の行で上書きします。

最後に、最大数のrand（）に関連付けられた行が吐き出されます。これは、すべての行で同じ確率で発生するはずです。

于 2008-11-01T02:29:38.270 に答える
0

別の解決策があります。プラットフォームは DS であるため、おそらくファイルをメモリに保持しようとは思わないでしょう。これにより、ファイルが 2 回読み取られます。1 回目は行を数え、2 回目は目的の行を見つけます。これは、これまでに提案された他のソリューションよりも遅く実行されますが、ほとんどメモリを使用しません. 私はあなたのためにCでそれを書きました（私はエラー処理を省略しました）：

main(int argc, char **argv)
{
    FILE *f;
    int nLines = 0;
    char line[1024];
    int randLine;
    int i;

    srand(time(0));
    f = fopen(argv[1], "r");

/* 1st pass - count the lines. */
    while(!feof(f))
    {
        fgets(line, 1024, f);
        nLines++;
    }

    randLine = rand() % nLines;
    printf("Chose %d of %d lines\n", randLine, nLines);

/* 2nd pass - find the line we want. */
    fseek(f, 0, SEEK_SET);
    for(i = 0; !feof(f) && i <= randLine; i++)
        fgets(line, 1024, f);

    printf("%s", line);
}

更新:おっと、これを投稿する前に Brian R. Bondy の回答を読むべきでしたが、コードの記述に夢中になっていて、気づきませんでした。これは、行の位置を配列に格納しないことを除いて、ほとんど同じです。ファイルの大きさと、メモリの節約よりも速度が重要かどうかに応じて、どちらの方法でも実行できます。

于 2008-10-24T02:21:43.883 に答える
0

整数オーバーフローを回避するMark Ransomの方法についての簡単なメモ: DS には FPU がないため、浮動小数点除算はソフトウェアでエミュレートされ、非常に遅くなります。速度が懸念される場合は、型キャスト/フロートまたはダブルへの昇格を絶対に避けたいと思うでしょう。

浮動小数点演算を回避する整数オーバーフローを回避する別の方法を次に示します。

if(rand() <= RAND_MAX / count)

確率は整数除算のためにわずかに歪む可能性がありますが、これは確かに DS ではるかに高速に実行されるはずです。

于 2008-11-06T02:42:24.090 に答える
-1

ファイル アプローチへの Adam のランダム オフセットと Mark の確率アプローチを組み合わせて使用​​します。Adam の方法では、ファイルのセクションにランダムにアクセスできます。次に、マークのアプローチを使用して、より大きな文字列を優先しないようにします。マークのアルゴリズムは、どこから始めても最初の数文字列を優先します。

于 2008-10-24T02:29:15.040 に答える