在C中有效地从文本文件中有效地选择随机行？

Question

这本质上是这个问题的一个受限制的版本.

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

我们需要从文件中随机选择一条线,具有统一的概率,但是存在约束条件:

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

我的第一个想法是使用lstat()调用以字节为单位获取总文件大小.fseek()然后可以用来直接访问随机字节偏移量,将类似O(1)的内容访问到文件的随机部分.

问题是我们不能再做一些事情,比如读到下一个换行符并将其称为一天,因为这会产生偏向长线的分布.

我解决这个问题的第一个想法是读取直到第一个"n"换行符(如果需要,回到文件的开头),然后从这个较小的集合中选择一个具有统一概率的行.可以安全地假设文件的内容是随机排序的,因此这个子样本在长度上应该是统一的,并且,由于它的起始点是从所有可能的点统一选择的,所以它应该代表从文件中统一选择的整个.所以,在伪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())];

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

编辑:进一步考虑,我现在很确定我的方法不统一,因为起点更可能在更长的单词内,因此不统一.整蛊!

Answer 1

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

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

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