在 C 中以均匀概率有效地从文本文件中选择随机行？

这本质上是一个更受限制的版本这个问题 https://stackoverflow.com/questions/232237/whats-the-best-way-to-return-a-random-line-in-a-text-file-using-c.

假设我们有一个非常大的文本文件，包含大量行。

我们需要以统一的概率从文件中随机选择一行，但有一些限制：

• 因为这是一个软实时应用程序，所以我们无法迭代整个文件。选择应该花费恒定的时间。
• 由于内存限制，无法缓存该文件。
• 由于文件允许在运行时更改，因此不能假定文件的长度是常量。

我的第一个想法是使用lstat()调用以获取总文件大小（以字节为单位）。fseek()然后可以用于直接访问随机字节偏移量，以 O(1) 的方式访问文件的随机部分。

问题是我们不能做类似读到下一个换行符然后就到此为止的事情，因为这会产生偏向于长行的分布。

我解决这个问题的第一个想法是读取直到前“n”个换行符（如果需要，回绕到文件的开头），然后从这个较小的集合中选择具有统一概率的行。可以安全地假设文件的内容是随机排序的，因此该子样本在长度方面应该是统一的，并且由于其起点是从所有可能的点中统一选择的，因此它应该将文件中的统一选择表示为所有的。所以，在pseudo-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())];

这似乎不是一个特别优雅的解决方案，而且我并不完全相信它会是统一的，所以我想知道是否有更好的方法来做到这一点。有什么想法吗？

编辑：经过进一步考虑，我现在非常确定我的方法不统一，因为起点更有可能位于较长的单词内，因此不统一。棘手！

从文件中选择一个随机字符（如您所述，通过 rand 和eek）。现在，我将应用以下算法，而不是查找关联的换行符，因为正如您所指出的那样，这是有偏差的：

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

我不明白这除了均匀分布的线之外还能给出什么。效率取决于线路的平均长度。如果您的文件的行相对较短，则这可能是可行的，但如果该文件确实无法通过操作系统进行预缓存，则您可能会在物理磁盘查找中付出高昂的代价。