योजना वैक्टर

Question

योजना R5RS मानक राज्यों में 6.3.6 Vectors अनुभाग वैक्टर के बारे में निम्नलिखित की जटिलता:

वेक्टर heterogenous संरचनाओं जिसका तत्वों पूर्णांकों द्वारा अनुक्रमित रहे हैं। एक वेक्टर आमतौर पर एक ही लंबाई की सूची से कम जगह पर कब्जा करता है, और यादृच्छिक रूप से चुने गए तत्व तक पहुंचने के लिए आवश्यक औसत समय सूची के मुकाबले वेक्टर के लिए आम तौर पर कम होता है।

वैक्टरों का यह विवरण थोड़ा फैल गया है।

मुझे पता है कि क्या इस वास्तव मेंvector-ref और list-ref संचालन और उनकी जटिलता के संदर्भ में इसका मतलब है करना चाहते हैं। दोनों प्रक्रियाएं वेक्टर और सूची की के-वें तत्व लौटाती हैं। क्या वेक्टर ऑपरेशन ओ (1) है और सूची ऑपरेशन ओ (एन) है? सूची से वैक्टर अलग कैसे हैं? मुझे इसके बारे में और जानकारी कहां मिल सकती है?

अभी मैं आसान लुकअप के लिए कुंजी/मूल्य जोड़े संग्रहीत करने के लिए डेटा संरचना के रूप में एसोसिएशन सूचियों का उपयोग कर रहा हूं। यदि चाबियाँ पूर्णांक हैं तो मूल्यों को संग्रहीत करने के लिए वेक्टरों का उपयोग करना बेहतर होगा।

Answer 1

vector-ref और list-ref का बहुत विशिष्ट विवरण कार्यान्वयन पर निर्भर कर रहे हैं, जिसका अर्थ है: प्रत्येक योजना दुभाषिया विनिर्देश इसे लागू कर सकते हैं के रूप में यह देखता है फिट है, तो अपने प्रश्न के लिए एक जवाब R5RS के अनुरूप सभी दुभाषिए का सामान्यीकरण नहीं किया जा सकता, आपके द्वारा उपयोग किए जा रहे वास्तविक दुभाषिया पर पर निर्भर करता है।

लेकिन हाँ, किसी भी सभ्य कार्यान्वयन में यह मानने के लिए एक सुरक्षित शर्त है कि vector-ref ऑपरेशन ओ (1) है, और list-ref ऑपरेशन शायद ओ (एन) है। क्यूं कर? क्योंकि हुड के तहत एक वेक्टर, कार्यान्वयन भाषा के मूल निवासी डेटा संरचना का उपयोग करके कार्यान्वित किया जाना चाहिए, जो ओ (1) को इसके सूचकांक (कहते हैं, एक आदिम सरणी) के तत्व को एक्सेस करने की अनुमति देता है - इसलिए vector-ref को सीधे कार्यान्वित करना। जबकि लिस्प में सूचियां cons कोशिकाओं को जोड़कर बनाई गई हैं, और किसी दिए गए इंडेक्स में एक तत्व ढूंढने से सूची में इससे पहले सभी तत्वों को घुमाने में शामिल किया जाता है - इसलिए ओ (एन) जटिलता।

एक साइड नोट के रूप में - हाँ, वेक्टरों का उपयोग कुंजी/मूल्य जोड़े की एसोसिएशन सूचियों का उपयोग करने से एक तेज़ विकल्प होगा, जब तक कि कुंजी पूर्णांक हों और अनुक्रमित किए जाने वाले तत्वों की संख्या पहले से ज्ञात हो (एक योजना वेक्टर इसके निर्माण के बाद इसका आकार नहीं बढ़ सकता है)। सामान्य मामले के लिए (पूर्णांक के अलावा कुंजी, परिवर्तनीय आकार) जांचें कि क्या आपका दुभाषिया हैश तालिकाओं का समर्थन करता है या बाहरी पुस्तकालय का उपयोग करता है जो उन्हें प्रदान करता है (कहें, SRFI 69)।

Answer 2

ए सूचीcons सेल्स का निर्माण किया गया है। R⁵RS list section से:

सूची के लगातार जोड़े के कार फ़ील्ड में ऑब्जेक्ट्स सूची के तत्व हैं। उदाहरण के लिए, एक दो-तत्व सूची एक जोड़ी है जिसका कार पहला तत्व है और जिसका सीडीआर एक जोड़ी है जिसका कार दूसरा तत्व है और जिसका सीडीआर खाली सूची है। सूची की लंबाई तत्वों की संख्या है, जो जोड़ों की संख्या के समान है। (a . (b . (c .())))

और निम्नलिखित "नोड्स" द्वारा स्मृति में प्रतिनिधित्व किया जा सकता है::

[p] --> [p] --> [p] --> null 
|  |  | 
|==> a |==> b |==> c 

प्रत्येक नोड [] साथ

उदाहरण के लिए, सूची (a b c) जोड़े की आगामी श्रृंखला के बराबर है मूल्य में एक सूचक p (यह car) है, और अगले तत्व के लिए एक अन्य सूचक (यह cdr है)।

यह सूची असीमित लंबाई तक बढ़ने की अनुमति देता है, लेकिन सूची के सामने शुरू करने के लिए ref ऑपरेशन की आवश्यकता है और अनुरोध किए गए एक को खोजने के लिए k तत्वों को पार करें। जैसा कि आपने कहा है, यह ओ (एन) है।

---

इसके विपरीत, एक वेक्टर मूल रूप से मान जो आंतरिक रूप से संकेत की एक सरणी के रूप में प्रतिनिधित्व किया जा सकता है की एक सरणी है। उदाहरण के लिए, वेक्टर #(a b c) प्रतिनिधित्व किया जा सकता है के रूप में:

[p p p] 
| | | 
| | |==> c 
| | 
| |==> b 
| 
|==> a 

कहाँ सरणी [] तीन संकेत की एक श्रृंखला शामिल है, और प्रत्येक सूचक वेक्टर में एक मूल्य को सौंपा गया है। तो आंतरिक रूप से आप v[3] नोटेशन का उपयोग कर वेक्टर v के तीसरे तत्व का संदर्भ दे सकते हैं। चूंकि आपको पिछले तत्वों को पार करने की आवश्यकता नहीं है, vector-ref एक ओ (1) ऑपरेशन है।

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

---

कई संसाधन ऑनलाइन कर रहे हैं - Scheme Data Structures पर इस लेख में और अधिक विस्तार में चला जाता है और कुछ उदाहरण प्रदान करता है, हालांकि यह बहुत अधिक सूचियों पर ध्यान केंद्रित है।

---

सब ने कहा, अपनी चाबी कर रहे हैं (या हो सकता है) पूर्णांकों और आप या तो तत्वों की एक निश्चित संख्या है या वेक्टर reallocations के लिए उचित समय के साथ प्रबंधन कर सकते हैं - उदाहरण के लिए, आप स्टार्टअप पर वेक्टर लोड और फिर ज्यादातर पढ़ते हैं - एक वेक्टर एक एसोसिएशन सूची के लिए एक आकर्षक विकल्प हो सकता है।