एक सूची में बुरा क्यों लगा रहा है?

Question

मैंने हाल ही में स्कैला सीखना शुरू कर दिया है, और मैं :: (विपक्ष) फ़ंक्शन में आया हूं, जो एक सूची में आगे बढ़ता है।
पुस्तक "स्काला में प्रोग्रामिंग" में यह कहा गया है कोई संलग्न समारोह है, क्योंकि एक सूची में जोड़कर प्रदर्शन ओ (एन) है prepending जबकि ओ के एक प्रदर्शन (1)

कुछ बस मुझे के रूप में के बारे में गलत हमलों है वह बयान

प्रदर्शन कार्यान्वयन पर निर्भर नहीं है? क्या आगे और पिछड़े लिंक दोनों के साथ सूची को कार्यान्वित करना संभव नहीं है और कंटेनर में पहला और अंतिम तत्व संग्रहीत करना संभव नहीं है?

दूसरा प्रश्न मुझे लगता है कि जब मुझे कोई सूची है तो मुझे क्या करना है, 1,2,3 कहें और मैं इसके अंत में 4 जोड़ना चाहता हूं?

Answer 1

कुंजी यह है कि x :: somelistsomelist को म्यूटेट नहीं करता है, बल्कि इसके बजाय एक नई सूची बनाता है, जिसमें somelist के सभी तत्व होते हैं। यह ओ (1) समय में किया जा सकता है क्योंकि आपको नव निर्मित, एकल लिंक वाली सूची में x के उत्तराधिकारी के रूप में केवल somelist सेट करने की आवश्यकता है।

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

दूसरे प्रश्न के संबंध में: आप अपनी सूची के अंत में एकल तत्व सूची को जोड़ने के लिए ::: का उपयोग कर सकते हैं। यह एक ओ (एन) ऑपरेशन है।

List(1,2,3) ::: List(4) 

Answer 2

prepending तेजी से होता है क्योंकि यह केवल दो आपरेशन की आवश्यकता है:

1. नई सूची नोड
2. कि मौजूदा सूची

जोड़कर करने के लिए नए नोड बिंदु अधिक आपरेशन की आवश्यकता है, क्योंकि आपके पास है बनाएं सूची के अंत तक पहुंचने के लिए क्योंकि आपके पास केवल सिर के लिए सूचक है।

मैंने पहले स्काला में प्रोग्राम कभी नहीं किया है, लेकिन आप एक List Buffer

Answer 3

सबसे कार्यात्मक भाषाओं प्रमुखता से एक अकेले लिंक्ड-सूची डेटा संरचना लगाने, के रूप में यह एक आसान अपरिवर्तनीय संग्रह प्रकार है की कोशिश कर सकते। जब आप एक कार्यात्मक भाषा में "सूची" कहते हैं, तो आमतौर पर इसका मतलब है (एक सिंगल-लिंक्ड सूची, आमतौर पर अपरिवर्तनीय)। इस तरह के एक प्रकार के लिए, संलग्न है ओ (एन) जबकि विपक्ष ओ (1) है।

Answer 4

अन्य उत्तरों ने इस घटना के लिए अच्छी व्याख्याएं दी हैं। यदि आप सबराउटिन में किसी सूची में कई आइटम जोड़ रहे हैं, या यदि आप तत्वों को जोड़कर एक सूची बना रहे हैं, तो एक कार्यात्मक मुहावरे सूची में सूची बनाने के लिए फ्रंट पर आइटमों को ध्यान में रखना है , फिर अंत में इसे उलट दें। यह आपको ओ (एन²) के बजाय ओ (एन) प्रदर्शन देता है।

Answer 5

चूंकि सवाल अभी अपडेट किया गया था, यह ध्यान देने योग्य है कि चीजें यहां बदल गई हैं।

आज के स्कैला में, आप किसी अनुक्रमिक संग्रह के अंत में किसी आइटम को जोड़ने के लिए बस xs :+ x का उपयोग कर सकते हैं। (इसके अलावा कई x +: xs पहले जोड़ें करने के लिए है। स्काला के 2.8+ संग्रह संचालन से कई के लिए स्मरक कि col पर col रूपांतर के बगल में चला जाता है।)

यह हे हो जाएगा (n) के साथ List या Seq का डिफ़ॉल्ट लिंक कार्यान्वयन, लेकिन यदि आप Vector या IndexedSeq का उपयोग करते हैं, तो यह प्रभावी रूप से स्थिर समय होगा। स्कैला का Vector शायद स्कैला की सबसे उपयोगी सूची-जैसी संग्रह है- जावा के Vector के विपरीत जो आजकल अधिकतर बेकार है।

यदि आप स्कैला 2.8 या उच्चतर में काम कर रहे हैं, तो collections introduction एक पूर्ण पढ़ना आवश्यक है।