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

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

澄清:

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

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

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

  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()假设为1,因为rand() % n == 0的概率可能高于所需的1 / RAND_MAX概率1 / n 。 在我的机器上, RAND_MAX是2147483647,所以差值是4.66×10 -10 ,但C标准只要求RAND_MAX至少为32767(3.05×10 -5差异)。

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

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

这种方法很好,因为:

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

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

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

iv)无论文件的长度是多少,它都给予每一行公平的机会。

建议:

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

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

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

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

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

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

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

其他答案:

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

  1. 获取文件的长度。
  2. 在文件中选择一个随机位置。
  3. 寻求那个位置。
  4. 向前迭代,直到找到换行符。
  5. 如果找不到换行符,请回头查看。
  6. 使用gets()来读取该行。

我有另一种解决方案。 由于平台是DS,您可能不想尝试将文件保存在内存中。 这会两次读取文件。 一旦计算线数,第二次找到它想要的线。 这将比目前为止建议的其他解决方案运行得慢,但它几乎不使用任何内存。 我甚至为你写了C(我省略了error handling):

 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的回答,但我有点痴迷于编写代码而没有注意到。 这几乎是相同的,除了它不存储数组中的行位置。 您可以采用任何一种方式,具体取决于文件的大小以及速度是否比保存内存更重要。

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

最后,你得到与最高数字rand()spat out相关联的行,这在你的所有行中应该是同样可能的。

只是关于Mark Ransom避免整数溢出的方法的快速说明:DS没有FPU,因此浮点除法将在软件中模拟并且非常慢。 如果速度是一个问题,你会想要不惜一切代价避免类型转换/促销浮动或加倍。

这是一种避免整数溢出的不同方法,它避免了任何浮点数学运算:

 if(rand() <= RAND_MAX / count) 

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

使用Adam的随机偏移量组合到文件方法和Mark的概率方法中。 Adam的方法可以让你随机到达文件的一部分。 然后你使用Mark的方法来避免使用更大的字符串。 Mark的算法会优先选择开始的几个字符串,