Generazione di alberi di directory pseudocasuali?

Question

Sto provando a scrivere un programma che si autogenererà in modo pseudocasuale (basato su un valore di inizializzazione in modo da poter rieseguire lo stesso test più di una volta) una struttura di directory crescente costituita da file. (Questo è quello di stress test un'installazione database di controllo del codice sorgente)

Mi chiedevo se qualcuno di voi erano a conoscenza di qualcosa di simile al quasirandom "che riempiono lo spazio" sequenze (ad esempio van der Corput sequences o Halton sequences) che potrebbe funzionare qui.

modifica: o un algoritmo frattale. Questo suona sospettosamente come un algoritmo frattale.

---

modifica 2: Non importa, penso capito la soluzione ovvia, inizia con un albero vuoto, e solo uso uscite sequenziali di un generatore pseudocasuale di deterministico (in base al numero generato e lo stato della albero generato finora) fai una delle azioni N, ad es creare una nuova sottodirectory, aggiungere un nuovo file, rinominare un file, eliminare un file, ecc.

Voglio farlo in questo modo piuttosto che semplicemente scaricare i file in sequenza in una struttura di cartelle, perché ci stiamo imbattendo in una situazione dove stiamo avendo alcuni problemi con grandi # di file, e non siamo sicuri esattamente quale sia la causa. (profondità albero, numero di nomi, numero cancellazioni, ecc.)

Non è solo un albero fisso che devo generare, la strategia di utilizzo è: far crescere un po 'la struttura ad albero, valutare alcune statistiche sul rendimento, far crescere il struttura ad albero un po 'di più, valutare alcune statistiche sulle prestazioni, ecc.

Answer 1

Come si menziona nella seconda modifica, probabilmente implementerò l'intera operazione come un attraversamento di file, con il PRNG che decide "cambia in directory", "crea directory" , "sposta su un livello", "crea file", "elimina file" e ha un altro valore per determinare quale file eliminare, quale directory modificare e generare nomi per file e directory

I u Ho usato un metodo simile per testare lo stress su un server del flusso di lavoro che ho scritto (anche se non avevo bisogno di tenere traccia di dove erano gli oggetti di lavoro, ma solo di averne scelto a caso uno su cui operare).

Answer 2

Se questo è solo per test, cosa c'è di sbagliato in un semplice, ingenuo algoritmo di generazione? Come, generare una quantità casuale (1-10) di sottodirectory, generare nomi per loro, quindi per ogni directory generare ricorsivamente sottodirectory e una certa quantità di file.

Questo è facilmente personalizzabile ed è possibile controllare il seme per rand. Per le esigenze del funkier, la distribuzione delle quantità di file/directory può essere non lineare, ma qualcosa che si adatta meglio alle tue esigenze.

Suona qualcosa che può essere montato in mezz'ora e finito. Non riesco a vedere il bisogno di qualcosa di matematico o complesso. A meno che non sia solo per divertimento, ovviamente :-)

Answer 3

Questo è un insieme di problemi diversi che lo rende un puzzle divertente.

Per prima cosa abbiamo il generatore di numeri pseudocasuali. C'è un sacco di cose disponibili. Mi aspetto solo una funzione che crei un numero nell'intervallo 0..n-1.

Quindi abbiamo un algoritmo per determinare il numero di sottonodi su un singolo nodo. È allettante usare una funzione lineare ma non è una rappresentazione equa della realtà. Quindi è possibile creare la seguente funzione:

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

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

Questa funzione produce numeri piccoli. La maggior parte sarà nella gamma 0..9 ma la cima è praticamente infinita. Se vuoi avere numeri più grandi puoi anche usare una soglia più grande

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

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

L'ultimo problema è come creare un albero. Questo è piuttosto semplice. Ma dovresti tenere a mente che l'algoritmo deve finire.Quindi è necessario effettuare una delle seguenti operazioni:

• uso una profondità massima
• decremento del numero generato in base al livello di nidificazione
• determinare il numero di foglie in percentuale del totale dei sottonodi. Questa percentuale dovrebbe aumentare a livelli più alti (10-50 al primo livello, 20-60 in seconda .. 50-100 in quinta, 60-100 al sesto, fino a 90-100 nono e più alto.

Naturalmente è possibile modificare i parametri per creare l'albero richiesto