ディレクトリツリーからランダムに完全に公正な方法でファイルを選択

Question

私は、個々のファイルがまったく同じ確率で選択されるような方法でディレクトリツリーからファイルをランダムに選択する方法を探しています他のすべてのファイルと同じです。

• /いくつか/親/ディレクトリ/
  • foo.jpgという
  • sub_dir/
    • ：ファイルの以下のツリーの例では、各ファイルが選択されているのは25％の確率を持っている必要があります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

すべてのファイルを1つのリスト（パスを含む）に保存して、それを選択するのはなぜですか？

Answer 3

を選択でき、すべてのファイルパスをリストに集めて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