जावा ऐरेलिस्ट स्वचालित रूप से क्यों नहीं हटते

Question

लंबे समय पहले मैंने प्रिंसटन Coursera MOOC से एक वीडियो व्याख्यान देखा: एल्गोरिदम का परिचय, जो here पाया जा सकता है। यह ArrayList को तत्वों को जोड़ने या हटाने के दौरान संरचना की तरह आकार बदलने की लागत बताता है। यह पता चला है कि अगर हम अपनी डेटा संरचना में आकार देने की आपूर्ति करना चाहते हैं तो हम O(n) से amortized O(n)add और remove संचालन के लिए जाएंगे।

मैं कुछ वर्षों से जावा ArrayList का उपयोग कर रहा हूं। मुझे हमेशा यकीन है कि वे स्वचालित रूप से बढ़ते हैं और कम हो जाते हैं। हाल ही में, मेरे आश्चर्य की बात है, मैं this post में गलत साबित हुआ था। जावा ArrayList एस सिकुड़ नहीं है (भले ही वे निश्चित रूप से बढ़ते हैं)।

1. मेरी राय ArrayList रों में सिकुड़ कोई नुकसान नहीं है के रूप में प्रदर्शन पहले से ही amortized O(n) है प्रदान करने में:

   यहाँ मेरी सवाल कर रहे हैं। जावा रचनाकारों ने इस सुविधा को डिजाइन में क्यों शामिल नहीं किया?

2. मुझे पता है कि HashMap एस जैसी अन्य डेटा संरचनाएं भी स्वचालित रूप से कम नहीं होती हैं। क्या जावा में कोई अन्य डेटा संरचना है जो स्वचालित सिकुड़ने का समर्थन करने वाले सरणी के शीर्ष पर बनाई गई है?

3. अन्य भाषाओं में क्या प्रवृत्तियों हैं? पाइथन/सी # आदि में सूचियों, शब्दकोशों, मानचित्रों, सेटों के मामले में स्वचालित सिकुड़ने जैसा दिखता है। यदि वे जावा के विपरीत दिशा में जाते हैं, तो मेरा प्रश्न है: क्यों?

Answer 1

टिप्पणियां पहले से ही जो कुछ आप पूछ रहे हैं उसे कवर करती हैं। यहाँ आपके प्रश्नों पर कुछ विचार:

1. जब जावा में ArrayList की तरह एक संरचना का निर्माण, डेवलपर्स क्रम/प्रदर्शन के बारे में कुछ निर्णय करते हैं। उन्होंने स्पष्ट रूप से अतिरिक्त रनटाइम से बचने के लिए "सामान्य" संचालन से सिकुड़ने का निर्णय लिया, जिसकी आवश्यकता है।

2. सवाल यह है कि आप स्वचालित रूप से क्यों हटना चाहते हैं। ArrayList इतना बढ़ता नहीं है (कारक लगभग 1.5 है; newCapacity = oldCapacity + (oldCapacity >> 1), सटीक होने के लिए)। हो सकता है कि आप बीच में भी डालें और न केवल अंत में संलग्न हों। फिर LinkedList (जो किसी सरणी पर आधारित नहीं है -> कोई संकीर्ण आवश्यकता नहीं है) बेहतर हो सकता है। यह वास्तव में आपके उपयोग के मामले पर निर्भर करता है। यदि आपको लगता है कि आपको वास्तव में ArrayList सब कुछ चाहिए, लेकिन तत्वों को हटाते समय इसे कम करना होगा (मुझे संदेह है कि आपको वास्तव में इसकी आवश्यकता है), बस ArrayList का विस्तार करें और विधियों को ओवरराइड करें। लेकिन सावधान रहना! यदि आप हर हटाने पर सिकुड़ते हैं, तो आप O(n) पर वापस आ गए हैं।

3. सी # List और सी ++ vector तत्वों को हटाने पर एक सूची को कम करने के बारे में वही व्यवहार करते हैं। लेकिन स्वचालित बढ़ने के कारक अलग-अलग होते हैं। यहां तक ​​कि कुछ जावा-कार्यान्वयन भी विभिन्न कारकों का उपयोग करते हैं।