हैश को निर्धारित करने के लिए यह कब समझ में आता है?

Question

perldata से:

You can preallocate space for a hash by assigning to the keys() function. 
This rounds up the allocated buckets to the next power of two: 

    keys(%users) = 1000;  # allocate 1024 buckets 

वहाँ जब एक हैश presizing प्रदर्शन में सुधार होगा के लिए एक बुनियादी नियम यह है?

Answer 1

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

लेकिन यदि आपको पता है कि आपको कम से कम 1 एम आइटम की आवश्यकता होगी, तो विस्तार करने का कोई कारण नहीं है, और तालिका बढ़ने के दौरान अंतर्निहित और कभी भी डेटा संरचनाओं को विस्तारित करने की आवश्यकता है।

क्या आप इस विस्तार को नोटिस करेंगे? एह, शायद। आधुनिक मशीनें बहुत तेज हैं, यह नहीं आ सकती है। लेकिन यह ढेर विस्तार के लिए एक शानदार अवसर है, इस प्रकार एक जीसी और सभी प्रकार की चीजों का झुकाव पैदा कर रहा है। इसलिए, यदि आप जानते हैं कि आप इसका उपयोग करने जा रहे हैं, तो प्रदर्शन के कुछ और मिलनसारों को ट्विक करने के लिए यह एक "सस्ता" फिक्स है।

Answer 2

असल में यह हैश प्रदर्शन को अनुकूलित करने का दरवाजा है। हैश प्रदर्शन आपके द्वारा उपयोग किए जा रहे हैंशिंग डेटा पर और आपके द्वारा संभाले जा रहे डेटा पर भारी निर्भर करता है, इसलिए अंगूठे के नियम के साथ आने के लिए लगभग असंभव है। वैसे भी, कुछ कहा जा सकता है।

आप जानते हैं कि प्रत्येक डेटा संरचना अंतरिक्ष और समय दक्षता के बीच दी गई शेष राशि प्रदान करती है। हैश टेबल विशेष रूप से समय दक्षता के रूप में अच्छे होते हैं, जो एक आकर्षक स्थिर (0 (1)) समय की पहुंच प्रदान करते हैं।

यह तब तक सच रहता है जब तक टक्कर न हो। जब टक्कर होती है, तो पहुंच का समय टक्कर मूल्य से संबंधित बाल्टी के आकार के साथ रैखिक होता है। (अधिक जानकारी के लिए this पर एक नज़र डालें)। "धीमे" होने के अलावा, टक्कर, ज्यादातर एक्सेस टाइम गारंटी में व्यवधान है जो कि सबसे महत्वपूर्ण पहलू है जो अक्सर पहले स्थान पर हैश टेबल चुनने की ओर जाता है।

आदर्श रूप से, हैश टेबल "पूर्ण हैशिंग" के रूप में जाना जाता है (जो वास्तव में केवल तभी संभव है जब आप एल्गोरिदम को उस प्रकार के डेटा को ठीक-ठीक कर सकते हैं जिसे आप संभालेंगे), लेकिन यह इतना आसान नहीं है सामान्य मामले में प्राप्त करें (यह वास्तव में एक उदारता है)। वैसे भी, यह तथ्य की बात है कि बड़ी हैश सारणी (एक अच्छी हैशिंग एल्गोरिदम के साथ) टकराव की आवृत्ति को कम कर सकती है, और इस प्रकार स्मृति की कीमत पर प्रदर्शन में सुधार कर सकती है। छोटे हैश टेबल अधिक टकराव देखेंगे (इसलिए कम प्रदर्शन और कम गुणवत्ता वाली पहुंच समय गारंटी होगी) लेकिन कम स्मृति पर कब्जा करें।

तो, यदि आप अपना प्रोग्राम प्रोफाइल करते हैं और देखते हैं कि हैश टेबल एक्सेस एक बाधा है (किसी भी कारण से) तो आपके पास हैश स्पेस (यदि आपको देने की स्मृति है) के लिए अधिक मेमोरी आरक्षित करके इसे हल करने का मौका है।

किसी भी मामले में, मैं इस मान को यादृच्छिक रूप से नहीं बढ़ाऊंगा, लेकिन पूरी तरह से प्रोफाइलिंग के बाद ही, क्योंकि यह भी सच है कि एल्गोरिदम perl उपयोग (AFAIK) में संकलित किया गया है और इसका भी हैश प्रदर्शन पर एक बड़ा प्रभाव पड़ता है (दूसरे शब्दों में, यदि आप हैश स्पेस को बड़ा करते हैं तो भी आपको कई टकराव हो सकते हैं)।

प्रदर्शन से संबंधित चीजों के साथ सामान्य रूप से, यह उपयोगी हो सकता है या नहीं, यह आपके ठोस मामले पर निर्भर करता है।

Answer 3

मैं हैश बढ़ती पर बेंचमार्क विस्तार लागत की कोशिश की:

use Benchmark qw(cmpthese); 

# few values 
cmpthese(-4, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 17576; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
}); 

# more values 
cmpthese(-8, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 456976; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
}); 

परिणाम बड़ा अनुकूलन की तरह ध्वनि नहीं है, लेकिन ढेर विखंडन विल Hartung ने उल्लेख लाभ हो सकता है को कम करने। WinXP मशीन पर पर्ल 5.12 चल रहा है।

 Rate normal prealloc 
normal 48.3/s  --  -2% 
prealloc 49.4/s  2%  -- 
     (warning: too few iterations for a reliable count) 
    s/iter normal prealloc 
normal  3.62  --  -1% 
prealloc 3.57  1%  --