स्कैला सूची में आकार का क्षेत्र क्यों नहीं है?

जावा पृष्ठभूमि से आ रहा है, मुझे आश्चर्य है कि क्यों List स्कैला में size फ़ील्ड नहीं है जैसे जावा जावा समतुल्य LinkedList। आखिरकार, एक आकार के क्षेत्र के साथ आप निरंतर समय में सूची का आकार निर्धारित करने में सक्षम होंगे, तो आकार क्षेत्र क्यों गिराया गया था?स्कैला सूची में आकार का क्षेत्र क्यों नहीं है?

(यह सवाल स्काला 2.8 में नया संग्रह वर्गों को संदर्भित करता है और बाद में। इसके अलावा, मैं अपरिवर्तनीय List को परिवर्तनशील एक चर्चा करते हुए हूँ, नहीं।)

स्रोत

2011-11-19 python dude

यह जावा में एक आकार() 'है, एक समारोह। – Kapep

लेकिन फ़ंक्शन को एक फ़ील्ड द्वारा समर्थित किया जाता है, जो इसे ओ (1) बनाता है। स्कैला सूची में ऐसा कोई क्षेत्र नहीं है, अच्छे कारण के लिए, लेकिन यह लंबाई ओ (एन) तक पहुंच बनाता है। –

"* पायथन * दोस्त" * जावा * पृष्ठभूमि से आता है? * पायथन * भाषा का संदर्भ नहीं देता है, है ना? – huynhjl

एक नहीं कह सकता आकार क्षेत्र आकार जहां वे सर्वत्र हैं और वे भी एमएल और हास्केल में बहुत आम हैं लिस्प के बाद से 50 वर्षों के लिए ही अस्तित्व में है बिना हटा दिया गया, सूची के रूप में दोनों स्केला में प्रभावशाली था,।

मूल कारण यह है कि सूची एक पुनरावर्ती संरचना है। एक खाली खाली ListCons(head: A, tail: List[A]) है - सिवाय इसके कि Cons को वास्तव में सुविधाजनक इन्फिक्स नोटेशन की अनुमति देने के लिए :: कहा जाता है। आप पूंछ (इसके मुख्य तत्व के बिना सूची) तक पहुंच सकते हैं और यह भी एक सूची है। और यह लगभग हर समय किया जाता है। तो सूची में गिनती होने का मतलब केवल एक पूर्णांक जोड़ना नहीं है, लेकिन तत्वों के रूप में कई पूर्णांक हैं। यह व्यवहार्य है, लेकिन निश्चित रूप से मुक्त नहीं है।

यदि आप जावा के LinkedList, LinkedList के साथ तुलना करते हैं तो एक पुनरावर्ती कार्यान्वयन (नोड पर आधारित है, जो विपक्ष की तरह कम या कम है, लेकिन दोनों दिशाओं में लिंक के साथ)। लेकिन एक लिंक्डलिस्ट एक नोड नहीं है, यह उनका मालिक है (और उनकी गिनती रखें)। इसलिए जब यह एक पुनरावर्ती कार्यान्वयन है, तो आप इसे दोबारा इलाज नहीं कर सकते हैं। यह आप एक लिंक्डलिस्ट के रूप में एक लिंक्डलिस्ट के पूंछ चाहते थे, आपको या तो सिर को हटाना होगा और अपनी सूची बदलनी होगी या अन्य सभी पूंछ तत्वों को एक नई लिंक्डलिस्ट में कॉपी करना होगा। तो स्कैला का List और जावा का LinkedList बहुत अलग संरचनाएं हैं।

स्रोत

2011-11-19 22:21:43

सूची स्केल में सख्त हैं। तो हर बार जब विपक्ष लागू होता है तो यह पूंछ के आकार को जानता है और इसलिए 1 से बढ़ सकता है और इसे एक विशिष्ट क्षेत्र में लिख सकता है। 'विपक्ष की तरह (सिर: ए, पूंछ: सूची [ए]) {ओवरराइड वैल आकार: Int = tail.size + 1} '। यह संभव है, लेकिन बहुत भूख माना जा सकता है। – ayvango

आप length क्षेत्र जांच की है?

स्रोत

2011-11-19 22:02:12

'लंबाई' एक विधि है जो पूरी सूची में जाती है, इसलिए 'ओ (एन)' जटिलता होती है। ओपी पूछता है कि निरंतर समय तक पहुंच के साथ 'लंबाई' * फ़ील्ड * क्यों नहीं है। –

@Udo आयोजित: आपका लिंक स्कैला 2.7.7 से है, जिसका मुझे कोई अनुभव नहीं है। मेरा प्रश्न स्कैला 2.9+ पर आधारित है, और विशेष रूप से पुस्तक "प्रोग्रामिंग इन स्कैला", द्वितीय एड। पर, जहां यह अध्याय 16 में कहा गया है कि सूची की लंबाई निर्धारित करने से तत्वों की संख्या में रैखिक है। –

http://www.scala-lang.org/api/current/scala/collection/mutable/LinkedList.html की लंबाई भी है और 2.9 है। आपको वहां आकार भी मिलेगा जो लंबाई के बराबर है। –

सूची आकार को परिभाषित करता है:

> List(1, 2, 3).size 
res4: Int = 3

जो रैखिक ओ (एन) निष्पादन समय है। यदि आपको वास्तव में निरंतर समय की आवश्यकता है, तो आपको म्यूटेबल ListBuffer पर विचार करना चाहिए जो निरंतर समय आकार कार्यान्वयन प्रदान करता है।

स्रोत

2011-11-19 22:07:49 David

स्कैला का कौन सा संस्करण यह है? 2.8 से पहले या बाद में? –

कम से कम 2.8 और बाद में। देखें: http://www.scala-lang.org/api/2.8.0/scala/collection/immutable/List.html – David

हालांकि यह निरंतर समय है? यह कहता है "लंबाई के बराबर" –

क्योंकि इस क्षेत्र को बनाए रखने

सभी सूचियों के लिए स्मृति ओवरहेड जोड़े हैं;
प्रत्येक सूची निर्माण पर मामूली समय ओवरहेड जोड़ें।

जावा में आमतौर पर LinkedList बनाया जाता है, और फिर तत्वों को जोड़कर/हटाकर नई सूचियां तैयार किए बिना छेड़छाड़ की जाती है; स्कैला में कई List एस बनाए गए हैं।

तो यह निर्णय लिया गया कि ओवरहेड इसके लायक नहीं है।

स्रोत

2011-11-19 22:21:22

वास्तव में, एक 'आकार' फ़ील्ड जोड़ना * 8 से 16 बाइट्स से _cons_ के आकार को डबल * करेगा, बशर्ते कि 8 बाइट्स के गुणकों में ऑब्जेक्ट आवंटित किए जाएं। –

क्या मुझे कुछ याद आ रही है? आकार है:

Welcome to Scala version 2.9.1.final (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_29). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.collection.immutable.List 
import scala.collection.immutable.List 

scala> val a = List(1,2,3) 
a: List[Int] = List(1, 2, 3) 

scala> a size 
res0: Int = 3

स्रोत

2011-11-20 00:08:04 Fred

सटीक लेकिन यह एक ओ (एन) आकार कार्यान्वयन है। विषय यह था कि लिंक्डलिस्ट जावा कार्यान्वयन में एक आकार क्षेत्र है जो निरंतर समय में आकार को पुन: स्थापित करता है। – David

हे (एन) जटिलता के "नुकसान" के रूप में बड़ा के रूप में आप सोच सकते हैं नहीं है। मार्टिन ओडर्स्की ने एक वार्ता में उल्लेख किया कि (यदि मुझे सही याद है) किसी भी कंप्यूटर भाषा में सभी कार्यक्रमों में बनाई गई सभी सूचियों में से 9 0% का आकार 4 या उससे कम है।(यह अपरिवर्तनीयता और दक्षता के संदर्भ में था)

इसलिए, ओ (एन) size के लिए एक्सेस समय अधिकांश सूचियों के लिए इतना बड़ा ओवरहेड नहीं है, और जैसा कि अन्य ने यहां उल्लेख किया है, स्मृति बचत को क्षतिपूर्ति से अधिक इस।

स्रोत

2011-11-20 00:28:26 Adrian

स्कैला सूची में आकार का क्षेत्र क्यों नहीं है?

उत्तर

संबंधित मुद्दे