使用C在文本文件中返回随机行的最佳方法是什么?
使用C在文本文件中返回随机行的最佳方法是什么? 它必须使用标准I / O库( ),因为它适用于Nintendo DS自制程序。
澄清:
- 使用文件中的标题来存储行数不适用于我想要做的事情。
- 我希望它尽可能随机(如果每条线具有被选为每隔一条线的相同概率,则最好。)
- 程序运行时,该文件永远不会更改。 (这是DS,所以没有多任务处理。)
读取每一行,并使用随机数选择是保留该行还是忽略该行。 对于第一行,您希望保持1:1的赔率; 对于第二个,你想要1:2的赔率等。
count = 0; while (fgets(line, length, stream) != NULL) { count++; if ((rand() * count) / RAND_MAX == 0) strcpy(keptline, line); }
我没有证实它具有适当的随机性质,但乍一看似乎是正确的。
已经指出整数溢出很快就会成为比较编码方式的问题,我自己也独立地得出了相同的结论。 可能有很多方法可以修复它,但这是第一个想到的方法:
if ((rand() / (float)RAND_MAX) <= (1.0 / count))
马克的回答几乎是正确的,除了两个问题:
- 如果一行超过
length - 1
字符(包括换行符),那么while
循环将为同一行增加至少两次count
:一次为第一个length - 1
字符,另一个为下一个length - 1
字符等。 -
rand() * count
可能导致整数溢出。
要解决第一个问题,您可以将fgets
调用到垃圾缓冲区,直到它返回NULL
(表示I / O错误或没有数据读取的EOF)或垃圾缓冲区包含换行符:
count = 0; while (fgets(line, length, stream) != NULL) { char *p = strchr(line, '\n'); if (p != NULL) { assert(*p == '\n'); *p = '\0'; // trim the newline } else { // haven't reached EOL yet. Read & discard the rest of the line. #define TRASH_LENGTH 1024 char trash[TRASH_LENGTH]; while((p = fgets(trash, TRASH_LENGTH, stream)) != NULL) { if ((p = strchr(trash, '\n')) != NULL) // reached EOL break; } } assert(strchr(line, '\n') == NULL); // `line` does not contain a newline count++; // ...
如果浮点运算不可用,@ tvanfosson的建议可以解决第二个问题:
int one_chance_in(size_t n) { if (rand() % n == 0) // `rand` returns an integer in [0, `RAND_MAX`] return 1; else return 0; }
但请注意, rand() % n
不是一个统一的离散随机变量,即使rand()
假设为1,因为rand() % n == 0
的概率可能高于所需的1 / RAND_MAX
概率1 / n
。 在我的机器上, RAND_MAX
是2147483647,所以差值是4.66×10 -10 ,但C标准只要求RAND_MAX
至少为32767(3.05×10 -5差异)。
此外,对于任何想知道为什么这个方案有效的人(就像我一样),如果有m行并且概括,那么计算第一行保留在保持行中的概率可能会有所帮助:在循环的第一次迭代中,第一行被复制到keptline
的概率是1/1。 在循环的第二次迭代中,第二行不覆盖第一行的概率是1/2。 在第三次迭代中,第三行不覆盖第一行的概率是2/3。 继续,最后一行不覆盖第一行的概率是( m -1)/ m 。 因此,在迭代所有行之后第一行保持在保持行中的概率是:
1/1×1/2×2/3×3/4×……×( m – 2)/( m – 1)×( m – 1)/ m = 1 / m
第二行保留在keptline
的概率是:
1/2×2/3×3/4×……×( m – 2)/( m – 1)×( m – 1)/ m = 1 / m
第三行保留在keptline
的概率是:
1/3×3/4×…×( m – 2)/( m – 1)×( m – 1)/ m = 1 / m
等等。他们都是1 / m 。
这种方法很好,因为:
i)您可以不费力地生成随机线
ii)您只需要每个随机行一次读取文件总共1次+ 1行。 多余的读取数据仅等于文件的大小。
iii)无论文件中的位置如何,它都给予每一行公平的机会。
iv)无论文件的长度是多少,它都给予每一行公平的机会。
建议:
我建议使用2遍算法。 那真的是1次传球+ N次线。 其中N是您想要的随机行数。
您将用于计算每行的行数和起始位置的第一个过程。
然后,您将从0开始的随机数减去行数减1.使用该随机数(行索引)获取该行索引的起始位置。 寻求那个位置。
然后,您只需要再读取一次,并且您知道确切的大小。 (直到下一行的起始索引)
如何存储行数和每行的索引:
要存储行数,您显然可以使用int。
如果可以使用向量,则可以将每个行索引添加到向量中。 如果不是,您可以创建一个包含您认为最大行数的整数数组。 然后索引到该数组。
其他答案:
另一个答案提到你可以从1到文件大小中选择一个随机数,然后使用最近的换行符。 但这不起作用。 例如,您可能有1行非常长,而其他行则不长。 在这种情况下,您的分布将不均匀。
- 获取文件的长度。
- 在文件中选择一个随机位置。
- 寻求那个位置。
- 向前迭代,直到找到换行符。
- 如果找不到换行符,请回头查看。
- 使用gets()来读取该行。
我有另一种解决方案。 由于平台是DS,您可能不想尝试将文件保存在内存中。 这会两次读取文件。 一旦计算线数,第二次找到它想要的线。 这将比目前为止建议的其他解决方案运行得慢,但它几乎不使用任何内存。 我甚至为你写了C(我省略了error handling):
main(int argc, char **argv) { FILE *f; int nLines = 0; char line[1024]; int randLine; int i; srand(time(0)); f = fopen(argv[1], "r"); /* 1st pass - count the lines. */ while(!feof(f)) { fgets(line, 1024, f); nLines++; } randLine = rand() % nLines; printf("Chose %d of %d lines\n", randLine, nLines); /* 2nd pass - find the line we want. */ fseek(f, 0, SEEK_SET); for(i = 0; !feof(f) && i <= randLine; i++) fgets(line, 1024, f); printf("%s", line); }
更新:哎呀,我应该在发布之前阅读Brian R. Bondy的回答,但我有点痴迷于编写代码而没有注意到。 这几乎是相同的,除了它不存储数组中的行位置。 您可以采用任何一种方式,具体取决于文件的大小以及速度是否比保存内存更重要。
您所需要做的就是每行生成一个未缩放的随机数,同时保持您生成的所有随机数的最大值。 每当更新最大值时,都会用当前行覆盖选定的行。
最后,你得到与最高数字rand()spat out相关联的行,这在你的所有行中应该是同样可能的。
只是关于Mark Ransom避免整数溢出的方法的快速说明:DS没有FPU,因此浮点除法将在软件中模拟并且非常慢。 如果速度是一个问题,你会想要不惜一切代价避免类型转换/促销浮动或加倍。
这是一种避免整数溢出的不同方法,它避免了任何浮点数学运算:
if(rand() <= RAND_MAX / count)
由于整数除法,概率可能略有偏差,但这在DS上肯定会运行得更快。
使用Adam的随机偏移量组合到文件方法和Mark的概率方法中。 Adam的方法可以让你随机到达文件的一部分。 然后你使用Mark的方法来避免使用更大的字符串。 Mark的算法会优先选择开始的几个字符串,