संग्रह शुरू करते समय हैशसेट स्मृति के साथ क्या करता है?

Question

मैं निम्नलिखित समस्या पर ठोकर खाई।
मैं 1 से 100.000.000 से सभी नंबरों के साथ हैशसेट चाहता हूं।

var mySet = new HashSet<int>(); 
for (var k = 1; k <= 100000000; k++) 
    mySet.Add(k); 

कि कोड यह नहीं था के बाद से मैं स्मृति अतिप्रवाह 49mil के आसपास कहीं मिल गया: मैं निम्नलिखित कोड की कोशिश की। यह भी बहुत धीमी थी और स्मृति अत्यधिक बढ़ी।

फिर मैंने कोशिश की।

var mySet = Enumerable.Range(1, 100000000).ToHashSet(); 

जहां ToHashSet() निम्नलिखित कोड है:

public static HashSet<T> ToHashSet<T>(this IEnumerable<T> source) 
{ 
    return new HashSet<T>(source); 
} 

मैं एक स्मृति अतिप्रवाह फिर से मिल गया, लेकिन मैं पिछले कोड के साथ तो और अधिक संख्या में डाल करने में सक्षम था।

var tempList = new List<int>(); 
for (var k = 1; k <= 100000000; k++) 
    tempList.Add(k); 

var numbers = tempList.ToHashSet(); 

यह लेता है के बारे में 800ms अपने सिस्टम पर सिर्फ tempList जहां Enumerable.Range() केवल 4 टिक लेता भरने के लिए:

बात यह है कि काम करता है निम्नलिखित है!

मुझे हैशसेट की आवश्यकता है या अन्यथा इसे देखने के लिए अधिक समय लगेगा (मुझे यह ओ (1) होना चाहिए) और यह बहुत अच्छा होगा अगर मैं इसे सबसे तेज़ तरीका कर सकूं।

अब मेरा प्रश्न है:
पहले दो तरीकों से मेमोरी ओवरफ्लो क्यों होता है जहां तीसरा नहीं होता है?

क्या कुछ विशेष हैशसेट प्रारंभ करने पर स्मृति के साथ कुछ करता है?

मेरे सिस्टम में 16 जीबी मेमोरी है इसलिए मुझे अतिप्रवाह अपवाद मिलने पर मुझे आश्चर्य हुआ।

Answer 1

अन्य संग्रह प्रकारों की तरह, हैशसेट स्वचालित रूप से अपनी क्षमता को बढ़ाएगा क्योंकि आप तत्व जोड़ते हैं। बड़ी संख्या में तत्व जोड़ते समय, इसके परिणामस्वरूप बड़ी संख्या में पुनर्वितरण होंगे।

आप एक निर्माता है कि एक IEnumerable<T> लेता है के साथ प्रारंभ करते हैं, यह अगर IEnumerable<T> तथ्य एक ICollection<T> में है की जाँच करेगा, और यदि हां, संग्रह के आकार के HashSet की क्षमता आरंभ कर देगा।

यह आपके साथ हो रहा है जो तीसरा उदाहरण है - आप List<T> जोड़ रहे हैं जो ICollection<T> भी है, इसलिए आपके हैशसेट को सूची के आकार के बराबर प्रारंभिक क्षमता दी गई है, इस प्रकार यह सुनिश्चित करना कि कोई पुनर्वसन की आवश्यकता नहीं है ।

आप भी और अधिक कुशल यदि आप, List<T> निर्माता है कि एक क्षमता पैरामीटर लेता है का उपयोग के रूप में इस reallocations जब सूची निर्माण से बचने जाएगा:

var noElements = 100000000; 
var tempList = new List<int>(noElements); 
for (var k = 1; k <= noElements; k++) 
    tempList.Add(k); 

var numbers = tempList.ToHashSet(); 

आपके सिस्टम स्मृति के लिए के रूप में, जांचें कि यह 32-बिट या 64-बिट प्रक्रिया है या नहीं। 32-बिट प्रक्रिया में अधिकतम 2 जीबी मेमोरी उपलब्ध है (3 जीबी यदि आपने/3 जीबी स्टार्टअप स्विच का उपयोग किया है)।

अन्य संग्रह प्रकारों के विपरीत (उदा।List<T>, Dictionary<TKey,TValue>), HashSet<T> में कोई कन्स्ट्रक्टर नहीं है जो प्रारंभिक क्षमता निर्धारित करने के लिए capacity पैरामीटर लेता है। यदि आप बड़ी संख्या में तत्वों के साथ HashSet<T> प्रारंभ करना चाहते हैं, तो ऐसा करने का सबसे प्रभावी तरीका संभवतः पहले तत्वों को सरणी या List<T> में उपयुक्त क्षमता के साथ जोड़ना है, फिर इस सरणी को या HashSet<T> कन्स्ट्रक्टर में सूचीबद्ध करें।

Answer 2

HashSet दोगुनी बढ़ता है और आवंटन इसे उपलब्ध स्मृति से अधिक होने का कारण बनता है।

एक 64-बिट प्रणाली एक HashSet 89 लाख आइटम के ऊपर धारण कर सकते हैं पर

।

एक 32-बिट सिस्टम सीमा पर के बारे में 61.7 मिलियन आइटम है।

इसलिए आप मुझे HashSet<T> लगता है, सबसे .net संग्रह की तरह, सरणी के विकास के लिए रणनीति को दोगुना करने का उपयोग करता है और अधिक जानकारी

http://blog.mischel.com/2008/04/09/hashset-limitations/

Answer 3

के लिए स्मृति अतिप्रवाह अपवाद

हो रही है। दुर्भाग्यवश कोई कन्स्ट्रक्टर ओवरलोड नहीं है जो क्षमता लेता है।

लेकिन अगर यह ICollection<T> जांच करता है और ICollection<T>.Count के रूप में आरंभिक क्षमता का इस्तेमाल किया आप ICollection<T> कि GetEnumerator() और Count लागू करता है का एक अल्पविकसित कार्यान्वयन लागू कर सकते हैं। इस तरह आप अस्थायी List<T> को भौतिक बनाने के बिना सीधे HashSet<T> भर सकते हैं।

Answer 4

यदि आप एक हैशसेट में 100 मिलियन इंच डालते हैं जो 1.5 जीबी (मेरी मशीन) का उपभोग करेगा यदि आप एक बूल [100000000] बनाते हैं जहां आप प्रत्येक नंबर को सही करते हैं तो आपको केवल 100 एमबी लगता है और यह भी दिखता है एक हैशसेट से तेज़। यह मानता है कि 0-100000000