Eliminare i Global?

Question

Ho una serie di oggetti albero con una profondità intorno agli anni '20.Ciascuno dei nodi di questo albero necessita dell'accesso alla radice del proprio albero.

Un paio di soluzioni:

1. Ogni nodo può memorizzare direttamente un riferimento alla radice (spreca memoria)
   • Posso calcolare la radice in fase di esecuzione "salendo" (cicli di spreco)
   • Posso usare campi statici (ma questo equivale a globali)

Qualcuno può fornire un progetto che non utilizzi un globale (in qualsiasi variazione) ma sia più efficiente del n. 1 o del n. 2 rispettivamente in memoria o cicli?

Modificare: Dato che ho un insieme di alberi, non posso semplicemente memorizzarlo in modo statico poiché sarebbe difficile distinguere tra gli alberi.(grazie Maccullt)

Answer 1

Passa la radice come parametro a qualunque funzione nel nodo che ne abbia bisogno.

Modificare:Le opzioni in realtà sono le seguenti:

1. Memorizza il riferimento root nel nodo
2. Non memorizzare affatto il riferimento root
3. Memorizza il riferimento root in un file globale
4. Memorizza il riferimento root nello stack (il mio suggerimento, pattern visitatore o ricorsivo)

Penso che queste siano tutte le possibilità, non esiste l'opzione 5.

Answer 2

Perché dovresti eliminare i globali?Capisco lo stigma secondo cui i globali sono cattivi e tutto il resto, ma a volte avere semplicemente una struttura di dati globale con tutti gli elementi è la soluzione più rapida.

Fai un compromesso:chiarezza del codice e meno problemi futuri per le prestazioni.Questo è il significato di "Non ottimizzare ancora".Dato che sei nella fase di ottimizzazione, a volte è necessario eliminare un po' di leggibilità e buone pratiche di programmazione a favore delle prestazioni.Voglio dire, gli hack bit a bit non sono leggibili ma sono veloci.

Non sono sicuro di quanti oggetti albero hai, ma personalmente opterei per l'opzione uno.A meno che tu non abbia a che fare con migliaia di alberi, i puntatori in realtà non ammonteranno a molto più di poche stringhe.Se la memoria è davvero un problema estremamente importante, prova entrambi i metodi (sembrano abbastanza semplici da implementare) ed eseguilo tramite un profiler.Oppure usa l'eccellente Esplora processi.

Modificare:Una delle app su cui sto lavorando ha un albero dei nodi contenente circa 55.000 nodi.Costruiamo la struttura ad albero ma manteniamo anche un array per le ricerche O(1).Molto meglio dell'O(m*n) che ottenevamo utilizzando un metodo FindNodeByID ricorsivo.

Answer 3

Passare la radice come parametro è generalmente la cosa migliore.Se stai utilizzando una sorta di iteratore per navigare nell'albero, un'alternativa è memorizzare un riferimento a root in esso.

Answer 4

Il punto n. 1 è un'ottimizzazione prematura della memoria.#2 è un'ottimizzazione prematura delle prestazioni.Hai profilato la tua app per determinare se i colli di bottiglia della memoria o della CPU ti causano problemi?In caso contrario, perché sacrificare un design più mantenibile per una "ottimizzazione" che non aiuta i tuoi utenti?

Ti consiglio vivamente di scegliere il numero 2.Ogni volta che memorizzi qualcosa che potresti invece calcolare, quello che stai facendo è memorizzare nella cache.Ci sono alcuni casi in cui la memorizzazione nella cache è una buona idea, ma è anche un problema di manutenzione.(Ad esempio, cosa succede se sposti un nodo da un albero a un altro cambiando il suo genitore ma dimentichi di aggiornare anche il campo radice?) Non memorizzare nella cache se non è necessario.

Answer 5

Potresti derivare una classe da TreeView e quindi aggiungere una proprietà statica singleton.In questo modo stai effettivamente aggiungendo un campo globale che fa riferimento alla singola istanza della classe ma ha il vantaggio di avere come ambito lo spazio dei nomi di quella classe.

Answer 6

Ignorando il disgusto per le classi interne, potrei definire una classe Tree e definire i nodi come classi interne.Ciascuno dei nodi avrebbe accesso allo stato del proprio albero, inclusa la radice.

Questo potrebbe finire per essere lo stesso del n. 1 a seconda di come Java collega i nodi ai loro genitori.(Non ne sono sicuro e dovrò profilarlo)