स्मृति आवंटन परिप्रेक्ष्य से ArrayList बनाम LinkedList

Question

मुझे जावा सूची में उदाहरण के नामों के लिए बड़ी मात्रा में जानकारी स्टोर करने की आवश्यकता है। वस्तुओं की संख्या बदल सकती है (या संक्षेप में मैं आकार को पूर्वनिर्धारित नहीं कर सकता)। मेरा मानना ​​है कि स्मृति आवंटन परिप्रेक्ष्य से लिंक्डलिस्ट आरेलिस्ट के मुकाबले एक बेहतर विकल्प होगा, क्योंकि एक बार अधिकतम आकार पहुंचने के बाद एक ऐरेलिस्ट के लिए, स्वचालित रूप से स्मृति आवंटन युगल होता है और इसलिए हमेशा आवंटित होने वाली अधिक स्मृति का मौका होता है क्या ज़रूरत है।

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

Answer 1

LinkedList कम प्रविष्टियों आवंटित सकता है, लेकिन यह इन प्रविष्टियों को astronomically अधिक महंगी की तुलना में वे ArrayList के लिए होगा रहे हैं - पर्याप्त है कि बुरी से बुरी हालत ArrayList जहाँ तक स्मृति का संबंध है सस्ता है।

(FYI करें, मुझे लगता है कि आप इसे गलत मिल गया है;। ArrayList 1.5x जब यह पूर्ण नहीं 2x है द्वारा बढ़ता है)

उदा देखें http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures: LinkedList प्रति तत्व 24 बाइट्स का उपभोग करता है, जबकि ArrayList प्रति तत्व 4 बाइट्स सबसे अच्छे मामले में खपत करता है, और सबसे खराब मामले में 6 बाइट प्रति तत्व। (परिणाम 32-बिट बनाम 64-बिट जेवीएम, और संपीड़ित ऑब्जेक्ट पॉइंटर विकल्पों के आधार पर भिन्न हो सकते हैं, लेकिन उन तुलनाओं में LinkedList कम से कम 36 बाइट्स/तत्व की लागत है, और ArrayList सबसे अच्छा 8 और सबसे खराब 12 है।)

अद्यतन:

मैं यहाँ अन्य पदों से समझते हैं कि व्यक्ति एक LinkedList में संग्रहीत तत्वों एक ArrayList तुलना में अधिक स्थान लेता है LinkedList भी नोड जानकारी स्टोर करने की जरूरत है के रूप में, लेकिन मैं अभी भी परिदृश्य के लिए अनुमान लगा रहा हूँ मैंने परिभाषित किया है कि लिंक्डलिस्ट एक बेहतर विकल्प हो सकता है। इसके अलावा, मैं प्रदर्शन पहलू (fetching, हटाना आदि) में शामिल नहीं होना चाहता, जैसा कि पहले से ही इस पर चर्चा की जा चुकी है।

स्पष्ट है, यहां तक ​​कि सबसे खराब स्थिति में, ArrayList ही तत्वों के साथ एक LinkedList की तुलना में छोटे 4x है। LinkedList जीत बनाने का एकमात्र संभावित तरीका जानबूझकर फुलाए गए मूल्य के साथ ensureCapacity पर कॉल करके या ArrayList से जोड़े गए कई मूल्यों को हटाने के द्वारा जानबूझकर तुलना को ठीक करना है।

संक्षेप में, यह LinkedList स्मृति तुलना जीत सुनिश्चित करने के लिए मूल रूप से असंभव है, और यदि आप, अंतरिक्ष के बारे में परवाह तो बुला ArrayList पर trimToSize() तुरन्त एक विशाल अंतर से फिर से ArrayList जीत कर देगा। गंभीरता से। ArrayList जीतता है।

Answer 2

ArrayList.trimToSize() आपको संतुष्ट कर सकता है।

इस ArrayList उदाहरण की सूची को वर्तमान आकार के रूप में ट्रिम करता है। एक एप्लिकेशन इस ऑपरेशन का उपयोग को एक ArrayList इंस्टेंस के संग्रहण को कम करने के लिए कर सकता है।

वैसे, ऐरेलिस्टिस्ट जावा 6 में, यह डबल क्षमता नहीं है, यह लगभग 1.5 गुणा अधिकतम आकार तक पहुंच गया है।

Answer 3

ऐरेलिस्ट प्रति ऑब्जेक्ट का एक संदर्भ उपयोग करते हैं (या दो जब इसका आकार जितना दोगुना हो) यह आम तौर पर 4 बाइट होता है।

लिंक्डलिस्ट केवल इसकी जरूरतों को नोड्स का उपयोग करता है, लेकिन ये प्रत्येक 24 बाइट्स हो सकते हैं।

तो यहां तक ​​कि सबसे खराब ArrayList LinkedList से 3x छोटा होगा।

ARrayList समर्थन को याद करने के लिए यादृच्छिक अभिगम ओ (1) लेकिन लिंक्डलिस्ट ओ (एन) है। अंत से हटाने के लिए, दोनों कर रहे हैं हे (1), मध्य ArrayList में कहीं से हटाने के लिए हे (एन)

है जब तक आप लाखों लोगों की प्रविष्टियों की है, संग्रह के आकार बात की संभावना नहीं है। सबसे पहले क्या मायने रखता है प्रविष्टियों का आकार जो संग्रहित संग्रह के बावजूद समान है।

Answer 4

... लेकिन मैं अभी भी परिदृश्य मैं परिभाषित किया है LinkedList एक बेहतर विकल्प

आपका अनुमान सही नहीं है हो सकता है के लिए अनुमान लगा रहा हूँ।

एक बार जब आप सरणी सूची की प्रारंभिक क्षमता को पार कर चुके हैं, तो बैकिंग का आकार 1 और 2 संदर्भों के बीच प्रविष्टियों की संख्या के बीच होगा। यह बैकिंग सरणी विकसित करने के लिए उपयोग की जाने वाली रणनीति के कारण है।

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

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

---

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

Answer 5

लिफाफा बुरी से बुरी हालत के पीछे: एक सरणी में

500,000 नाम आवंटित सरणी के अप्रयुक्त भाग में, 1000000 = 500,000 इस्तेमाल किया के लिए आकार 500,000 खाली संकेत दिए गए।

एक लिंक्ड सूची में 500,000 प्रविष्टियां = प्रति प्रविष्टि 3 पॉइंटर्स (नोड ऑब्जेक्ट वर्तमान, पिछला, और अगला) = स्मृति में 1,5000,000 पॉइंटर्स हैं। (फिर आपको नोड का आकार स्वयं जोड़ना होगा)