Una estructura de datos 2D óptima

Question

He pensado mucho en esto, pero realmente no he podido encontrar algo.

Supongamos que quiero am X n colección de elementos ordenables por cualquier columna y cualquier fila en O (m * n), y también la posibilidad de insertar o eliminar una fila en O (m + n) o menos .. . ¿Es posible?

Lo que he encontrado es una cuadrícula, donde los nodos se insertan en un vector, así que tengo índices para ellos, e indice la primera fila y columna para eliminar la necesidad de recorrer la lista en cualquiera dirección. con mi método logré la complejidad anterior, pero me preguntaba si es posible reducirlo aún más por un factor no constante.

Ejemplo para sortability:

1 100 25 34 
2 20 15 16 
3 165 1 27 

Ordenado por tercera fila:

25 1 34 100 
15 2 16 20 
1 3 27 165 

ordenación que por primera columna:

1 3 27 165 
15 2 16 20 
25 1 34 100 

Answer 1

Crearía dos matrices de índice, una para las columnas y otra para las filas. Así que para sus datos

1 100 25 34 
2 20 15 16 
3 165 1 27 

Se crea dos matrices:

• cols = [0, 1, 2, 3]
• rows = [0, 1, 2]

Luego, cuando se desea ordenar la matriz por la tercera fila, que mantenga el original matriz intacta, pero simplemente cambie la matriz de índices en consecuencia:

• cols = [2, 0, 3, 1]
• rows = [0, 1, 2]

El truco ahora es para acceder a su matriz con una vía indirecta. Por lo tanto, en lugar de acceder a él con m[x][y], acceda al m[cols[x]][rows[y]]. También debe usar m [cols [x]] [rows [y]] cuando realiza el reordenamiento de la matriz rows/cols.

Esta clasificación es O(n*log(n)), y el acceso es O(1).

Para la estructura de datos, me gustaría utilizar una matriz con enlaces a otra matriz:

+-+ 
|0| -> [0 1 2 3 4] 
|1| -> [0 1 2 3 4] 
|2| -> [0 1 2 3 4] 
+-+ 

Para insertar una fila, simplemente insertarlo en la última posición y actualizar la matriz del índice rows en consecuencia, con el posicion correcta. P.ej. cuando rows era [0, 1, 2] y desea insertarlo en la parte delantera, las filas se convertirán en [3, 0, 1, 2]. De esta forma, la inserción de una fila es O(n).

Para insertar una columna, también agréguela como último elemento y actualice cols en consecuencia. La inserción de una columna es O(m), la fila es O(n).

La eliminación también es O(n) o O(m), aquí simplemente reemplaza la columna/fila que desea eliminar con la última, y ​​luego elimina el índice de la matriz de índices.

Answer 2

Se puede utilizar una tabla hash e insertar (i , j) -> nodo donde (i, j) es una 2-tupla que contiene 2 enteros. Puedes escribir tu propia clase personalizada que defina el método Equals y un método GetHash() para eso ... o Python te lo da de forma gratuita.

Ahora ... ¿qué quiere decir con exactamente - ordenable por una fila o una columna? ¡Da un ejemplo con valores por favor!

Answer 3

¿Quizás creando una base de datos pequeña para ello?

Probablemente los algoritmos de clasificación de bases de datos sean mejores que reinventar la rueda. MySql haría. Para obtener rendimiento, la tabla se puede crear en la memoria. Luego puede indexar en columnas como una tabla habitual, y dejar que el motor de la base de datos haga el trabajo sucio (ordenar y tal). Y luego solo cosechas los resultados.

Answer 4

Si me entregaran este problema, crearía vectores de reasignación de filas y columnas. P.EJ. para ordenar las filas, yo determinaría el orden de las filas como siempre, pero en lugar de copiar las filas, simplemente cambiaría el vector de reasignación de filas.

Se vería algo como esto:

// These need to be set up elsewhere. 
size_t nRows, nCols; 
std::vector<T> data; 

// Remapping vectors. Initially a straight-through mapping. 
std::vector<size_t> rowMapping(nRows), colMapping(nCols); 
for(size_t y = 0; y < nRows; ++y) 
    rowMapping[y] = y; 
for(size_t x = 0; x < nCols; ++x) 
    colMapping[x] = x; 

// Then you read data(row, col) with 
T value = data[rowMapping[row] * nCols + colMapping[col]]; 

P. S. una pequeña optimización sería almacenar punteros en rowMapping en lugar de índices. Esto le permitiría hacer T value = rowMapping[row][colMapping[col]];, sin embargo, tendría que volver a calcular los punteros cada vez que cambien las dimensiones de data, lo que podría ser propenso a errores.

Answer 5

Solo para agregar a las respuestas de Martin y Mike: lo que necesitas es, en esencia, pivotar, que es lo que sugieren y una técnica muy conocida que se usa en casi cualquier algoritmo numérico que involucre matrices. Por ejemplo, puede ejecutar una búsqueda rápida de "descomposición de LU con pivoteo parcial" y "descomposición de LU con giro completo". Los vectores adicionales que almacenan las permutaciones se llaman los "pivotes".