Thực hiện các mảng cực thưa thớt

Question

Tôi có một mảng tĩnh cực kỳ thưa thớt với 4 kích thước 8192 mỗi mà tôi muốn thực hiện tra cứu từ (C#). Chỉ 68796 trong số 4,5 * 10^15 giá trị này khác không. Cách nhanh nhất để làm điều này là gì, với tốc độ và mức sử dụng bộ nhớ thấp là quan trọng?

Cảm ơn

Answer 1

Trước tiên, tôi cho rằng các mảng đồng bằng khá rõ ràng là cấu trúc dữ liệu sai cho vấn đề của bạn.

Cách sử dụng dictionary nơi bạn sử dụng chỉ mục 4- tuple làm chỉ mục?

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

Tôi chưa bao giờ làm điều đó, nhưng nó sẽ hoạt động tốt. Nếu bạn không có Tuple sẵn sàng vì bạn đang làm việc với một phiên bản của .NET Framework trước NET 4, bạn có thể cung cấp loại chỉ số của riêng bạn:

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

Sử dụng Hashtable (từ điển chung đã được thực hiện như Hashtable). Là vector sử dụng chính của chỉ mục 4 thứ nguyên. Như giá trị lưu trữ những gì bạn muốn.

Answer 3

Bạn có thể sử dụng đơn giản Dictionary hoặc tạo một bản đồ tương tự phù hợp với nhu cầu của bạn (nó sẽ là mảng mà bạn đặt các phần tử theo giá trị băm mà bạn tính trên 4 giá trị). .

Cũng là một cây nhị phân Kết có thể làm các trick nếu bạn chấp nhận một sự phức tạp logarit cho tra cứu ..

Answer 4

Những gì tôi muốn làm là sử dụng danh sách băm thay vì mảng "bình thường" cho điều này, sau đó (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

tôi nghĩ rằng cách tốt nhất là sử dụng một bảng băm (Dictionary<T, int>), lập chỉ mục với một tuỳ chỉnh struct chứa 4 chỉ số. Đừng quên ghi đè object.Equals() và object.GetHashCode() vào số đó struct.