Construya un árbol a partir de las rutas del archivo de la lista (Python) – Depende del rendimiento

Hola, estoy trabajando en un kit de herramientas de gestión / análisis de archivos de muy alto rendimiento escrito en Python. Quiero crear una función que me dé una lista o algo así en un formato de árbol. Algo así como en esta pregunta (relacionado con java)

Desde:

dir/file dir/dir2/file2 dir/file3 dir3/file4 dir3/file5 

Nota: la lista de rutas es sin clasificar

A:

 dir/ file dir2/ file2 file3 dir3/ file4 file5 [[dir, [file, [dir2, [file2]], file3]], [dir3, [file4, file5]]] 

algo en ese sentido. He estado jugando con algunas ideas pero ninguna me proporcionó la velocidad que me gustaría tener.

Nota: Ya tengo la lista de rutas, así que no te preocupes por eso. La función toma la lista de rutas y da una lista de árbol.

Gracias por adelantado

Ahora que aclaró un poco más la pregunta, creo que lo siguiente es lo que desea:

 from collections import defaultdict input_ = '''dir/file dir/dir2/file2 dir/file3 dir2/alpha/beta/gamma/delta dir2/alpha/beta/gamma/delta/ dir3/file4 dir3/file5''' FILE_MARKER = '' def attach(branch, trunk): ''' Insert a branch of directories on its trunk. ''' parts = branch.split('/', 1) if len(parts) == 1: # branch is a file trunk[FILE_MARKER].append(parts[0]) else: node, others = parts if node not in trunk: trunk[node] = defaultdict(dict, ((FILE_MARKER, []),)) attach(others, trunk[node]) def prettify(d, indent=0): ''' Print the file tree structure with proper indentation. ''' for key, value in d.iteritems(): if key == FILE_MARKER: if value: print ' ' * indent + str(value) else: print ' ' * indent + str(key) if isinstance(value, dict): prettify(value, indent+1) else: print ' ' * (indent+1) + str(value) main_dict = defaultdict(dict, ((FILE_MARKER, []),)) for line in input_.split('\n'): attach(line, main_dict) prettify(main_dict) 

Produce:

 dir3 ['file4', 'file5'] dir2 alpha beta gamma ['delta'] delta [''] dir dir2 ['file2'] ['file', 'file3'] 

Algunas cosas a tener en cuenta:

  • El script hace un uso intensivo de defaultdicts , básicamente, esto permite omitir la verificación de la existencia de una clave y su inicialización si no está allí.
  • Los nombres de los directorios se asignan a las claves del diccionario. Pensé que esta podría ser una buena característica para usted, ya que las claves están en hash y usted podrá recuperar información mucho más rápido de esta manera que con las listas. Puede acceder a la jerarquía en la forma main_dict['dir2']['alpha']['beta']
  • Note la diferencia entre .../delta y .../delta/ . Pensé que esto era útil para que pudieras diferenciar rápidamente si tu hoja es un directorio o un archivo.

Espero que esto responda tu pregunta. Si algo no está claro, publica un comentario.

No tengo claro lo que tiene frente a lo que necesita (probablemente ayudaría a proporcionar parte del código que tiene que es demasiado lento), pero probablemente debería simplemente dividir sus nombres de ruta en nombres y nombres de base, y luego construir una árbol a partir de eso, utilizando una clase específica, o al menos una jerarquía de listas o diccionarios. Luego, varios recorridos deberían permitirle serializar en casi cualquier forma que requiera.

En cuanto a los problemas de rendimiento, ¿has considerado usar Pypy, Cython o Shedskin? Tengo un sistema de copia de seguridad con deduplicación en el que he estado trabajando por diversión, que puede ejecutar el mismo código en Pypy o Cython; ejecutarlo en Pypy en realidad supera a la versión aumentada con Cython (mucho en 32 bits, un poco en 64 bits). También me encantaría comparar la piel de gallo, pero aparentemente no puede ceder a través del límite de piel de caca / cpython.

Además, el perfil es de rigor cuando tiene problemas de rendimiento, al menos, si ya ha seleccionado un algoritmo adecuado.

En primer lugar, “el rendimiento muy alto” y “Python” no se mezclan bien . Si lo que busca es optimizar el rendimiento al máximo, cambiar a C le traerá beneficios muy superiores a cualquier optimización de código inteligente que pueda imaginar.

En segundo lugar, es difícil creer que el cuello de botella en un “conjunto de herramientas de análisis / gestión de archivos” sea ​​esta función . Las operaciones de E / S en el disco son al menos un orden de magnitud más lentas que cualquier cosa que suceda en la memoria. Perfilar su código es la única forma precisa de medir esto, pero … ¡Estoy listo para pagarle una pizza si me equivoco! 😉

Construí una función de prueba tonta solo para realizar una medición preliminar:

 from timeit import Timer as T PLIST = [['dir', ['file', ['dir2', ['file2']], 'file3']], ['dir3', ['file4', 'file5', 'file6', 'file7']]] def tree(plist, indent=0): level = [] for el in plist: if isinstance(el, list): level.extend(tree(el, indent + 2)) else: level.append(' ' * indent + el) return level print T(lambda : tree(PLIST)).repeat(number=100000) 

Esto produce:

 [1.0135619640350342, 1.0107290744781494, 1.0090651512145996] 

Dado que la lista de rutas de prueba es de 10 archivos, y el número de iteraciones es de 100000, esto significa que en 1 segundo puede procesar un árbol de aproximadamente 1 millón de archivos. Ahora … a menos que esté trabajando en Google, eso me parece un resultado aceptable.

Por el contrario, cuando comencé a escribir esta respuesta, hice clic en la opción “propiedad” en la raíz de mi HD principal de 80Gb [esto debería darme la cantidad de archivos que contiene, usando el código C]. Faltan unos minutos y estoy en torno a 50 GB, 300000 archivos …

HTH! 🙂