Implementacja bardzo rzadkich macierzy

Question

Mam bardzo rzadką statyczną tablicę z 4 wymiarami po 8192, z których chcę zrobić odnośniki (C#). Tylko 68796 z tych 4,5 * 10^15 wartości są niezerowe. Jaki jest najszybszy sposób, aby to zrobić, mając na uwadze szybkość i niskie zużycie pamięci?

Dzięki

Answer 1

Po pierwsze, chciałbym twierdzą, że zwykłe tablice są dość wyraźnie zły rodzaj struktury danych dla Twojego problemu.

Co powiesz na używanie numeru dictionary, w którym jako indeks używany jest numer 4- tuple?

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

Ja sam nigdy tego nie robiłem, ale powinno działać dobrze. Jeśli nie masz Tuple gotowy, ponieważ pracujemy z wersji .NET Framework poprzedzającego 4, można podać swój własny typ indeksu:

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

Użyj hashtable (ogólne słownik jest już zaimplementowany jako Hashtable). Jako kluczowy wektor użytkowy 4-wymiarowego indeksu. Jako wartość przechowuj to, co chcesz.

Answer 3

Możesz użyć zwykłego Dictionary lub utworzyć podobną mapę dostosowaną do twoich potrzeb (będzie to tablica, w której umieszczasz elementy zgodnie z wartością haszową, którą obliczysz na swoich 4 wartościach), ale musisz zadbać o kolizje .

również binarne drzewo wyszukiwanego można zrobić trick jeśli przyjąć złożoność logarytmiczną dla odnośnika ..

Answer 4

Co zrobiłbym to użyć hash list zamiast „normalnych” tablic do tego, to (pseudo-code):

// 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

Myślę, że najlepszym sposobem jest użycie hash-table (Dictionary<T, int>), indeksowane ze zwyczajem struct zawierającego 4 indeksów. Nie zapomnij zastąpić object.Equals() i object.GetHashCode() tym numerem struct.