जावा का ट्रीमैप प्रारंभिक आकार की अनुमति क्यों नहीं देता है?

Question

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

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

Answer 1

HashMap के विपरीत जो अपने आंतरिक को दोबारा डालने के रूप में आवंटित करता है, TreeMap आम तौर पर नए जोड़ने पर अपने नोड्स को पुन: आवंटित नहीं करता है। अंतर को बहुत कम रूप से सचित्र किया जा सकता है क्योंकि ArrayList और LinkedList के बीच: पहला पुन: आवंटन आकार बदलने के लिए, जबकि दूसरा नहीं है। यही कारण है कि TreeMap का प्रारंभिक आकार सेट करना लगभग LinkedList के आरंभिक आकार को सेट करने की कोशिश के रूप में लगभग अर्थहीन है।

गति अंतर दो कंटेनरों के विभिन्न समय जटिलता की वजह से है: एक HashMap में N नोड्स डालने, O(n) है, जबकि TreeMap के लिए यह, O(N*LogN) है जो 1000000 नोड्स के लिए मोटे तौर पर 20 बार asymptotic अंतर है। यद्यपि एसिम्प्टोटिक जटिलता में अंतर अलग-अलग एल्गोरिदम द्वारा निर्धारित विभिन्न स्थिरांकों के कारण सीधे समय के अंतर में अनुवाद नहीं करता है, यह तय करने का एक अच्छा तरीका है कि बहुत बड़े इनपुट पर कौन सा एल्गोरिदम तेजी से चल रहा है।

Answer 2

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

एक हैशमैप में आपके द्वारा संग्रहीत चीजों के लिए एक खाली-स्थान की खाली जगह की आवश्यकता होती है। मेरे प्रोफेसर ने हमेशा मुझे बताया है कि ऑब्जेक्ट या जो भी आप उस हैशपैप में संग्रहीत कर रहे हैं, उस स्थान की 5 गुणा की आवश्यकता है। तो हैशमैप की प्रारंभिक रचना से आकार निर्दिष्ट करने से आपके हैशपैप की गति में सुधार होता है। अन्यथा, यदि आपके पास योजना बनाने की तुलना में हैशपैप में जाने वाली अधिक वस्तुएं हैं, तो हैशैप को "आकार देना" है।

(वर्तनी के लिए संपादित)

Answer 3

मुझे लगता है गलत हूँ एक ट्री-मैप की सरणी के प्रारंभिक आकार सेट करने के लिए सक्षम होना चाहिए?

हां। TreeMap में कोई सरणी नहीं है। एक TreeMap 2 बच्चों के साथ बाइनरी नोड्स का उपयोग करता है।

यदि आप सुझाव दे रहे हैं कि पेड़ नोड में बच्चों की संख्या पैरामीटर होनी चाहिए, तो आपको यह पता लगाना होगा कि खोज समय पर इसका प्रभाव कैसा है। और मुझे लगता है कि यह O(log2N) से O(log2M * log2(N/M)) पर खोज समय बदलता है जहां N संख्या तत्व हैं और M नोड बच्चों की औसत संख्या है। (और मैं कुछ आशावादी धारणाएं कर रहा हूं ...) यह "जीत" नहीं है।

क्या कोई अलग कारण है कि यह इतना धीमा है?

हां। कारण यह है कि एक (बड़े) TreeMap इष्टतम परिस्थितियों में एक (बड़े) HashMap के सापेक्ष धीमी है, यह है कि एक संतुलित बाइनरी पेड़ का उपयोग करके लुकअप को log2N पेड़ नोड्स को देखने की आवश्यकता होती है। कॉन्सस्ट्रा द्वारा, इष्टतम HashMap (अच्छा लोड कारक और कोई टकराव हॉटस्पॉट) में एक लुकअप में 1 हैशकोड गणना शामिल है और O(1) हैशचेन नोड्स को देख रहा है।

नोट्स:

1. TreeMap एक द्विआधारी पेड़ संगठन है कि संतुलित पेड़ देता है का उपयोग करता है, तो O(log2N) सबसे खराब स्थिति समय देखने है।
2. HashMap प्रदर्शन हैश फ़ंक्शन और कुंजी स्थान की टक्कर दर पर निर्भर करता है। सबसे बुरे मामले में जहां सभी चाबियाँ एक ही हैश श्रृंखला पर समाप्त होती हैं, HashMap में O(N) लुकअप है।

Answer 4

क्या मुझे लगता है कि ट्रीएप के सरणी के शुरुआती आकार को सेट करने में सक्षम होना चाहिए?

हां। यह एक सरणी नहीं है। इसमें एक पेड़ है