Tengo una matriz de enteros que debe actuar como un amortiguador:C: forma inteligente de "cambiar" una matriz?
x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};
Ahora si añado una nueva fila {3, 3, 3, 3, 3}, la nueva matriz debe ser similar:
x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};
¿Hay una forma inteligente de hacerlo sin copiar todos los elementos?
¿Qué tal el funcionamiento del módulo?
Si accede a los elementos como matrix[x + SZ * y] usted podría cambiar a:
matrix[x + SZ * ((y + FIRST_ROW) % SZ)].
De esta forma, para implementar este cambio, simplemente coloque la nueva línea {3, 3, 3 ..} donde estaba la línea {0, 0, 0} e incremente el contador FIRST_ROW para apuntar a la nueva fila inicial.
¡Agradable, gracias! Este lugar está lleno de personas creativas. :-) –
+1 según la especificación adicional en los comentarios a la pregunta original, esta es probablemente la alternativa que proporcionará el mejor rendimiento. –
Ahora lo implementé y funciona bien. Gracias de nuevo, y gracias chicos por todas las otras respuestas! –
Utilice una lista vinculada.
struct node
{
int row[5];
struct node *next;
};
Al añadir una fila es tan simple como caminar la lista al final, a continuación, la sustitución de la NULL siguiente puntero con un nuevo nodo (cuyo siguiente puntero es NULL).
Esto funciona para el algoritmo, pero ¿no dará resultados extremadamente lentos cuando realmente haces cosas con la matriz? – alternative
Eso depende de lo que esté haciendo con él. Si no extiendes tu matriz todo el tiempo, probablemente es mejor que tomes la memcpy ocasional. – nmichaels
Tenga en cuenta que en la pregunta, la nueva fila no se "agrega" a la matriz, sino que reemplaza a la 1ra fila. Por lo tanto, si elige la solución de lista vinculada, asegúrese de anular su primer elemento en la lista. – ysap
¿Se puede incrementar x para que apunte a la segunda fila y luego liberar la primera fila? Obviamente, necesitaría asignar una fila a la vez y esto no garantizaría que la matriz sea contigua. Si lo necesita, puede asignar un gran bloque de memoria para mantener su matriz y luego golpear las partes no utilizadas cuando llegue al final.
Si su matriz está definida como int ** y asigna cada fila por separado, entonces solo tendrá que intercambiar los punteros de fila.
Eso suena bien. Realmente necesito aprender a pensar más orientado a punteros. :) –
El único problema es que, a diferencia de la solución de lista vinculada propuesta en otro lugar, aquí tiene que asignar previamente los punteros al número máximo de filas que tendrá. De lo contrario, es una forma más eficiente que la lista vinculada. ** EDITAR ** Me acabo de dar cuenta de que en tu pregunta te quedas con 3 filas después de agregar la nueva fila. Si esto es representativo, entonces estás bien con la respuesta de @mikerobi. Solo necesita administrar sus punteros una vez que las filas se intercambian. – ysap
@ysap, la operación O (n) ocasional para aumentar el número de filas, generalmente será más eficiente que un O (n) frecuente, para acceder a un valor. – mikerobi
Si utiliza una matriz de punteros a matrices (en lugar de una matriz bidimensional ordinaria), puede copiar solo los punteros a filas en lugar de copiar todos los elementos.
Y si está de acuerdo con la sobreasignación de la matriz de punteros, podría agregar un puntero nuevo al final y avanzar el puntero al "inicio" de la matriz. Pero esto no sería una buena idea si potencialmente desea hacer este tipo de cambio muchas veces. Y, por supuesto, querrá asegurarse de tener el puntero original en algún lugar para poder free() correctamente sus recursos.
Ejemplo de código de escritura lenta: puede usar aritmética de módulo para direccionar las filas. Al presionar una nueva fila, simplemente aumente una variable de desplazamiento inicial, agregue la altura de la matriz y modifique el resultado por la altura de la matriz. De esta forma obtienes una matriz circular sin necesidad de copiar toda la matriz y mantener compacta la matriz matriz.
Las respuestas múltiples a continuación son técnicamente correctas, pero todas implican diferentes compensaciones. ¿Puedes expandir un poco tu uso esperado? ¿Qué tan grandes serán estas matrices? ¿Con qué frecuencia esperas agregar una fila, en comparación con la cantidad de veces que accederás a los datos de las matrices? ¿Tendrás acceso a elementos individuales de la matriz, o solo se leerá como una entidad completa de principio a fin? ¿Desea poder liberar partes de la matriz de vez en cuando? Si es así, ¿solo desde el final, o desde el principio, o desde una fila arbitraria? –
La matriz no es grande (como 100 elementos en total).Siempre accederé a toda la matriz, la fila "vieja" puede desaparecer (comportamiento de fifo-queue), las actualizaciones ocurren muy a menudo. –
En ese caso, el enfoque de módulo propuesto por @ruslik es probablemente la mejor opción. Simplemente asigne una matriz que pueda manejar el tamaño máximo, mantenga un puntero al encabezado actual y envuelva el final de la matriz cuando se quede sin espacio. –