Generación de árbol de directorios Pseudorandom?

Question

Estoy tratando de escribir un programa que se autogenerará pseudoaleatoriamente (basado en un valor inicial para que pueda volver a ejecutar la misma prueba más de una vez) una estructura de directorios creciente que consiste en archivos. (Esto es a prueba de estrés de una instalación base de datos de control de código fuente)

Me preguntaba si alguno de ustedes estaban al tanto de algo similar a la quasirandom secuencias "de compilación" (por ejemplo van der Corput sequences o Halton sequences) que podría funcionar aquí.

editar: O un algoritmo fractal. Esto suena sospechosamente como un algoritmo fractal.

---

editar 2: No importa, creo que me di cuenta de la solución obvia, se inicia con un árbol vacío, y sólo tiene que utilizar las salidas secuenciales de un generador pseudoaleatorio de forma determinista (basado en el número generado y el estado de la árbol generado hasta ahora) hacer una de N acciones, por ejemplo crear un nuevo subdirectorio, agregar un nuevo archivo, cambiar el nombre de un archivo, eliminar un archivo, etc.

Quiero hacerlo de esta forma en lugar de solo verter archivos secuencialmente en una estructura de carpetas, porque nos encontramos con una situación donde tenemos algunos problemas con grandes #s de archivos, y no estamos seguros de cuál es la causa. (profundidad de árbol, # de renombrados, # de eliminaciones, etc.)

No es solo 1 árbol fijo que necesito generar, la estrategia de uso es: hacer crecer un poco la estructura de árbol, evaluar algunas estadísticas de rendimiento, hacer crecer estructurar un árbol un poco más, evaluar algunas estadísticas de rendimiento, etc.

Answer 1

Como mencionó en su segunda edición, probablemente implementaría todo el proceso como un recorrido de árbol de archivos, con el PRNG decidiendo "cambiar a directorio", "crear directorio" , "subir un nivel", "crear archivo", "eliminar archivo" y tener otro valor para determinar qué archivo eliminar, a qué directorio cambiar y generar nombres para archivos y directorios.

I u busqué un método similar para probar la tensión en un servidor de flujo de trabajo que escribí (aunque no necesité hacer un seguimiento de dónde estaban los artículos de trabajo, solo se necesitaba seleccionar al azar uno para operar).

Answer 2

Si esto es solo para probar, ¿qué hay de malo con algún algoritmo de generación simple e ingenuo? Como, genere una cantidad aleatoria (1-10) de subdirectorios, genere nombres para ellos, luego para cada directorio recursivamente genere subdirectorios y cierta cantidad de archivos.

Esto es fácilmente personalizable y puede controlar la semilla para rand. Para necesidades más divertidas, la distribución de las cantidades de archivos/directorios puede no ser lineal, sino algo que se adapte mejor a sus necesidades.

Suena algo que se puede mejorar en media hora y terminar. No veo la necesidad de algo matemático o complejo. A menos que esto sea solo por diversión, por supuesto :-)

Answer 3

Este es un conjunto de problemas diferentes que lo hace un rompecabezas divertido.

Primero tenemos el generador de números pseudoaleatorio. Hay muchas cosas disponibles. Solo espero una función que cree un número en el rango 0..n-1.

Luego tenemos un algoritmo para determinar el número de subnodos en un solo nodo. Es tentador usar una función lineal, pero eso no es una representación justa de la realidad. Por lo tanto, puede crear la siguiente función:

randomsize() { 
    int n = Random(0,10); 
    if (n<10) return n; 

    return Random(0,9) + 10 * random; 
} 

Esta función produce números pequeños. La mayoría estará en el rango de 0..9 pero la parte superior es prácticamente infinita. Si desea tener números más grandes, también puede usar un umbral más grande

randomsize() { 
    int n = Random(0,100); 
    if (n<10) return n; 

    return Random(0,9) + 10 * random; 
} 

El último problema es cómo crear un árbol. Esto es bastante simple. Pero debes tener en cuenta que el algoritmo debe terminar.Por lo que tiene que hacer uno de los siguientes:

• uso de una profundidad máxima
• disminución del número generado basado en el nivel de anidamiento
• determinar el número de hojas en forma de porcentaje de los subnodos totales. Este porcentaje debe incrementar a niveles más altos (10-50 en el primer nivel, 20-60 en segundo .. 50-100 a quinta, 60-100 a sexta, hasta 90-100 en nineth y superior.

Ofcourse puede modificar los parámetros para crear su árbol requerido.