एक सूची में पुनरावृत्ति क्यों करना इसके माध्यम से अनुक्रमणित करने से तेज होगा?

Question

पढ़ना Java documentation for the ADT List यह कहते हैं:

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

इसका क्या अर्थ है? मैं निष्कर्ष निकाला नहीं है जो खींचा गया है।

Answer 1

किसी लिंक किए गए सूची में, प्रत्येक तत्व अगले तत्व के लिए सूचक है:

head -> item1 -> item2 -> item3 -> etc. 

item3 पहुंचने के लिए, आप स्पष्ट रूप से देख सकते हैं कि आप सिर से चलने के लिए की जरूरत है प्रत्येक नोड के माध्यम से जब तक आप आइटम 3 तक नहीं पहुंच जाते, क्योंकि आप सीधे कूद नहीं सकते हैं।

इस प्रकार, यदि मैं अगर मैं लिखना इस, प्रत्येक तत्व के मूल्य मुद्रित करने के लिए चाहता था:

head -> print head 
head -> item1 -> print item1 
head -> item1 -> item2 -> print item2 
head -> item1 -> item2 -> item3 print item3 

यह बुरी तरह अक्षम क्योंकि हर बार है:

for(int i = 0; i < 4; i++) { 
    System.out.println(list.get(i)); 
} 

क्या होता है यह है आप सूची की शुरुआत से इसे पुनरारंभ कर रहे हैं और प्रत्येक आइटम के माध्यम से चला जाता है। इसका मतलब है कि आपकी जटिलता सूची को पार करने के लिए प्रभावी रूप से O(N^2) है!

, तो इसके बजाय मैं इस किया था: एक ही ट्रेवर्सल, जो O(N) है में

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc. 

सब:

for(String s: list) { 
    System.out.println(s); 
} 

तो क्या होता है यह है।

अब List के अन्य कार्यान्वयन पर जा रहा है जो कि ArrayList है, जिसे एक साधारण सरणी द्वारा समर्थित किया जाता है। उस स्थिति में उपरोक्त दोनों ट्रैवर्स समकक्ष हैं, क्योंकि एक सरणी संगत है, इसलिए यह यादृच्छिक कूद को मनमाने ढंग से स्थानांतरित करने की अनुमति देती है।

Answer 2

जवाब यहाँ निहित है:

ध्यान दें कि इन आपरेशनों (, LinkedList वर्ग उदाहरण के लिए) कुछ कार्यान्वयन के लिए सूचकांक मूल्य के लिए आनुपातिक समय में निष्पादित कर सकते हैं

एक लिंक्ड सूची नहीं करता है एक अंतर्निहित सूचकांक नहीं है; कॉलिंग .get(x) को पहली प्रविष्टि को खोजने के लिए सूची कार्यान्वयन की आवश्यकता होगी और .next() x-1 बार (ओ (एन) या रैखिक समय पहुंच के लिए) पर कॉल करें, जहां एक सरणी-समर्थित सूची केवल 0 (3) में स्थिरता backingarray[x] में हो सकती है या निरंतर पहर।

आप JavaDoc for LinkedList को देखें, तो आप टिप्पणी

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

जबकि JavaDoc for ArrayList इसी

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

size, isEmpty, get, set, iterator, और listIterator संचालन निरंतर समय में चलाते हैं। एडी ऑपरेशन अमोरिज्ड निरंतर समय में चलता है, यानी, एन तत्वों को जोड़ने के लिए ओ (एन) समय की आवश्यकता होती है। अन्य सभी परिचालन रैखिक समय में चलते हैं (मोटे तौर पर बोलते हैं)। LinkedList कार्यान्वयन के लिए निरंतर कारक कम है।

एक related question titled "Big-O Summary for Java Collections Framework" एक जवाब इस संसाधन, "Java Collections JDK6" जो उपयोगी हो सकते की ओर इशारा करते हैं।

Answer 3

LinkedList के i-th तत्व को खोजने के लिए कार्यान्वयन i-th तक सभी तत्वों के माध्यम से होता है।

तो

for(int i = 0; i < list.length ; i++) { 
    Object something = list.get(i); //Slow for LinkedList 
} 

Answer 4

जबकि स्वीकृत उत्तर सबसे निश्चित रूप से सही है, तो क्या मैं मामूली दोष बता सकता हूं। का हवाला देते हुए ट्यूडर:

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

यह पूरी तरह से सच नहीं है। सच्चाई यह है कि

एक ArrayList के साथ, एक हस्तलिखित गिना पाश है के बारे में 3x तेजी

source: Designing for Performance, Google's Android doc

ध्यान दें कि हस्तलिखित पाश अनुक्रमित यात्रा को संदर्भित करता है, है। मुझे इटरेटर की वजह से संदेह है जिसका उपयोग लूप के लिए बढ़ाया जाता है। यह एक संरचना में दंड में मामूली प्रदर्शन का उत्पादन करता है जिसे एक संगत सरणी द्वारा समर्थित किया जाता है। मुझे यह भी संदेह है कि यह वेक्टर वर्ग के लिए सच हो सकता है।

मेरा नियम है, जब भी संभव हो लूप के लिए बढ़ाया गया उपयोग करें, और यदि आप वास्तव में प्रदर्शन की परवाह करते हैं, तो केवल ArrayLists या वेक्टर के लिए अनुक्रमित पुनरावृत्ति का उपयोग करें।ज्यादातर मामलों में, आप इसे अनदेखा भी कर सकते हैं- संकलक पृष्ठभूमि में इसे अनुकूलित कर सकता है।

मैं केवल यह इंगित करना चाहता हूं कि एंड्रॉइड में विकास के संदर्भ में, ऐरेलिस्ट के दोनों ट्रैवर्स आवश्यक नहीं हैं। विचार के लिए बस खाना।

Answer 5

लुकअप के लिए ऑफसेट के साथ एक सूची में इटरेट करना, जैसे कि i, श्लेमेल चित्रकार के एल्गोरिदम के समान है।

शैलेमियल सड़क के चित्र के रूप में नौकरी प्राप्त करता है, सड़क के बीच नीचे बिंदीदार रेखा चित्रित करता है। पहले दिन वह सड़क पर पेंट करने और सड़क के 300 गज की दूरी तय करने का एक कैन लेता है। "यह सुंदर अच्छा है!" अपने मालिक कहते हैं, "आप एक तेज कार्यकर्ता हैं!" और उसे एक कोपेक देता है।

अगले दिन शलेमिल केवल 150 गज की दूरी पर हो जाता है। "ठीक है, यह कल जितना अच्छा नहीं है, लेकिन आप अभी भी एक तेज कार्यकर्ता हैं। 150 गज सम्मानजनक है," और उसे एक कोपेक देता है।

अगले दिन शलेमेल सड़क के 30 गज की दूरी पर चित्रित करता है। "केवल 30!" उसके मालिक को चिल्लाता है। "यह अस्वीकार्य है! पहले दिन आपने दस बार किया था कि बहुत काम! क्या चल रहा है?" श्लेमीएल कहते हैं,

"मैं इसकी मदद नहीं कर सकता"। "हर दिन मैं पेंट से दूर और दूर दूर हो सकता है!"

Source।

यह छोटी सी कहानी यह समझने में आसान हो सकती है कि आंतरिक रूप से क्या हो रहा है और यह इतना अक्षम क्यों है।