Quali strutture dati e algoritmi dovrei considerare per un albero radicato orientato che ha un alto tasso di abbandono?

5

Ho bisogno di rappresentare un albero radice radicato nella memoria.

Quale sarebbe una buona struttura dati e algoritmi per l'esecuzione delle azioni principali, dati i dettagli elencati di seguito?

  • Dimensione: ~ 40.000 nodi. Ma idealmente dovrebbe scalare bene fino a 10 volte la dimensione o più.

  • Arity: molto variabile. Alcuni nodi hanno 2-3 bambini. Alcuni ne hanno 10. Alcuni (più rari) hanno 1000.

  • I dati NON sono statici - durante il giorno, ~ 1-3% dei nodi / bordi saranno aggiunti / rimossi / spostati in diverse parti dell'albero (per un buon esempio di vita reale, facciamo finta che sia un albero del filesystem in cui le persone sono molto attive e ha symlink).

Ai fini della notazione:

  • D (V) - profondità del vertice (distanza dalla radice).
  • A (V) - arità del vertice (quanti bambini ha)
  • V - Dimensioni dell'albero (quanti vertici totali)

Le seguenti azioni sono necessarie (con la velocità d'azione desiderata indicata).

  • Possibilità di aggiungere un singolo vertice o una nuova sottostruttura

    O (N) dove N è la quantità di vertici che vengono aggiunti (non già nell'albero) e O (D (V)) dove V è il vertice dove sono collegati i nuovi nodi.

  • Possibilità di eliminare una sottostruttura

    O (N) dove N è la quantità di vertici eliminati e O (D (V)) dove V è il vertice da cui vengono cancellati i nuovi nodi.

  • Possibilità di spostare un sottoalbero in un altro genitore altrove nell'albero

    O (N) dove N è la quantità di vertici che vengono spostati e O (D (V)) dove V è il vertice in cui vengono spostati i nuovi nodi.

    Si noti che a causa delle esigenze di recupero descritte di seguito, NON prevedo che è possibile farlo in O (1) indipendentemente dal numero di nodi che vengono spostati, come in una normale struttura dati di base dell'albero con i puntatori del nodo figlio .

  • Possibilità di trovare un nodo con il suo nome (necessario per tutti i passaggi successivi)

    Idealmente, O (1). Molto decisamente molto meno di O (log V).

  • Possibilità di conoscere il percorso completo dal vertice alla radice

    O (1) idealmente. Ma decisamente inferiore a O (D (V)). Questo è molto importante; ed è la ragione per cui le implementazioni collegate standard dell'albero non funzioneranno, anche con collegamenti a 2 vie.

posta DVK 20.10.2014 - 17:06
fonte

2 risposte

-1

La lunga risposta è "The Art of Computer Programming, Vol. 4A: Algoritmi Combinatorial Parte 1".

La risposta più breve è, ci sono un sacco di modi diversi per farlo. Se non sei sicuro di quale rappresentazione usare, stai andando molto più avanti di te. La prima domanda è, c'è un modo per implementarlo nella lingua che stai utilizzando con cui ti trovi a tuo agio? Una volta che la parte viene inchiodata e hai un'implementazione funzionante, puoi preoccuparti se è ottimizzata.

Non vuoi affatto preoccuparti delle cose di O () a meno che tu non abbia già imparato due modi per farlo, e tu stia scegliendo tra di loro. Se vuoi imparare come analizzare le diverse rappresentazioni in anticipo e scegliere quello perfetto, devi davvero leggere il libro sopra menzionato. Ogni domanda che fai è una dozzina di pagine di densa spiegazione matematica che si basa su informazioni precedenti contenute nel libro. Devi renderlo di circa 500 pagine, e poi saprai come "generare tutti gli alberi", e puoi determinare per quale serie di alberi vuoi ottimizzare.

    
risposta data 02.01.2019 - 22:26
fonte
-3

Come hai detto è simile a un file system, perché non puoi effettivamente utilizzare il file system di Windows. Rendi ciascun nodo un file extentionless (per risparmiare memoria) e inseriscilo in cartelle. Una volta indicizzati i percorsi, Windows utilizzerà il miglior algoritmo possibile per trovare i sottoalberi (cartelle) richiesti.

Utilizzo di una tabella hash con doppio hashing con 1a funzione basata su 3-5 cifre casuali del nome e 2a basato su tutti gli altri caratteri.

    
risposta data 27.10.2014 - 15:08
fonte

Leggi altre domande sui tag