15

使用 C 在文本文件中返回随机行的最佳方法是什么？它必须使用标准 I/O 库 ( <stdio.h>)，因为它适用于 Nintendo DS 自制软件。

说明：

  • 使用文件中的标题来存储行数不适用于我想做的事情。
  • 我希望它尽可能随机（最好是如果每一行都有与其他行一样被选择的概率。）
  • 程序运行时文件永远不会改变。（这是 DS，所以没有多任务处理。）
4

8 回答 8

29

阅读每一行，并使用一个随机数来选择是保留该行还是忽略它。对于第一行，您希望保持 1:1 的赔率；对于第二个，你想要 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

马克的回答几乎是正确的，除了两个问题：

  1. 如果一行比length - 1字符长（包括换行符），那么while循环将count至少为同一行增加两次：第一个length - 1字符一次，下一个length - 1字符一次，等等。
  2. 的计算rand() * count会导致整数溢出。

要解决第一个问题，您可以调用fgets垃圾缓冲区，直到它返回NULL（指示 I/O 错误或没有数据读取的 EOF）或垃圾缓冲区包含换行符：

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++;
    // ...

如果浮点运算不可用，则可以通过@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;
}

但请注意，即使假设为一个，这rand() % n也不是一个统一的离散随机变量rand()，因为概率rand() % n == 0可能RAND_MAX比期望的概率 1/ 高 1/ n。在我的机器上，RAND_MAX是 2147483647，所以差异是 4.66 × 10 -10，但 C 标准只要求RAND_MAX至少是 32767（3.05 × 10 -5差异）。

keptline此外，对于任何想知道为什么这个方案有效的人（就像我一样），如果有m行并概括，计算第一行保留的概率可能会有所帮助：在循环的第一次迭代中，第一行被复制到的概率keptline是 1/1。在循环的第二次迭代中，第二行不覆盖第一行的概率为1/2。在第三次迭代中，第三行不覆盖第一行的概率为 2/3。继续，最后一行不覆盖第一行的概率是 ( m - 1)/ m。因此，第一行保留在keptline遍历所有行之后是：

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

第二行保留的概率keptline是：

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

第三行保留的概率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 pass + N 行。其中 N 是您想要的随机行数。

第一遍用于计算行数和每行的起始位置。

然后，您从 0 到行数减 1 取一个随机数。使用该随机数，即您的行索引，获取该行索引的起始位置。寻求那个位置。

然后，您只需要再读取 1 次，并且您知道确切的大小。（直到下一行的开始索引）

如何存储行数和每行的索引：

要存储行数，您显然可以只使用 int。

如果可以使用向量，则可以将每个行索引添加到向量中。如果不是，您可以创建一个整数数组，其中包含您认为会有的最大行数。然后索引到该数组。

其他答案：

另一个答案提到您可以从 1 到文件大小选择一个随机数，然后使用最接近的换行符。但这行不通。例如，您可能有 1 行非常长，而其他行则不那么长。在这种情况下，您的分布将不均匀。

于 2008-10-24T02:01:11.680 回答
3
  1. 获取文件的长度。
  2. 在文件中选择一个随机位置。
  3. 寻求那个位置。
  4. 向前迭代，直到找到换行符。
  5. 如果您没有找到换行符，请回到开头。
  6. 使用gets() 读取该行。
于 2008-10-24T02:02:13.300 回答
0

我有一个替代解决方案。由于平台是 DS，您可能不想尝试将文件保存在内存中。这会读取文件两次。一次计算行数，第二次找到它想要的行。这将比目前建议的其他解决方案运行得慢，但它几乎不使用任何内存。我什至为你用 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

您需要做的就是每行生成一个未缩放的随机数，同时保持您生成的所有随机数的最大值。每当您更新最大值时，都会用当前行覆盖所选行。

最后，您会得到与 rand() 吐出的最高数字相关联的行，这在您的所有行中应该是同样可能的。

于 2008-11-01T02:29:38.270 回答
0

简单介绍一下Mark Ransom避免整数溢出的方法：DS 没有 FPU，因此浮点除法将在软件中模拟，并且非常慢。如果速度是一个问题，您将不惜一切代价避免类型转换/提升浮动或加倍。

这是避免任何浮点数学运算的避免整数溢出的另一种方法：

if(rand() <= RAND_MAX / count)

由于整数除法，概率可能会略微偏斜，但这在 DS 上肯定会运行得更快。

于 2008-11-06T02:42:24.090 回答
-1

使用 Adam 的随机偏移到文件方法和 Mark 的概率方法的组合。亚当的方法可以让你随机进入文件的一部分。然后，您使用 Mark 的方法来避免偏爱较大的字符串。Mark 的算法会从它开始的地方优先选择前几个字符串，

于 2008-10-24T02:29:15.040 回答