使用C在文本文件中返回随机行的最佳方法是什么？

Question

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

澄清:

• 使用文件中的标题来存储行数不适用于我想要做的事情.
• 我希望它尽可能随机(如果每条线具有被选为每隔一条线的相同概率,则最好.)
• 程序运行时,该文件永远不会更改.(这是DS,所以没有多任务处理.)

Answer 1

读取每一行,并使用随机数选择是保留该行还是忽略该行.对于第一行,您希望保持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)) 

Answer 2

马克的答案几乎是正确的,除了两个问题:

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;
}

但请注意,即使假设为1 ,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.

Answer 3

这种方法很好,因为:

i)你可以不费力地生成随机线

ii)您只需要每个随机行一次读取文件总共1次+ 1行.多余的读取数据仅等于文件的大小.

iii)无论文件中的位置如何,它都给予每一行公平的机会.

iv)无论文件的长度如何,它都给予每一行公平的机会.

建议:

我建议使用2遍算法.那真的是1次传球+ N次线.其中N是您想要的随机行数.

您将用于计算每行的行数和起始位置的第一个过程.

然后,您将从0开始的随机数减去行数减1.使用该随机数(行索引)获取该行索引的起始位置.寻求那个位置.

然后,您只需要再读取一次,并且您知道确切的大小.(直到下一行的起始索引)

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

要存储行数,您显然可以使用int.

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

其他答案:

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