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

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

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

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

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

我的第一个想法是使用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())]; 

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

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

从文件中选择一个随机字符(通过rand并按照您的说明进行搜索)。 现在,我没有找到相关的换行符,因为你注意到它有偏见,我会应用以下算法:

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

我看不出除了线条的均匀分布外,它怎么能给出任何东西。 效率取决于线的平均长度。 如果你的文件行相对较短,这可能是可行的,但如果文件甚至无法通过操作系统进行预处理,你可能会在物理磁盘搜索中付出沉重的代价。

找到了解决方案,效果出奇的好。 在这里为自己和他人记录。

此示例代码在实践中每秒执行大约80,000次绘制,平均行长度与文件的长度匹配,在大多数运行中为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))); } } 

如果文件最后只更改(添加更多行),您可以创建一个具有统一概率的算法:

准备:创建一个索引文件,其中包含每个第n行的偏移量。 使用固定宽度格式,以便位置可用于确定您拥有的记录。

  1. 打开索引文件并读取最后一条记录。 使用ftell确定记录号。

  2. 打开大文件并fseek到步骤1中获得的偏移量。

  3. 阅读大文件到最后,计算换行数。 您现在拥有大文件中的总行数。

  4. 生成一个随机数,直到步骤3中获得的行数。

  5. fseek并读取索引文件中的相应记录。

  6. fseek到大文件中的适当偏移量。 跳过其余的换行符。

  7. 读行!

假设我们选择n = 100并且大文件包含367行。

索引文件:

 00000000,00004753,00009420,00016303 
  1. 索引文件有4条记录,因此大文件包含至少300条记录(100 *(4-1))。 最后一次偏移是16303。

  2. 打开大文件,然后将fseek打开到16303。

  3. 计算剩余的行数(67)。

  4. Generata是[0-366]范围内的随机数。 假设我们得到112。

  5. 112/100 = 1,余数为12。 读取偏移量为1的索引文件记录。我们得到结果4753。

  6. fseek到大文件中的4753然后跳过11(12-1)行。

  7. 阅读第12行。

瞧!

编辑:

我看到目标文件的评论发生了变化。 如果目标文件很少变化,那么这可能仍然是一种可行的方法。 在切换目标文件之前,您需要创建一个新的索引文件。 当目标文件增长超过n行时,您可能还希望更新索引文件。