¿Acabar con los globales?

Question

Tengo un conjunto de objetos de árbol con una profundidad de unos 20 años.Cada uno de los nodos de este árbol necesita acceso a la raíz de su árbol.

Un par de soluciones:

1. Cada nodo puede almacenar una referencia a la raíz directamente (desperdicia memoria)
   • Puedo calcular la raíz en tiempo de ejecución "subiendo" (ciclos de desperdicio)
   • Puedo usar campos estáticos (pero esto equivale a globales)

¿Alguien puede proporcionar un diseño que no utilice un global (en cualquier variación) pero que sea más eficiente que el n.° 1 o el n.° 2 tanto en memoria como en ciclos respectivamente?

Editar: Como tengo un conjunto de árboles, no puedo simplemente almacenarlo de forma estática, ya que sería difícil diferenciar entre árboles.(gracias maccullt)

Answer 1

Pase la raíz como parámetro a cualquier función en el nodo que la necesite.

Editar:Las opciones son realmente las siguientes:

1. Almacenar la referencia raíz en el nodo.
2. No almacene la referencia raíz en absoluto
3. Almacenar la referencia raíz en un global
4. Almacene la referencia raíz en la pila (mi sugerencia, ya sea patrón de visitante o recursiva)

Creo que estas son todas las posibilidades, no existe la opción 5.

Answer 2

¿Por qué necesitarías acabar con los globales?Entiendo el estigma de que los globales sean malos y todo eso, pero a veces simplemente tener una estructura de datos global con todos los elementos es la solución más rápida.

Haces una compensación:claridad del código y menos problemas futuros de rendimiento.Ese es el significado de "No optimizar todavía".Dado que estás en la etapa de optimización, a veces es necesario eliminar algunas legibilidad y buenas prácticas de programación en favor del rendimiento.Quiero decir, los hacks bit a bit no son legibles pero son rápidos.

No estoy seguro de cuántos objetos de árbol tienes, pero personalmente elegiría la opción uno.A menos que esté tratando con miles de árboles, los punteros realmente no serán mucho más que unas pocas cadenas.Si la memoria es realmente un tema muy importante, pruebe ambos métodos (parecen bastante simples de implementar) y ejecútelo a través de un generador de perfiles.O usa el excelente Explorador de procesos.

Editar:Una de las aplicaciones en las que estoy trabajando tiene un árbol de nodos que contiene alrededor de 55.000 nodos.Construimos la estructura de árbol pero también mantenemos una matriz para búsquedas O(1).Mucho mejor que el O(m*n) que obtuvimos cuando usamos un método recursivo FindNodeByID.

Answer 3

Generalmente es mejor pasar la raíz como parámetro.Si está utilizando algún tipo de iterador para navegar por el árbol, una alternativa es almacenar una referencia a la raíz en él.

Answer 4

El punto 1 es una optimización prematura de la memoria.#2 es una optimización prematura del rendimiento.¿Ha creado un perfil de su aplicación para determinar si los cuellos de botella de la memoria o la CPU le están causando problemas?Si no, ¿por qué sacrificar un diseño más fácil de mantener por una "optimización" que no ayuda a los usuarios?

Te recomiendo encarecidamente que elijas el número 2.Siempre que almacena algo que podría calcular, lo que está haciendo es almacenar en caché.Hay algunas ocasiones en las que el almacenamiento en caché es una buena idea, pero también es un dolor de cabeza de mantenimiento.(Por ejemplo, ¿qué sucede si mueve un nodo de un árbol a otro cambiando su padre pero olvida actualizar también el campo raíz?) No almacene en caché si no es necesario.

Answer 5

Puede derivar una clase de TreeView y luego agregar una propiedad estática singleton.De esa manera, efectivamente está agregando un campo global que hace referencia a la instancia única de la clase, pero tiene la ventaja de que el espacio de nombres tiene como ámbito esa clase.

Answer 6

Haciendo caso omiso del disgusto por las clases internas, podría definir una clase de árbol y definir los nodos como clases internas.Cada uno de los nodos tendría acceso al estado de su árbol, incluida su raíz.

Esto podría terminar siendo el mismo que el número 1 dependiendo de cómo Java relacione los nodos con sus padres.(No estoy seguro y tendré que perfilarlo)