Ho una matrice numero intero che dovrebbe agire come un buffer:C: modo intelligente per "spostare" una matrice?
x = {{0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}};
Ora, se aggiungo una nuova riga {3, 3, 3, 3, 3}, la nuova matrice dovrebbe essere simile:
x = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}};
C'è un modo intelligente per farlo senza copiare tutti gli elementi in giro?
Come funziona il modulo?
Se si accede agli elementi come matrix[x + SZ * y] si potrebbe cambiare a:
matrix[x + SZ * ((y + FIRST_ROW) % SZ)].
In questo modo per implementare questo spostamento è sufficiente inserire la nuova riga {3, 3, 3 ..} dove era la riga {0, 0, 0} e incrementare il contatore FIRST_ROW in modo che punti alla nuova riga iniziale.
Bello, grazie! Questo posto è pieno di persone creative. :-) –
+1 in base alle specifiche aggiuntive nei commenti alla domanda originale, questa è probabilmente l'alternativa che darà le migliori prestazioni. –
Ora l'ho implementato e funziona perfettamente. Grazie ancora, e grazie ragazzi per tutte le altre risposte! –
Utilizzare un elenco collegato.
struct node
{
int row[5];
struct node *next;
};
Aggiungendo una riga è semplice come camminare l'elenco alla fine, poi sostituendo il NULL puntatore prossimo con un nuovo nodo (il cui puntatore prossimo è NULL).
Questo funziona per l'algoritmo, ma non darà risultati estremamente lenti quando si fanno effettivamente cose con la matrice? – alternative
Dipende da cosa stai facendo con esso. Se non stai estendendo la tua matrice tutto il tempo, probabilmente stai meglio assorbendo la memcpy occasionale. – nmichaels
Si noti che nella domanda la nuova riga non viene "aggiunta" alla matrice, ma sostituisce la prima riga. Quindi, se scegli la soluzione dell'elenco collegato, assicurati di annullare il tuo primo elemento nell'elenco. – ysap
È possibile incrementare x in modo che punti alla seconda riga, quindi liberare la prima riga? Ovviamente, è necessario allocare una riga alla volta e ciò non garantisce che la matrice sia contigua. Se lo richiedi, potresti allocare un grosso blocco di memoria per mantenere la matrice e poi per eliminare le parti inutilizzate quando raggiungi la fine.
Se la matrice è definita come int ** e si assegna separatamente ciascuna riga, sarà sufficiente scambiare i puntatori di riga.
Sembra buono. Ho davvero bisogno di imparare a pensare più orientato al puntatore. :) –
Unico problema è che a differenza della soluzione di lista collegata proposta altrove, qui devi pre-allocare puntatori al numero massimo di righe che avrai. Altrimenti, è un modo più efficiente della lista collegata. ** EDIT ** Ho appena notato che nella tua domanda rimani con 3 righe dopo aver aggiunto la nuova riga. Se questo è rappresentativo, allora stai bene con la risposta di @ mikerobi. Devi solo gestire i tuoi puntatori una volta che le righe vengono scambiate. – ysap
@ysap, l'operazione occasionale di O (n) per aumentare il numero di righe, sarà solitamente più efficiente di un O (n) frequente, per accedere a un valore. – mikerobi
Se si utilizza un array di puntatori agli array (anziché a un ordinario array bidimensionale), è possibile copiare solo i puntatori su righe anziché copiare tutti gli elementi.
E se stai bene con la sovrastimazione della matrice di puntatori, potresti forse aggiungere un nuovo puntatore alla fine e far avanzare il puntatore verso "l'inizio" della matrice. Ma questa non sarebbe una buona idea se si vuole potenzialmente fare questo tipo di spostamento molte volte. E ovviamente vorresti assicurarti di avere il puntatore originale da qualche parte in modo che tu possa correttamente free() le tue risorse.
Esempio di codice di scrittura lazy - è possibile utilizzare l'aritmetica modulo per indirizzare le righe. Quando si preme una nuova riga, è sufficiente aumentare una variabile di offset iniziale, aggiungere l'altezza della matrice e formare il risultato per l'altezza della matrice. In questo modo si ottiene una matrice circolare senza la necessità di copiare l'intera matrice e mantenere compatto l'array matrice.
Più risposte di seguito sono tecnicamente corrette, ma implicano tutte compromessi diversi. Puoi espandere un po 'il tuo uso previsto? Quanto saranno grandi queste matrici? Quanto spesso ti aspetti di aggiungere una riga, rispetto al numero di volte in cui accederai ai dati dalle matrici? Accederai ai singoli elementi della matrice, o verrà letto solo come un'entità intera dall'inizio alla fine? Vuoi essere in grado di liberare parti della matrice di volta in volta? Se è così, solo dalla fine, o dall'inizio, o da una riga arbitraria? –
La matrice non è grande (come 100 elementi in totale).Avrò sempre accesso all'intera matrice, la "vecchia" riga può andare via (comportamento della coda in coda), gli aggiornamenti si verificano molto spesso. –
In tal caso, l'approccio modulo proposto da @ruslik è probabilmente la soluzione migliore. Basta allocare un array in grado di gestire la dimensione massima, mantenere un puntatore alla testata corrente e avvolgere la fine dell'array quando si esaurisce la stanza. –