सर्कुलर सूचियों के लिए क्या अच्छा है (लिस्प या योजना में)?

Question

मैं ध्यान दें कि योजना और लिस्प (मुझे लगता है) परिपत्र सूचियों का समर्थन है, और मैं C/C++ 'को आसान बनाने में' प्रविष्टि और तत्वों का विलोपन के लिए परिपत्र सूचियों का इस्तेमाल किया है, लेकिन क्या वे के लिए अच्छा कर रहे हैं?

योजना सुनिश्चित करता है कि वे बनाया जा सकता है और प्रसंस्कृत, लेकिन किस लिए?

वहाँ एक 'हत्यारा' डेटा संरचना है कि परिपत्र या पूंछ परिपत्र होने की जरूरत है है?

Answer 1

यह कहकर कि 'सर्कुलर सूचियों' का समर्थन करता है यह थोड़ा सा है। आप लिस्प में सभी प्रकार के परिपत्र डेटा संरचनाएं बना सकते हैं। कई प्रोग्रामिंग भाषाओं की तरह। इस संबंध में लिस्प के बारे में बहुत खास नहीं है। अपने ठेठ 'एल्गोरिदम और डेटास्ट्रक्चर' पुस्तक को लें और किसी भी परिपत्र डेटा संरचना को लागू करें: ग्राफ, अंगूठियां, ... कुछ लिस्पस ऑफ़र क्या है कि कोई सर्कुलर डेटा संरचनाओं को प्रिंट और पढ़ सकता है। इसका समर्थन इसलिए है क्योंकि ठेठ लिस्प प्रोग्रामिंग डोमेन सर्कुलर डेटा स्ट्रक्चर सामान्य हैं: पार्सर्स, रिलेशनल एक्सप्रेशन, शब्दों के नेटवर्क, योजनाएं, ...

यह काफी आम है कि डेटा संरचनाओं में चक्र होते हैं। वास्तविक 'परिपत्र सूचियां' अक्सर उपयोग नहीं की जाती हैं। उदाहरण के लिए एक कार्य शेड्यूलर के बारे में सोचें जो एक कार्य चलाता है और कुछ समय बाद अगली बार स्विच करता है। कार्यों की सूची परिपत्र हो सकती है ताकि 'अंतिम' कार्य के बाद शेड्यूलर 'पहला' कार्य लेता है। असल में कोई 'आखिरी' और 'पहला' नहीं है - यह केवल कार्यों की एक गोलाकार सूची है और शेड्यूलर बिना अंत के उन्हें चलाता है। आपके पास विंडो सिस्टम में विंडो की एक सूची भी हो सकती है और कुछ कुंजी कमांड के साथ आप अगली विंडो पर स्विच करेंगे। खिड़कियों की सूची परिपत्र हो सकता है।

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

चूंकि सर्कुलर डेटा संरचनाओं को बनाना आसान है, इसलिए कोई भी इंटरैक्टिव प्रोग्रामिंग के दौरान ऐसा कर सकता है। यदि आप बिल्ट-इन रूटीन के साथ एक गोलाकार डेटा संरचना मुद्रित करते हैं तो प्रिंटर इसे संभाल सकता है, तो यह एक अच्छा विचार होगा, अन्यथा यह हमेशा के लिए एक परिपत्र सूची मुद्रित कर सकता है ...

Answer 2

उदाहरण के लिए एक डबल लिंक्ड सूची डेटा संरचना योजना/LISP बिंदु दृश्य में "परिपत्र" है, यानी यदि आप विपक्षी संरचना को मुद्रित करने का प्रयास करते हैं तो आपको बैक्रेरेंस प्राप्त होते हैं, यानी "चक्र"। तो यह वास्तव में डेटा संरचनाओं के बारे में नहीं है जो "छल्ले" जैसा दिखते हैं, किसी भी डेटा संरचना जहां आपके पास कुछ प्रकार के बैकपॉइंटर्स हैं, योजना/एलआईएसपी परिप्रेक्ष्य से "परिपत्र" है।

एक "सामान्य" LISP सूची एकल जुड़ा हुआ है, जिसका अर्थ है कि सूची के अंदर से किसी आइटम को हटाने के लिए एक विनाशकारी उत्परिवर्तन ओ (एन) ऑपरेशन है; डबल लिंक्ड सूचियों के लिए यह ओ (1) है। यह डबल लिंक्ड सूचियों की "हत्यारा सुविधा" है, जो योजना/LISP संदर्भ में "परिपत्र" हैं।

Answer 3

क्या आपने कभी एकाधिकार खेला है?

काउंटर और मॉड्यूलो के साथ गेम खेलने के बिना और इस तरह, आप खेल के कंप्यूटर कार्यान्वयन में एकाधिकार बोर्ड का प्रतिनिधित्व कैसे करेंगे? एक परिपत्र सूची एक प्राकृतिक है।

Answer 4

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

एक परिपत्र सूची के साथ

, तो आप निश्चित लंबाई कतार का एक प्रकार हो सकता है।

सेटअप लंबाई 5 का एक परिपत्र सूची:

> (import (srfi :1 lists)) 
> (define q (circular-list 1 2 3 4 5)) 

की सूची में नंबर जोड़ने करते हैं:

> (set-car! q 6) 

अब, चलो करते हैं कि इस सूची के अंतिम तत्व:

> (set! q (cdr q)) 

सूची प्रदर्शित करें:

> (take q 5) 
(2 3 4 5 6) 

तो आप इसे एक कतार के रूप में देख सकते हैं जहां तत्व सूची के अंत में प्रवेश करते हैं और सिर से हटा दिए जाते हैं।

की सूची में 7 जोड़ें:

> (set-car! q 7) 
> (set!  q (cdr q)) 
> (take q 5) 
(3 4 5 6 7) 

आदि ...

फिर भी, यह एक तरह से है कि मैं परिपत्र सूचियों का उपयोग किया है है।

मैं इस तकनीक का उपयोग OpenGL demo में करता हूं जिसे मैंने Processing book में एक उदाहरण से पोर्ट किया था।

एड

Answer 5

एक परिपत्र सूचियों का उपयोग, जब नक्शे के srfi -1 संस्करण का उपयोग कर मूल्यों "दोहराने" के लिए है। उदाहरण के लिए, lst के प्रत्येक तत्व को val जोड़ने के लिए, हम लिख सकते हैं:

(map + (circular-list val) lst) 

उदाहरण के लिए:

(map + (circular-list 10) (list 0 1 2 3 4 5)) 

रिटर्न:

(10 11 12 13 14 15) 

बेशक

, आप से ऐसा कर सकता है को (lambda (x) (+ x val)) के साथ बदलना, लेकिन कभी-कभी उपरोक्त मुहावरे आसान हो सकता है। ध्यान दें कि यह केवल नक्शा के srfi-1 संस्करण के साथ काम करता है, जो विभिन्न आकारों की सूचियों को स्वीकार कर सकता है।