जावा

Question

में बड़ी सूचियों के लिए सबसे अच्छी सूची कार्यान्वयन क्या है मुझे एन तत्वों की एक बड़ी सूची बनाना है (100,000 तक हो सकता है)। सूची में प्रत्येक तत्व सूची के सूचकांक के बराबर एक पूर्णांक है। इसके बाद मुझे इस सूची में Collections.shuffle को कॉल करना होगा। मेरा सवाल है, जो सूची कार्यान्वयन (या तो जावा संग्रह या अपाचे संग्रह) का उपयोग किया जाना चाहिए। मेरी आंत महसूस है कि ऐरेलिस्ट का यहां भी उपयोग किया जा सकता है। सभी विचारों की सराहना की जाती है। धन्यवाद!

इनपुट के लिए धन्यवाद। मुझे लगता है कि मैं ArrayList के लिए चिपके हुए हूँ। मैं वर्तमान में प्रारंभिक कैपेसिटी पैरामीटर के साथ ऐरेलिस्टिस्ट कन्स्ट्रक्टर का उपयोग कर रहा हूं और मैं सूची का आकार पास करता हूं। तो यदि मूल सूची 100000 है, तो मैं इस नई सूची को नए ऐरेलिस्ट (100000) के साथ बना देता हूं; इसलिए मुझे लगता है कि मेरे पास एक सरणी नहीं है और एक सूची है क्योंकि कोई आकार बदलने वाला नहीं होगा। इसके अलावा, अपाचे संग्रहों में से अधिकांश ग्रोथलिस्ट & की तरह सूचीबद्ध हैं LazyList RandomAccess को लागू नहीं करता है। यह निश्चित रूप से शफल को धीमा कर देगा (javadocs के अनुसार)। FastArrayList RandomAccess को कार्यान्वित करता है लेकिन अपाचे के पास इस वर्ग के लिए एक नोट है, "यह वर्ग क्रॉस-प्लेटफ़ॉर्म नहीं है। इसका उपयोग करने से कुछ आर्किटेक्चर पर अप्रत्याशित विफलता हो सकती है"।

Answer 1

ऐरेलिस्ट में शायद प्रति सूची तत्व कम से कम ओवरहेड है, इसलिए सबसे अच्छा विकल्प होना चाहिए। यदि आपको अक्सर सूची के मध्य में आइटम हटाने की आवश्यकता होती है तो यह एक बदतर विकल्प हो सकता है।

Answer 2

ArrayList<T> शायद ठीक होगा, हाँ - लेकिन आप "सर्वश्रेष्ठ" के लिए क्या मापदंडों का उपयोग कर रहे हैं? और वैसे भी यह कितना अच्छा होना है? जो भी मानदंड है, जटिलता और "भलाई" के बीच आपके व्यापार-बंद क्या हैं?

Answer 3

Collections.shuffle जावाडोक से उद्धरित:

इस विधि रैखिक समय में चलाता है। यदि निर्दिष्ट सूची RandomAccess इंटरफ़ेस को लागू नहीं करती है और यह बड़ी है, तो यह कार्यान्वयन निर्दिष्ट सूची को शफल करने से पहले एक सरणी में डंप करता है, और shuffled सरणी को वापस सूची में डंप करता है। यह वर्गबद्ध व्यवहार से बचाता है जो कि "अनुक्रमिक पहुंच" सूची को स्थानांतरित करने के परिणामस्वरूप होगा।

तो यदि आपके पास कोई अन्य ज़रूरत नहीं है तो मैं ArrayList के साथ जाऊंगा जो RandomAccess लागू करता है।

Answer 4

ArrayList इसके लिए सबसे अच्छी सूची होगी। चूंकि शेल बैकिंग शफल में उपयोग किए गए तत्वों को स्वैप करने के लिए बहुत प्रभावी होगी।

लेकिन यदि आप वास्तव में प्रदर्शन का पीछा कर रहे हैं तो आप int [] या int [] पर आधारित एक कस्टम सूची का उपयोग करने पर विचार करना चाहेंगे क्योंकि सभी सूची और सूची मानक कार्यान्वयन के साथ आप बॉक्सिंग और इंटर्क्स को अनबॉक्सिंग इंक होंगे।

यह पर्याप्त पर कोई मुद्दा नहीं होगा क्योंकि यह केवल पॉइंटर्स को पुन: व्यवस्थित करेगा लेकिन जब आपको आवश्यकता नहीं हो सकती है तो आप 100,000 ऑब्जेक्ट्स तैयार करेंगे। मान लें कि सृजन से पहले आप अपनी सूची का आकार जानते हैं, आप एक नई सूची वर्ग बना सकते हैं जो एक प्राचीन सरणी को लपेटता है। यदि java.util.List के रूप में उपयोग किया जाता है तो आपको अभी भी किसी भी विधि से वापसी को बॉक्स करने की आवश्यकता होगी।

Answer 5

Integer सरणी बनाना और फिर Arrays.asList के साथ इसे लपेटना आपको नियमित ArrayList से भी कम ओवरहेड देता है।

List<Integer> makeList(int size){ 
    if (size < 0) throw new IllegalArgumentException(); 
    Integer[] arr = new Integer[size]; 
    for (int i = 0; i < arr.length; ++i) arr[i] = i; 
    List<Integer> list = Arrays.asList(arr); 
    Collection.shuffle(list); 
    return list; 
} 

आप अंतरिक्ष (... जो बेशक बिल्कुल इस संदर्भ में कुछ भी नहीं है) में से एक पूरे int लायक बचाने के लिए, लेकिन यह से 'असली' ArrayList कम रेंज जांच करता है, इसलिए तक पहुँचने थोड़ा तेज किया जाएगा।शायद कुछ भी आपको नोटिस नहीं होगा, हालांकि :)

Answer 6

Javolution जावा में सबसे तेज़ सूची कार्यान्वयन का दावा है। लेकिन मुझे इस पुस्तकालय में कोई शफल कार्यान्वयन नहीं मिला, इसलिए आपको इसे हाथ से करना होगा।

Answer 7

Google की Guava लाइब्रेरी में कुछ वास्तव में अच्छा आदिम हैंडलिंग है, जिसमें Ints.asList() विधि शामिल है जो एक सूची को वापस लाया जा सकता है।

गुवा परियोजना अभी भी तैनाती के प्रारंभिक चरण में है, हालांकि कोड की सावधानीपूर्वक समीक्षा की गई है और Google पर इसका उपयोग किया जाता है। आपको SVN से कोड पुनर्प्राप्त करने और com.google.common.primitive कक्षाएं बनाने की आवश्यकता होगी।

Answer 8

आप स्मृति मैप किए गए फ़ाइल आधारित सूची कार्यान्वयन का भी उपयोग कर सकते हैं। इस तरह के कार्यान्वयन में सूची स्मृति में पूरी तरह से मौजूद नहीं है लेकिन विशाल सूची का केवल एक वर्ग स्मृति में सक्रिय होगा। यदि आप ढेर अंतरिक्ष सीमा तक पहुंच रहे हैं (अधिकांशतः 32 बिट जेवीएम में) तो आपको मेमोरी मैप की गई फ़ाइल का उपयोग करके डेटा को बिना किसी डेटा को धक्का देनी पड़ सकती है जो सामान्य फ़ाइल I/O से तेज होगी। इस तरह के एक कार्यान्वयन को इस google code में वर्णित किया गया है और इस link में समझाया गया है।

Answer 9

नए आविष्कार किए गए सूची कार्यान्वयन को GlueList कहा जाता है जो ArrayList और LinkedList से बहुत तेज़ है।