language agnostic - guia - ¿Qué estructuras de datos pueden almacenar eficientemente datos de "cuadrícula" 2D?

qgis español

Question

Estoy tratando de escribir una aplicación que realiza operaciones en una grilla de números, donde cada vez que una función ejecuta el valor de cada celda se cambia, y el valor de cada celda depende de sus vecinos. El valor de cada celda sería un número entero simple.

¿Cuál sería la mejor manera de almacenar mis datos aquí? He considerado tanto una lista plana como una estructura de matriz, pero parece ineficaz ya que tengo que hacer cálculos repetidamente para determinar qué celda está ''por encima'' de la celda actual (cuando hay un tamaño de cuadrícula arbitrario) y listas anidadas, lo que no ocurre Parece ser una muy buena forma de representar los datos.

No puedo evitar sentir que debe haber una mejor forma de representar estos datos en la memoria para este tipo de propósito. ¿Algunas ideas?

(Nota, no creo que esta sea realmente una pregunta subjetiva, pero el desbordamiento de pila parece pensar que es ... Estoy esperando que haya una manera aceptada de almacenar este tipo de datos)

Answer 1

Además de mi comentario, es posible que el algoritmo Hashlife sea ​​interesante.

Esencialmente (si lo entiendo correctamente), almacena sus datos en un árbol cuádruple con una tabla hash apuntando a los nodos del árbol. La idea aquí es que el mismo patrón puede aparecer más de una vez en su cuadrícula, y cada copia generará el mismo valor, por lo que solo tendrá que calcularlo una vez.

Esto es cierto para Life, que es una grilla de booleanos en su mayoría falsos. Si es cierto para su problema, no lo sé.

Answer 2

Aquí hay algunos enfoques. Voy a (intentar) ilustrar estos ejemplos con una representación de una cuadrícula de 3x3.

La matriz plana

+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+

a[row*width + column]

Para acceder a los elementos de la izquierda o la derecha, reste o agregue 1 (tenga cuidado en los límites de la fila). Para acceder a los elementos superiores o inferiores, reste o agregue el tamaño de fila (en este caso 3).

La matriz de dos dimensiones (para lenguajes como C o FORTRAN que lo soportan)

+-----+-----+-----+
| 0,0 | 0,1 | 0,2 |
+-----+-----+-----+
| 1,0 | 1,1 | 1,2 |
+-----+-----+-----+
| 2,0 | 2,1 | 2,2 |
+-----+-----+-----+

a[row,column]
a[row][column]

Acceder a elementos adyacentes es simplemente incrementar o disminuir el número de fila o columna. El compilador sigue haciendo exactamente la misma aritmética que en la matriz plana.

La matriz de matrices (por ejemplo, Java)

+---+   +---+---+---+
| 0 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 1 |-->| 0 | 1 | 2 |
+---+   +---+---+---+
| 2 |-->| 0 | 1 | 2 |
+---+   +---+---+---+

a[row][column]

En este método, una lista de "punteros de fila" (representados a la izquierda) es una nueva matriz independiente. Al igual que el conjunto de 2 d, se accede a los elementos adyacentes ajustando el índice apropiado.

Células totalmente vinculadas (lista doblemente vinculada de 2-d)

+---+   +---+   +---+
| 0 |-->| 1 |-->| 2 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 3 |-->| 4 |-->| 5 |
|   |<--|   |<--|   |
+---+   +---+   +---+
 ^ |     ^ |     ^ |
 | v     | v     | v
+---+   +---+   +---+
| 6 |-->| 7 |-->| 8 |
|   |<--|   |<--|   |
+---+   +---+   +---+

Este método tiene cada celda que contiene hasta cuatro punteros a sus elementos adyacentes. El acceso a los elementos adyacentes es a través del puntero apropiado. Deberá mantener una estructura de punteros a los elementos (probablemente usando uno de los métodos anteriores) para evitar tener que pasar secuencialmente por cada lista vinculada. Este método es un poco difícil de manejar, sin embargo, tiene una aplicación importante en el algoritmo Knuth''s Dancing Links , donde los enlaces se modifican durante la ejecución del algoritmo para omitir el espacio "en blanco" en la grilla.

Answer 3

Debe abstraerse de cómo almacena sus datos. Si necesita realizar operaciones relativas dentro de la matriz, Slice es el patrón común para hacerlo. Podrías tener algo como esto:

public interface IArray2D<T>
{
    T this[int x, int y] { get; }
}

public class Array2D<T> : IArray2D<T>
{
    readonly T[] _values;
    public readonly int Width;
    public readonly int Height;

    public Array2D(int width, int height)
    {
        Width = width;
        Height = height;
        _values = new T[width * height];
    }

    public T this[int x, int y]
    {
        get
        {
            Debug.Assert(x >= 0);
            Debug.Assert(x < Width);
            Debug.Assert(y >= 0);
            Debug.Assert(y < Height);

            return _values[y * Width + x];
        }
    }

    public Slice<T> Slice(int x0, int y0)
    {
        return new Slice<T>(this, x0, y0);
    }
}

public class Slice<T> : IArray2D<T>
{
    readonly IArray2D<T> _underlying;
    readonly int _x0;
    readonly int _y0;

    public Slice(IArray2D<T> underlying, int x0, int y0)
    {
        _underlying = underlying;
        _x0 = x0;
        _y0 = y0;
    }

    public T this[int x, int y]
    {
        get { return _underlying[_x0 + x, _y0 + y]; }
    }
}

Answer 4

Si el tiempo de búsqueda es importante para usted, una matriz bidimensional podría ser su mejor opción, ya que buscar los vecinos de una celda es una operación de tiempo constante dadas las coordenadas (x, y) de la celda.

Answer 5

Una matriz de matrices asignada dinámicamente hace que sea trivial apuntar a la celda que está sobre la celda actual y también admite tamaños de cuadrícula arbitrarios.