Implementazione di array estremamente sparsi

Question

Ho una matrice statica estremamente sparsa con 4 dimensioni di 8192 ciascuna che voglio fare ricerche da (C#). Solo 68796 di questi valori 4,5 * 10^15 sono diversi da zero. Qual è il modo più veloce per farlo, dato che la velocità e l'utilizzo di memoria ridotta sono di vitale importanza?

Grazie

Answer 1

In primo luogo, direi che gli array semplici sono abbastanza chiaramente il tipo sbagliato di struttura dati per il vostro problema.

Come utilizzare un dictionary in cui si utilizza un indice 4- tuple?

var lookup = new Dictionary<Tuple<int,int,int,int>, int>(); 

Non l'ho mai fatto, ma dovrebbe funzionare correttamente. Se non si dispone di Tuple pronto perché si sta lavorando con una versione di .NET Framework .NET precedente 4, è possibile fornire il proprio tipo di indice:

struct LookupKey 
{ 
    public readonly int First; 
    public readonly int Second; 
    public readonly int Third; 
    public readonly int Fourth; 
    … 
} 

var lookup = new Dictionary<LookupKey, int>(); 

Answer 2

Usa tabella hash (dizionario generica è già implementata come tabella hash). Come vettore chiave di utilizzo dell'indice di 4 dimensioni. Come valore memorizza ciò che vuoi.

Answer 3

È possibile utilizzare un semplice o creare una mappa simile adatta alle proprie esigenze (sarà un array in cui si posizionano gli elementi in base a un hashvalue calcolato sui 4 valori) ma sarà necessario preoccuparsi delle collisioni .

Anche un albero binario seach può fare il trucco se si accetta una complessità logaritmica per la ricerca ..

Answer 4

Quello che mi piacerebbe fare è utilizzare gli elenchi di hash invece di array "normale" per questo, allora (pseudo-codice):

// first, check bounds: 
if(x < 0 || y < 0 || z < 0 || w < 0 
|| x > xsize || y > ysize || z > zsize || w > wsize) 
    throw new Whatever(...); 

// now return value if != 0 
if(x in arr && y in arr[x] && z in arr[x][y] && w in arr[x][y][z]) 
    return arr[x][y][z][w]; 
else 
    return 0; 

Answer 5

Penso che il modo migliore è quello di utilizzare un hash-table (Dictionary<T, int>), indicizzato con un costume struct contenente i 4 indici. Non dimenticare di sovrascrivere object.Equals() e object.GetHashCode() su quello struct.