2017-07-21 17 views
5

मैं एड्रियान ग्रैंड के talk on Lucene's index architecture देख रहा था और एक बिंदु वह बनाता है कि ल्यूसीन अपने उलटा सूचकांक के शब्दकोश भाग का प्रतिनिधित्व करने के लिए क्रमबद्ध सरणी का उपयोग करता है। हैश टेबल ("क्लासिक" उलटा इंडेक्स डेटा स्ट्रक्चर) के बजाय क्रमबद्ध सरणी का उपयोग करने के पीछे तर्क क्या है?ल्यूसीन अपनी उलटा इंडेक्स के लिए हैश टेबल की बजाय सरणी का उपयोग क्यों करता है?

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

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

तो क्या हो रहा है? ल्यूसीन देवों के पास सरणी का उपयोग करने के लिए बहुत अच्छा कारण होना चाहिए। क्या स्केलेबिलिटी के साथ कुछ करना है? डिस्क पढ़ने की गति? कुछ और पूरी तरह से?

+1

उत्कृष्ट प्रश्न! – Eugene

+1

कई कारणों से ल्यूसीन हैश टेबल का उपयोग नहीं करता है इस जवाब में @Ivan द्वारा प्रदान किया गया है: https://stackoverflow.com/a/48053519/1697566 –

उत्तर

2

ठीक है, मैं अनुमानित अनुमान लगा सकता हूं (शायद एक टिप्पणी होनी चाहिए - लेकिन यह बहुत लंबा होने वाला है)।

  1. HashMap सामान्य एक तेजी से लुक-अप संरचना खोज समय O(1) है कि में है - जिसका अर्थ यह निरंतर है। लेकिन यह औसत मामला है; चूंकि (कम से कम जावा में) HashMapTreeNodes का उपयोग करता है - खोज उस बाल्टी के अंदर O(logn) है। यहां तक ​​कि यदि हम मानते हैं कि उनकी खोज जटिलता O(1) है, तो इसका मतलब यह नहीं है कि यह समान समय के अनुसार है। इसका मतलब यह है कि यह प्रत्येक अलग डेटा संरचना के लिए स्थिर है।

  2. मेमोरी वास्तव में - मैं एक उदाहरण here दूंगा। संक्षेप में 15_000_000 प्रविष्टियों में रैम के 1GB से थोड़ा अधिक आवश्यकता होगी; सॉर्ट किए गए सरणी शायद अधिक कॉम्पैक्ट हैं, खासकर जब से वे ऑब्जेक्ट्स के बजाए प्राइमेटिव्स रख सकते हैं। एक HashMap (आमतौर पर) में

  3. लाना प्रविष्टियों सभी कुंजी फिर से टुकड़ों में बंटी है कि एक महत्वपूर्ण प्रदर्शन हिट हो सकता है, क्योंकि वे सभी संभावित विभिन्न स्थानों पर ले जाने के लिए है की आवश्यकता है।

  4. शायद यहां एक अतिरिक्त बिंदु - श्रेणियों में खोजें, जिसके लिए कुछ TreeMap की आवश्यकता होगी, wheres arrays यहां अधिक उपयुक्त हैं। मैं एक सूचकांक विभाजन के बारे में सोच रहा हूं (हो सकता है कि वे इसे आंतरिक रूप से करें)।

  5. मेरे पास आपके जैसा ही विचार है - सरणी आमतौर पर संगत स्मृति होती है, शायद सीपीयू द्वारा पूर्व-प्राप्त होने के लिए बहुत आसान है।

  6. और अंतिम बिंदु: मुझे अपने जूते में डाल दिया, मैं पहले HashMap से शुरू करूंगा ... मुझे यकीन है कि उनके निर्णय के लिए अनिवार्य कारण हैं। मुझे आश्चर्य है कि क्या उनके पास वास्तविक परीक्षण हैं जो इस विकल्प को साबित करते हैं।

+0

उत्तर के लिए धन्यवाद!मुझे लगता है कि यह इस तथ्य से भी हो सकता है कि ल्यूसीन को केवल पाठ्य शर्तों से अधिक सामान्यीकृत करना है, और मनमानी शब्दों को हड़ताली करना काफी हिट हो सकता है। लेकिन मैं देखूंगा कि मैं थोड़ा प्रयोग कर सकता हूं यह देखने के लिए कि 'हैश मैप' और सरणी टेक्स्ट इंडेक्सिंग के लिए कैसे तुलना करते हैं। – CoconutFred

+0

अपने सेटअप की अपरिवर्तनीयता को न भूलें। –

+0

@ एंथनी डीमेलेमेस्टर मुझे पता नहीं है कि कैसे ल्यूसीन सेट अप है, शून्य ज्ञान की तरह, प्रतिक्रिया के लिए thx – Eugene

संबंधित मुद्दे