प्रभावी जावा आइटम 17: निष्कासन को ओवरराइड कैसे कर सकते हैं() प्रदर्शन में सुधार?

Question

पुस्तक में जोशुआ ब्लोच द्वारा प्रभावी जावा में, इस बात पर एक चर्चा है कि एक वर्ग "न्यायसंगत रूप से चुने गए संरक्षित तरीकों" को अपने आंतरिक कार्यों में हुक के रूप में कैसे प्रदान कर सकता है।
लेखक तो AbstractList.removeRange() में प्रलेखन हवाला देते हैं:

इस विधि इस सूची और उसके उप-सूचियों पर clear आपरेशन द्वारा कहा जाता है। के आंतरिक भाग का लाभ उठाने के लिए इस विधि को ओवरराइड करना सूची कार्यान्वयन इस सूची और इसकी उपसूची पर clear संचालन के प्रदर्शन में काफी सुधार कर सकता है।

मेरा सवाल यह है कि, इस विधि को ओवरराइड करने से प्रदर्शन में सुधार कैसे हो सकता है (बस इसे ओवरराइड करने से ज्यादा नहीं)? क्या कोई इसका उदाहरण दे सकता है?

Answer 1

चलिए एक ठोस उदाहरण लें - मान लीजिए कि आपके कार्यान्वयन को गतिशील सरणी द्वारा समर्थित किया गया है (उदाहरण के लिए ArrayList काम करता है)। अब, मान लीजिए कि आप श्रेणी [प्रारंभ, अंत) में तत्वों को हटाना चाहते हैं। removeRange का डिफ़ॉल्ट कार्यान्वयन start स्थिति में इटरेटर प्राप्त करके काम करता है, फिर remove() उचित समय पर कॉल करता है।

प्रत्येक बार remove() कहा जाता है, गतिशील सरणी कार्यान्वयन को सभी तत्वों को start + 1 पर स्थानांतरित करना होता है और हटाए गए तत्व में दिए गए अंतर को भरने के लिए एक स्थान वापस भेजना होता है। यह संभावित रूप से समय ओ (एन) ले सकता है, क्योंकि संभावित रूप से सभी सरणी तत्वों को शफल करने की आवश्यकता हो सकती है। इसका अर्थ यह है कि यदि आप सूची के कुल k तत्वों को हटा रहे हैं, तो निष्पक्ष दृष्टिकोण में ओ (एन) समय लगेगा, क्योंकि आप ओ (एन) काम के समय कर रहे हैं।

अब एक बेहतर दृष्टिकोण पर विचार करें: स्थिति end पर तत्व नकल start स्थिति है, तो तत्व end + 1start + 1 स्थिति, आदि जब तक सभी तत्वों को कॉपी कर रहे हैं। इसके लिए आपको केवल कुल ओ (एन) काम करने की आवश्यकता है, क्योंकि प्रत्येक तत्व को एक बार में स्थानांतरित किया जाता है। बेवकूफ एल्गोरिदम द्वारा दिए गए ओ (एन) दृष्टिकोण की तुलना में, यह एक बड़ा प्रदर्शन सुधार है। नतीजतन, इस कुशल एल्गोरिदम का उपयोग करने के लिए removeRange ओवरराइडिंग नाटकीय रूप से प्रदर्शन को बढ़ा सकता है।

आशा है कि इससे मदद मिलती है!

Answer 2

विधि के javadocs में विनिर्दिष्ट:

इस कार्यान्वयन एक सूची इटरेटर fromIndex से पहले तैनात हो जाता है, और बार-बार ListIterator.next ListIterator.remove के बाद कॉल जब तक पूरी रेंज हटा दिया गया है।

के बाद से इस सार वर्ग अपनी उपवर्गों के आंतरिक भागों के बारे में पता नहीं है, यह इस सामान्य एल्गोरिथ्म जो मदों की संख्या हटाया जा रहा के लिए आनुपातिक समय में चला जाएगा पर निर्भर करता है।

यदि, उदाहरण के लिए, आपने उप-वर्ग लागू किया है जो तत्वों को एक लिंक्ड सूची के रूप में संग्रहीत करता है। फिर आप इस तथ्य का लाभ उठा सकते हैं और एक लिंक किए गए सूची विशिष्ट एल्गोरिदम का उपयोग करने के लिए इस विधि को ओवरराइड कर सकते हैं (fromIndex पर पॉइंटर को toIndex पर इंगित करने के लिए) जो स्थिर समय में चलता है। इस प्रकार आपने प्रदर्शन में सुधार किया है क्योंकि आपने आंतरिक का लाभ उठाया है।

Answer 3

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