Случайный выбор файла из дерева каталогов совершенно честным способом

Question

Я ищу способ случайного выбора файла из дерева каталогов таким образом, чтобы любой отдельный файл имел точно такую ​​же вероятность выбора, как и все другие файлы. Например, в следующем дереве файлов каждый файл должен иметь 25% вероятности выбора:

• / некоторые / родитель / реж /
  • Foo.jpg
  • sub_dir /
    • bar.jpg
    • Baz.jpg
    • another_sub /
      • qux.png

Мое временное решение, которое я использую, пока кодирую остальную часть приложения, должно иметь такую ​​функцию:

def random_file(dir):
    file = os.path.join(dir, random.choice(os.listdir(dir)));
    if os.path.isdir(file):
        return random_file(file)
    else:
        return file

Однако это, очевидно, смещает результаты в зависимости от того, где они находятся в дереве и сколько братьев и сестер находятся рядом с ними в их каталоге, поэтому они в конечном итоге имеют следующие вероятности выбора:

• / некоторые / родитель / реж /
  • Foo.jpg - 50%
  • sub_dir / (50%)
    • Bar.jpg - 16,6%
    • Baz.jpg - 16,6%
    • another_sub / (16,6%)
      • qux.png - 16,6%

Контекст для функции находится в приложении фоновой ротации, которое я пишу, поэтому возможность отфильтровывать нежелательные расширения файлов из результатов будет плюсом (хотя я мог бы просто принудительно сделать это, выбрав еще раз, если это не так тип файла, который я хочу ... который становится беспорядочным, если имеется множество файлов "неправильного" типа).

Answer 1

Вы можете выбрать все файлы с одинаковой вероятностью, только если заранее знаете общее количество файлов, поэтому сначала необходимо создать полный список:

files = [os.path.join(path, filename)
         for path, dirs, files in os.walk(dir)
         for filename in files
         if not filename.endswith(".bak")]
return random.choice(files)

Answer 2

Как уже упоминалось в других ответах, вы можете выбрать один из них в произвольном порядке, собрав все пути к файлам в список и используя random.choice. Кроме того, возможен онлайн-выбор, который не использует дополнительную память, используя больше случайных чисел. Для n предметов это либо равный выбор среди первых n-1 предметов, либо n th предмет с вероятностью 1/n. Это может быть вычислено, когда вы пробегаете список возможностей.

Вы можете перебирать все имена файлов с помощью:

def recursive_files(dir):
    for path, _, fnames in os.walk(dir):
        for fname in fnames:
            yield os.path.join(path, fname)

И сделайте выбор онлайн с этим:

import random
def online_choice(iterable):
    for n, x in enumerate(iterable, 1):
        if random.randrange(n) == 0:
            pick = x
    return pick

Answer 3

Почему бы вам просто не сохранить все файлы в одном списке (с их путями) и выбрать из этого?