अत्यंत स्पैर सरणी का कार्यान्वयन

Question

मेरे पास 8192 के 4 आयामों के साथ एक बेहद स्पैस स्थिर सरणी है जिसे मैं (सी #) से लुकअप करना चाहता हूं। इन 4.5 * 10^15 मानों में से केवल 68796 गैर-शून्य हैं। ऐसा करने का सबसे तेज़ तरीका क्या है, गति और कम स्मृति उपयोग महत्वपूर्ण है?

धन्यवाद

Answer 1

पहले, मैं तर्क था कि सादे सरणियों काफी स्पष्ट रूप से अपनी समस्या के लिए डेटा संरचना की गलत तरह कर रहे हैं।

dictionary का उपयोग करने के बारे में, जहां आप 4- tuple का उपयोग इंडेक्स के रूप में करते हैं?

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

मैंने कभी ऐसा नहीं किया है, लेकिन इसे ठीक काम करना चाहिए।

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

उपयोग hashtable (सामान्य शब्दकोश पहले से ही के रूप में कार्यान्वित किया जाता है: यदि आप Tuple तैयार है क्योंकि आप .नेट फ्रेमवर्क .NET 4 पूर्ववर्ती के एक संस्करण के साथ काम कर रहे हैं की जरूरत नहीं है, तो आप अपने खुद के सूचकांक प्रकार प्रदान कर सकते हैश टेबल)। 4 आयाम सूचकांक के मुख्य उपयोग वेक्टर के रूप में। वैल्यू स्टोर के रूप में आप क्या चाहते हैं।

Answer 3

आप एक सादे Dictionary का उपयोग कर सकते हैं या अपनी आवश्यकताओं के लिए उपयुक्त एक समान मानचित्र बना सकते हैं (यह एक सरणी होगी जिसमें आप अपने 4 मानों पर गणना की गई हैशवल्यू के अनुसार तत्व डालते हैं) लेकिन आपको टकराव की देखभाल करने की आवश्यकता होगी ।

इसके अलावा

एक द्विआधारी खोज के पेड़ चाल कर सकते हैं यदि आप देखने के लिए एक लघुगणकीय जटिलता को स्वीकार ..

Answer 4

मुझे क्या होता है इस बात के लिए "सामान्य" सरणियों के बजाय उपयोग हैश सूचियों, तो (छद्म कोड):

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

मुझे लगता है कि सबसे अच्छा तरीका है एक हैश तालिका (Dictionary<T, int>), एक कस्टम struct 4 अनुक्रमित युक्त साथ अनुक्रमित उपयोग करने के लिए है। उस struct पर object.Equals() और object.GetHashCode() को ओवरराइड करना न भूलें।