Как быстро выбрать случайный файл из дерева папок?

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

Подобным образом произвольно выбирая файл таким образом, можно сделать, используя метод отбор проб из резервуара . Для каждого файла выберите его с вероятностью 1 / N, где N - это количество найденных вами файлов, включая только что найденный файл. Случайный файл является последним файлом, выбранным таким образом.

См. Также этот вопрос для аналогичной задачи выбора случайной строки из текстового файла;Отбор проб резервуара применяется, как правило, всякий раз, когда количество элементов для выбора заранее неизвестно.

---

Ниже объясняется, как работает отбор проб резервуара:

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

Если вы ничего не знаете о структуре папок, вы должны заглянуть в нее, чтобы узнать, сколько там элементов. О (1) решения не существует.

Но «приложению» нужно только чувствовать быстро, т. Е. Часто имеет значение только восприятие реакции. Для этого при первом запуске вы можете использовать эвристику, например, рекурсивную обработку в некоторых подпапках с определенной вероятностью, пока не найдете файл a . Он не будет равномерно случайным, но он будет относительно произвольно выбран с точки зрения пользователя.

Между тем вы можете действительно рекурсировать в папки и создавать кеш , пока изначально выбранный файл уже воспроизводится.