¿Cuál es la mejor estructura de datos para usar al programar una grilla bidimensional de mosaicos en Java? Las fichas en la cuadrícula deben ser fácilmente referenciadas por su ubicación, de modo que los vecinos y las rutas se puedan calcular de manera eficiente. ¿Debería ser una matriz 2D? Una ArrayList? ¿Algo más?Programación de una grilla 2D en Java
Si no se preocupa demasiado por la velocidad o la memoria, puede simplemente usar una matriz 2D: esto debería funcionar bastante bien.
Si la velocidad y/o la memoria son problemas para usted, esto depende del uso de la memoria y del patrón de acceso.
Una matriz unidimensional es el camino a seguir si necesita un alto rendimiento. Calcule el índice correcto como y * wdt + x. Hay 2 posibles problemas con esto: falta de memoria caché y el uso de memoria.
Si sabe que su patrón de acceso es tal que busca vecinos de un elemento la mayor parte del tiempo, mapear un espacio 2D en una matriz 1D como se describió anteriormente puede causar fallas de caché; desea que los vecinos estén cerca memoria, y los vecinos de 2 filas diferentes no lo son. Puede que tenga que asignar sus mosaicos 2d en un orden diferente a su matriz 1d. Ver Hilbert curves por ejemplo.
Para un mejor uso de la memoria, si sabe que la mayoría de sus teselas son siempre las mismas (por ejemplo, césped), puede implementar sparse array o quad tree. Ambos pueden implementarse de manera bastante eficiente, teniendo en cuenta el conocimiento de caché (el enlace de matriz dispersa es un buen ejemplo de esto). Otro beneficio es que estos pueden ser extendidos dinámicamente. Sin embargo, siempre tendrá que pagar niveles adicionales de indirección para que esto funcione.
NOTA: Tenga cuidado con el uso de clases genéricas como HashMap s con el tipo de clave siendo un tipo primitivo o una clase de ubicación especial si le preocupa el rendimiento: tendrá que asignar un objeto cada vez que indexe el hash map o pagar el precio del boxeo/unboxing. Además de esto, los mapas hash no te permitirán consultas espaciales eficientes (por ejemplo, dame todos los objetos existentes en el radio R de un objeto dado - los árboles cuádruples son mejores para esto).
Una matriz 2D parece una buena apuesta si planeas insertar cosas en lugares específicos. Siempre y cuando sea un Tamaño fijo.
Si tiene una dimensión fija para su cuadrícula, utilice una matriz 2D. Si necesita que el tamaño sea dinámico, use una ArrayList de ArrayLists.
Si simplemente necesita iterar sobre la cuadrícula y el direccionamiento aleatorio de las celdas, MyCellType [] [] debería estar bien. Esto es más eficiente en términos de espacio y (uno esperaría) tiempo para estos casos de uso.
La estructura de datos a utilizar realmente depende del tipo de operaciones se llevará a cabo:
En caso de que el número de posiciones significativas (distinto de cero/no predeterminados) en la red es más bien baja (< < nxm) se podría ser más eficiente en el uso del espacio para usar un hashmap, que mapea las posiciones (x, y) en mosaicos específicos. También puede iterar sobre posiciones significativas mucho más eficientemente. Además, podría almacenar referencias a las fichas vecinas en cada tesela para acelerar el recorrido de la ruta/vecindario.
Si su cuadrícula está llena de "información", debería considerar utilizar una matriz 2d o ArrayList (en caso de que en algún momento tenga tipos genéricos implicados como "tipo de mosaico", debe usar ArrayLists, ya que Java no permite matrices nativas de tipo genérico).
+1 para la amplia gama de alternativas y se centran en problemas de rendimiento. –