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

Question

我想找一种方法，从一棵文件夹树中随机选择一个文件，并且每个文件被选中的概率都要一样。比如在下面这个文件树中，每个文件被选中的概率应该都是25%：

• /some/parent/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

不过，这样明显会影响结果，因为文件在树中的位置和同级文件的数量会导致它们被选中的概率不同，结果如下：

• /some/parent/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

你为什么不把所有的文件都放在一个列表里（连同它们的路径），然后从中选择呢？

Answer 2

正如其他回答提到的，你可以随机选择一个文件，方法是把所有文件路径放到一个列表里，然后用 random.choice 来选择。还有一种方法是在线选择，这种方法不需要额外的内存，使用更多的随机数就可以了。对于 n 个项目，你可以在前 n-1 个项目中均匀选择，或者以 1/n 的概率选择第 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

如果你想以相同的概率选择所有文件，前提是你得提前知道文件的总数。所以，你需要先创建一个完整的文件列表：

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)