如何从文件夹树中快速选择随机文件？

Question

[我正在尝试从文件夹树中选择一个随机文件，从固定路径开始，然后在所有子文件夹（或所选文件夹本身）中进行递归“搜索”。

我的想法是：列出文件清单，计算文件数，在此范围内选择一个随机数，然后从该索引处选取文件。

这是我的代码：

// create list of all files
std::vector<std::string> paths;

for (const auto &entry : std::filesystem::recursive_directory_iterator(mPathDirectory)) {
    if (!std::filesystem::is_directory(entry)) {
        paths.push_back(entry.path().string());
    }
}

// pick random file
size_t numberOfFiles = paths.size();
int indexRandomFile = (int)round(rescale(random::uniform(), 0.0, 1.0, 0, numberOfFiles - 1));

return paths[indexRandomFile];

[还有O3，它也相当慢，考虑到我有大量的文件列表，并且我在一个“音频”应用程序中（应该更快）。

您有更聪明的主意吗？像O（1）这样的东西？ ：P

Answer 1

可以使用reservoir sampling技术来均匀地随机选择文件。对于每个文件，请以1 / N的机会进行选择，其中N是到目前为止找到的文件数，包括刚刚找到的文件。然后，随机文件是以此方式选择的最后一个文件。

关于从文本文件中选择随机行的类似任务，另请参见this question；通常，只要事先不知道要选择的项目数，就适用储层抽样。

---

以下说明油藏取样的工作方式：

1. 将N设置为1。
2. 将ChosenFile设置为null。
3. 对于每个文件：
   • 如果为random::uniform() < 1.0 / N，则将ChosenFile设置为文件名。
   • 加1到N。

现在，ChosenFile是随机选择的文件名。

---

以您问题中的代码，这是如何实施油藏采样的方法。请注意，列表中不再存储任何文件。另请注意，此代码未经测试。

// store randomly chosen file
std::string path;
size_t n = 1;

for (const auto &entry: std::filesystem::recursive_directory_iterator(mPathDirectory)) {
    if (!std::filesystem::is_directory(entry)) {
        if (random::uniform() < 1.0 / n) {
           path = entry.path().string();
        }
        n++;
    }
}

return path;

Answer 2

如果您对文件夹结构一无所知，则必须递归到其中以找出有多少个项目。没有O（1）解决方案。

但是“应用程序”只需要快速[[感觉，即通常只有对响应性的感知才是重要的。为此，您可以采用启发式方法，例如以一定的概率将其递归到some子文件夹，直到找到a文件。它不会是统一随机的，但是会从用户的角度相对任意地选择。

与此同时，您可以

really

递归到文件夹中并建立一个cache，而最初选择的文件已经在播放。