以完全公平的方式从目录树中随机选择文件

Question

我正在寻找一种从目录树中随机选择文件的方法,使得任何单个文件与所有其他文件具有完全相同的概率.例如,在以下文件树中,每个文件应有25%的可能性被选中:

• /一些/父母/ DIR /
  • 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

然而,这显然会使结果产生偏差,这取决于它们在树中的位置以及目录中有多少兄弟姐妹,因此它们最终会被选中以下概率:

• /一些/父母/ DIR /
  • 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概率为 的第 1 个项目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