Selección aleatoria de un archivo de un árbol de directorios de manera completamente equitativa

Question

Estoy buscando una manera de seleccionar aleatoriamente un archivo de un árbol de directorios de manera que cada archivo individual tenga exactamente la misma probabilidad de ser elegido como todos los otros archivos. Por ejemplo, en el siguiente árbol de archivos, cada archivo debe tener una probabilidad del 25% de ser elegido:

• /some/padre/dir/
  • foo.jpg
  • sub_dir/
    • bar.jpg
    • Baz.jpg
    • another_sub/
      • qux.png

Mi solución provisional que estoy usando mientras codificar el resto de la aplicación es tener una función de este modo:

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 

Sin embargo, esto sesga, obviamente, el resultados dependiendo de dónde están en el árbol y cuántos hermanos están al lado de ellos en su directorio para que terminen con las siguientes probabilidades de ser seleccionado:

• /some/padre/dir/
  • foo.jpg - 50%
  • sub_dir/(50%)
    • Bar.jpg - 16,6%
    • Baz.jpg - 16,6%
    • another_sub/(16,6%)
      • qux.png - 16,6%

El contexto de la función es una aplicación en la rotación de fondo que estoy escribiendo, por lo que la capacidad de filtrar las extensiones de archivos no deseados de estar en los resultados sería un bono (a pesar de que podría simplemente vigor que al elegir de nuevo si no es el tipo de archivo que quiero ... que se vuelve complicado si hay una gran cantidad de archivos del tipo "incorrecto", sin embargo).

Answer 1

Sólo se pueden seleccionar todos los archivos con la misma probabilidad si se conoce el número total de archivos de antemano, por lo que necesita para crear una lista completa primero:

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

¿Por qué no solo almacena todos los archivos en una lista (con su ruta) y elige de eso?

Answer 3

Como otras respuestas mencionadas, se puede elegir uno al azar, ya sea mediante la recopilación de todas las rutas de archivos en una lista y usando random.choice. Alternativamente, es posible realizar una selección en línea que no use memoria extra al usar más números aleatorios.Para los artículos n, es igual selección entre los primeros artículos n-1, o el n elemento con probabilidad 1/n. Esto se puede calcular al ejecutar la lista de posibilidades.

Se puede recorrer todos los nombres de archivo con:

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

Y hacer la selección en línea con esto:

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