9

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

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

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

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

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

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

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

4

3 回答 3

2

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

此示例代码在实践中每秒执行大约 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)));
    }

}
于 2012-11-21T15:00:39.803 回答
2

从文件中选择一个随机字符（通过 rand 并按照您的说明进行搜索）。现在，而不是找到相关的换行符，因为正如你所指出的那样有偏见，我将应用以下算法：


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

除了线条的均匀分布之外，我看不出这怎么能提供任何东西。效率取决于一条线的平均长度。如果您的文件有相对较短的行，这可能是可行的，但如果文件真的不能被操作系统预缓存，您可能会在物理磁盘寻道上付出沉重的代价。

于 2012-11-21T20:11:19.170 回答
1

如果文件最后只更改（添加更多行），您可以创建具有统一概率的算法：

准备工作：创建一个索引文件，其中包含每个第 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当目标文件增长超过行数时，您可能还想更新索引文件。

于 2012-11-20T17:37:15.200 回答