Sto cercando di trovare un modo efficace per rappresentare una griglia in qualsiasi numero di dimensioni. Vorrei essere in grado di specificare un insieme di coordinate e quindi ottenere il valore memorizzato nella posizione sulla griglia. Mi piacerebbe anche spostare facilmente qualsiasi numero di quadrati in qualsiasi dimensione facilmente. Come potrei creare una struttura di dati come questa?
Quando le dimensioni della griglia hanno valori massimi fissi, hai un semplice array multidimensionale; vale a dire int grid[10][10][10][10] per una griglia quadridimensionale. (Se la tua lingua non supporta matrici multidimensionali, puoi simularla tramite int index(int x, int y, int z, int t) { return x + (nX * y) + (nX * nY * z) + (nX * nY * nZ * t); } )
Quando il massimo delle dimensioni può aumentare (e ridursi), puoi usare elenchi annidati o un grafico; ma potrebbero non soddisfare i requisiti di rendimento.
Dici di voler rappresentare la 'griglia', ma ovviamente hai bisogno di farlo.
Se definisci il tuo oggetto "punto" con il numero di dimensioni richiesto:
Class Point
{
int x;
int y;
int z;
....
}
Quindi in sostanza hai definito la 'griglia' in cui esistono senza la necessità di un datastucture per la griglia stessa.
Cercare un punto in una posizione è semplicemente una questione di memorizzare i tuoi punti in un elenco o hashmap opportunamente indicizzati.
Spostarlo è semplicemente questione di cambiare le sue coordinate.
Potrebbe essere meglio chiamato una matrice o array multidimensionale.
Si dovrebbe notare che, in generale, tali matrici multidimensionali contengono molti elementi. Ad esempio, una serie di dimensioni 10 20 30 contiene 10 * 20 * 30 che è 6000 elementi, ed è considerata piccola (poiché 10, 20 e 30 sono piccoli). Ma una serie di dimensioni 8 8 8 8 8 8 8 8 8 8 (dieci occorrenze di 8) ha 2 30 elementi (se ogni elemento era un 32 bit int cioè 4 byte, che richiede 4Gbyte di RAM) e ciascuna dimensione individuale è 8, un numero piuttosto piccolo.
Per prima cosa devi stimare la quantità di elementi da conservare . Potrebbe essere abbastanza grande da non adattarsi al tuo computer (quindi il tuo problema è praticamente irrisolvibile, o non rintracciabile, e dovresti cambiare completamente il tuo approccio o ottenere un computer molto più grande). Leggi la la tesi di Cobham e esplosione combinatoria . Se vuoi mantenere tutti gli elementi avrai bisogno di una matrice multidimensionale, come risposta di Kasper van den Berg .
A volte sai che la griglia o la matrice è sparse (la maggior parte degli elementi sono 0) o che ha qualche altra proprietà (ad es. è simmetrica , anti-simmetrico , triangolare ). Quindi devi specificare le sue proprietà nella domanda (quindi in generale devi chiediti: quali sono le proprietà che conosco di una griglia simile? come posso lo caratterizzi? ).
Gli array sparsi potrebbero essere rappresentati da tabelle hash o mappe (mappatura di tuple di indice su elementi diversi da zero).
Leggi anche i grafici e amp; hypergraphs & relazioni (e forse anche motori di inferenza ). Forse potrebbero essere più adatti al tuo problema concreto (che hai dimenticato di menzionare)
Il blog di J.Pitrat ha alcuni spunti interessanti, in particolare: È possibile definire un problema?
@Basile La risposta di Starynkevitch è ottima, ma sfiora un po 'le matrici dense. Loro possono essere rappresentati come matrici unidimensionali nel codice.
Dicendo che hai qualcosa come un cuboide n-dimensiona. Con dire, quattro dimensioni, si potrebbe fare qualcosa di simile:
x1 + side1 * x2 + side1 * side2 * x3 + side1 * side2 * side3 * x4
Dove side1..side3 sono i lati della matrice e x1..x4 sono coordinate. Potrebbe esserci un bug da qualche parte, ma tu hai l'idea.
Anche se richiede molta memoria. Supponiamo che la matrice 1000x1000x1000x1000 di galleggianti a precisione singola sia 4 TB (decimale tera, non tebi)!
Leggi altre domande sui tag data-structures