有效地选择从在C均匀概率的文本文件的随机行？(Efficiently choosing a rand

这基本上是一个更受限的版本这个问题。

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

我们需要选择从文件随机线，均匀的概率，但也有限制：

因为这是一个软实时的应用程序，我们无法遍历整个文件。在选择时应采取的恒定时间十岁上下的量。
由于内存的限制，该文件不能被缓存。
因为该文件被允许在运行时改变，文件的长度不能被假定为是恒定的。

我首先想到的是使用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和寻求正如你指出）。现在，而不是找到相关的换行符，因为这正如你指出有失偏颇，我会申请如下算法：


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

我看不出这可以给任何东西，但线的均匀分布。效率取决于一行的平均长度。如果你的文件有线路比较短，这可能是可行的，但如果该文件确实也不能将由OS预缓存，您可以在物理磁盘寻道付出了沉重的代价。

Answer 2:

解决方案发现，其中工程出奇地好。记录在这里为自己和他人。

该示例代码执行每秒约80000平在实践中，与匹配的文件，以4显著位上多数奔跑的平均线的长度。相比之下，我得到约250使用从方法每秒绘制交叉引用的问题。

从本质上讲它所做的抽样文件中的任意地方，然后将其丢弃，并用概率成反比线路长度再次战平。这抵消了更长的话偏差。平均来说，该方法提出了一些平接受一个前等于该文件中的平均线的长度。

一些显着的缺点：

较长的线路长度的文件将产生更多的拒绝每绘图，使这个慢得多。

具有较长的线路长度文件需要比在rdraw功能，从而出现50更大的恒定意味着更长寻求在实践倍如果线路长度表现出高方差。例如，将其设置为BUFSIZ对我降低消耗的速度测试，以10000左右一个文件每秒平局。仍比文件中虽然计数线快得多。

 int rdraw(FILE* where, char *storage, size_t bytes){ int offset = (int)(bytes*drand48()); int initial_seek = offset>50?offset-50:0; fseek(where, initial_seek, SEEK_SET); int chars_read = 0; while(chars_read + initial_seek < offset){ fgets(storage,50,where); chars_read += strlen(storage); } return strlen(storage); } int main(){ srand48(time(NULL)); struct stat blah; stat("/usr/share/dict/words", &blah); FILE *where = fopen("/usr/share/dict/words", "r"); off_t bytes = blah.st_size; char b[BUFSIZ+1]; int i; for(i=0;i<1000000; i++){ while(drand48() > 1.0/(rdraw(where, b, bytes))); } }