डेटा संरचनाएं, PHP

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

डेटा स्ट्रक्चर्स या एब्सट्रैक्ट डेटा टाइप ( ADT ) एक ऐसा मॉडल है जिसे ऑपरेशन के एक सेट के रूप में परिभाषित किया जाता है जिसे खुद पर लागू किया जा सकता है और इन ऑपरेशनों के परिणाम किस सीमा तक सीमित होते हैं।
हममें से अधिकांश लोग रोजमर्रा की जिंदगी में स्टैक और कतार के साथ सामना करते हैं, लेकिन सुपरमार्केट कतार और डेटा संरचना के बीच क्या आम है? इसमें हम इस लेख को समझने की कोशिश करेंगे, जिसमें पेड़ों का भी वर्णन होगा।




UPD : s01e02

1. अनेकता
2. बारी
3. लकड़ी

अनेकता

स्टैक को आमतौर पर वस्तुओं के एक निश्चित समूह के रूप में वर्णित किया जाता है, जिन्हें एक साथ समूहीकृत किया जाता है, जहां सामान्य सेट का प्रत्येक तत्व एक के बाद एक जाता है - पुस्तकों या ट्रे का एक ढेर। कंप्यूटर विज्ञान में, स्टैक ऑब्जेक्ट्स का एक संग्रह होता है, जिसमें एक सामान्य नियम होता है: स्टैक पर रखी गई अंतिम वस्तु सामान्य सूची से प्राप्त होने वाली पहली होती है। इस नियम को "लास्ट एंटर, फर्स्ट एंटर" या LIFO भी कहा जाता है। एक अनुवर्ती नियम है - पहला अंदर आया, पहला बाहर आया ( एफआईएफओ ), लेकिन बाद में उस पर और अधिक।
यह नियम, LIFO, का उपयोग किया जाता है, उदाहरण के लिए, सिगरेट, मिठाई के लिए वेंडिंग मशीनों में - वहां भरी हुई अंतिम वस्तु पहले जारी की जाएगी।

स्टैक की एक सार परिभाषा एक सूची है, जिसके लिए सभी ऑपरेशन एक छोर के सापेक्ष परिभाषित होते हैं, अर्थात्। ढेर के ऊपर।
स्टैक को परिभाषित करने वाले मूल संचालन:

• init - एक स्टैक बनाएं।
• धक्का - स्टैक की शुरुआत (शीर्ष) में एक तत्व जोड़ें, बाकी 1 स्थिति को नीचे ले जाते हुए।
• पॉप - स्टैक से एक तत्व (और हटाएं) (ऊपर से)।
• शीर्ष - स्टैक के पहले तत्व पर मूल्य हटाएं (हटाए बिना)।
• ismmpty - खालीपन के लिए स्टैक की जाँच करें।

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

यह जानते हुए कि हमारे स्टैक को LIFO और इसके बुनियादी कार्यों के रूप में परिभाषित किया गया है, हम अपने स्टैक को एक सरणी के माध्यम से लिख सकते हैं, खासकर जब से हमारे पास पहले से ही इसके लिए बुनियादी धक्का और पॉप ऑपरेशन हैं। हमारा उदाहरण होगा:

<?php class ReadingList { protected $stack; protected $limit; public function __construct($limit = 10) { //   $this->stack = array(); //        $this->limit = $limit; } public function push($item) { // ,      if (count($this->stack) < $this->limit) { //       array_unshift($this->stack, $item); } else { throw new RunTimeException(' !'); } } public function pop() { if ($this->isEmpty()) { //     throw new RunTimeException(' !'); } else { //     return array_shift($this->stack); } } public function top() { return current($this->stack); } public function isEmpty() { return empty($this->stack); } } 

इस उदाहरण में, हमने array_push () और array_pop () के बजाय PHP फ़ंक्शन array_unshift () और array_shift () का उपयोग किया है, इसलिए हमारे पास पहले स्टैक तत्व हमेशा शीर्ष पर होता है, अन्यथा वर्टेक्स स्टैक का nth तत्व होगा। ज्यादा अंतर नहीं है। अब हमारे स्टैक में कुछ तत्व जोड़ें:

 <?php $myBooks = new ReadingList(); $myBooks->push('A Dream of Spring'); $myBooks->push('The Winds of Winter'); $myBooks->push('A Dance with Dragons'); $myBooks->push('A Feast for Crows'); $myBooks->push('A Storm of Swords'); $myBooks->push('A Clash of Kings'); $myBooks->push('A Game of Thrones'); 

अब, कुछ तत्वों को इसमें से निकालते हैं:

 <?php echo $myBooks->pop(); //    'A Game of Thrones' echo $myBooks->pop(); //    'A Clash of Kings' echo $myBooks->pop(); //    'A Storm of Swords' 

अब हमारे पास जो स्टैक है, वह सबसे ऊपर है।

 <?php echo $myBooks->top(); //  'A Feast for Crows' 

यदि आप पॉप () विधि को फिर से कॉल करते हैं, तो स्टैक से "ए फेस्ट फॉर कॉव्स" हटा दिया जाएगा। यदि आप धक्का देते हैं, और फिर तुरंत पॉप करते हैं, तो स्टैक नहीं बदलेगा, क्योंकि हमारा स्टैक "अंतिम लॉग इन, पहले लॉग इन" के आधार पर काम करता है। यदि हम स्टैक से आइटम खींचना जारी रखते हैं, तो जल्दी या बाद में हमें एक संदेश के साथ एक अपवाद मिलेगा कि स्टैक खाली है।

SPLStack

PHP (SPL Extension) हमें विभिन्न डेटा संरचनाओं के कार्यान्वयन के साथ प्रदान करता है, जिसमें SplStack भी शामिल है, जो संस्करण 5.3 से शुरू होता है। हम अपनी रीडिंगलिस्ट को विरासत में प्राप्त करके बना सकते हैं:

 <?php class ReadingList extends SplStack { } 

SplStack हमें पहले से परिभाषित की तुलना में कुछ अधिक विधियां प्रदान करता है, क्योंकि SplStack पुनरावृत्ति को लागू करने के लिए क्षमता (स्टैक में तत्वों की संख्या) की दोगुनी लिंक की गई सूची को लागू करता है।

एक लिंक की गई सूची, जो अनिवार्य रूप से एक अलग सार संरचना है, नोड्स की एक सूची है, जिनमें से प्रत्येक में अगले ऑब्जेक्ट के लिए एक संकेतक है। इस संरचना का प्रतिनिधित्व इस तरह से किया जा सकता है, अप्रत्यक्ष गणना के साथ:



एक दोहरी लिंक की गई सूची में, प्रत्येक नोड में दो बिंदु होते हैं - सूची में पिछले और अगले नोड्स के लिए। यह संरचना आपको दो दिशाओं में खोज करने की अनुमति देती है:



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

बारी

तो हम "पहले आए, पहले निकले" या फीफो आए। जो कोई वास्तविक लाइन-अप में खड़ा था, वह जानता है कि जिसने पहले स्थान लिया था वह पहले छोड़ देगा। एक अपवाद वह वस्तु है जिसे आप सिर्फ हस्ताक्षर करते हैं, पूछते हैं, आदि।

कतारों के लिए बुनियादी ऑपरेशन हैं:

• init - एक कतार बनाएँ।
• enqueue - कतार के अंत (पूंछ) में एक तत्व जोड़ें।
• dequeue - एक तत्व को कतार (सिर) की शुरुआत से हटा दें।
• isEmpty - खालीपन के लिए कतार की जाँच करें।

PS उन लोगों के लिए जो प्रोलॉग से परिचित हैं - इस मामले में, पूंछ में सूची के सभी तत्व शामिल नहीं हैं, सिवाय सिर के।

PHP हमें SplQueue वर्ग (दोगुनी लिंक की गई सूची) प्रदान करता है, केवल इस मामले में सूची का प्रमुख अंतिम तत्व है। हमारे रीडिंगलिस्ट को एक कतार के रूप में परिभाषित करें:

 <?php class ReadingList extends SplQueue { } $myBooks = new ReadingList(); //       $myBooks->enqueue('A Game of Thrones'); $myBooks->enqueue('A Clash of Kings'); $myBooks->enqueue('A Storm of Swords'); 

SplQueue SplDoublyLinkedList से विरासत में मिलता है और एक सरणी के रूप में एक्सेस इंटरफ़ेस को लागू करता है, इस प्रकार सरणियों के माध्यम से हमारी कतार और ढेर तक पहुंच की अनुमति देता है:

 <?php $myBooks[] = 'A Feast of Crows'; $myBooks[] = 'A Dance with Dragons'; 

कतार से कुछ तत्वों को हटाएं:

 <?php echo $myBooks->dequeue() . "\n"; //    'A Game of Thrones' echo $myBooks->dequeue() . "\n"; //    'A Clash of Kings' 

enqueue () पुश के लिए एक उपनाम है (), हालांकि dequeue () पॉप के लिए एक उपनाम नहीं है () ! क्यू के संदर्भ में पॉप () का एक अलग व्यवहार है, क्योंकि अगर हम पॉप () का उपयोग करते हैं, तो यह कतार की पूंछ (ए डांस विथ ड्रेगन) के तत्व को हटा देगा, क्योंकि कतार में मुख्य चीज फीफो नियम है।

आप देख सकते हैं (बिना डिलीट किए) कौन सा तत्व नीचे () विधि के माध्यम से सूची का प्रमुख है:

 <?php echo $myBooks->bottom() . "\n"; //  'A Storm of Swords' 

पेड़

ADT नियंत्रण आमतौर पर 3 ऑपरेशन के लिए नीचे आता है: संरचना में तत्वों को सम्मिलित करना, संरचना से तत्व मूल्य को हटाना और प्राप्त करना। स्टैक और कतारों के लिए, ये ऑपरेशन स्थिति निर्भर (xIFO) हैं। लेकिन क्या होगा अगर हमें मूल्य द्वारा जानकारी प्राप्त करने की आवश्यकता है?

कल्पना कीजिए कि हमारे पास ऐसी प्लेट है (तत्वों का क्रम मायने नहीं रखता):



जाहिर है, इस मामले में स्टैक या कतार हमारी मदद नहीं करेगी, क्योंकि हमें सभी मूल्यों को दरकिनार करना होगा अगर हमें इसकी आवश्यकता है तो यह अंत में अनुपस्थित है या बिल्कुल भी अनुपस्थित है। मान लीजिए कि आप जो आइटम चाहते हैं वह सूची में है। फिर इसकी खोज के लिए हमें औसत, n / 2 तत्वों से गुजरना होगा, जहाँ n पूरी सूची की लंबाई है। अधिक सूची - बाईपास के लिए अधिक समय। इस खोज समस्या को हल करने के लिए, आपको किसी तरह डेटा को व्यवस्थित करने की आवश्यकता है ताकि संरचना द्वारा खोज सरल हो जाए। और यहां पेड़ दिखाई देते हैं।

इस संरचना का एक सार उदाहरण निम्नलिखित कार्यों के साथ एक तालिका है:

• create - एक खाली टेबल बनाएं।
• सम्मिलित करें - तालिका में एक तत्व जोड़ें।
• हटाना - तालिका से कोई आइटम हटाना।
• पुनः प्राप्त करें - तालिका में एक तत्व ढूंढें।

हां, यह डेटाबेस से प्रसिद्ध CRUD (क्रिएट रीड अपडेट डिलीट) के समान है, क्योंकि पेड़ और डेटाबेस निकटता से संबंधित हैं।

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

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



जैसा कि आप इस तस्वीर से देख सकते हैं, पेड़ एक पदानुक्रमित संरचना है जहां एक माता-पिता → नोड्स के बीच बाल संबंध है। वंश के बिना एक नोड एक अंत नोड (पत्ती) है, माता-पिता के बिना एक वंशज पेड़ की जड़ है, नोड्स के बीच कनेक्शन किनारों हैं। दो वंशों के साथ एक नोड सबसे सरल पेड़ है, और इसके आधार पर, हम इस तरह के नोड्स की पुनरावर्ती सूची के रूप में पेड़ का प्रतिनिधित्व कर सकते हैं। यह ध्यान दिया जाना चाहिए कि इसकी संरचना में पेड़ एक डबल लिंक की गई सूची जैसा दिखता है।

इसलिए, हमारे पेड़ का वर्णन इस प्रकार किया जा सकता है:

 <?php class BinaryNode { public $value; //   public $left; //    BinaryNode public $right; //    BinaryNode public function __construct($item) { $this->value = $item; //   -  $this->left = null; $this->right = null; } } class BinaryTree { protected $root; //   public function __construct() { $this->root = null; } public function isEmpty() { return $this->root === null; } } 

नए मान डालें

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

सादगी के लिए, हम सबसे सरल कार्यान्वयन के कुछ नियमों को निरूपित करते हैं: वर्तमान मूल्य से कम सब कुछ बाईं ओर जाता है, अधिक - दाईं ओर।
दोहराए जाने से बाहर रखा जाएगा:

1. यदि पेड़ खाली है, तो पेड़ की जड़ के रूप में [new_node] डालें (जाहिर है!)
2. अलविदा (पेड़ खाली नहीं है):
   
   • 2 ए। यदि ([वर्तमान नोड] खाली है) - यहां पेस्ट करें और रोकें;
   • 2 बी। अगर ([new_node]> [करंट नोड]) - दाईं ओर बार-बार [new_node] डालने की कोशिश करें और चरण 2 दोहराएं
   • 2c। यदि ([new_node] <[करंट नोड]) - बाईं ओर [new_node] डालने की कोशिश करें और चरण 2 को दोहराएं
   • 2 डी। अन्यथा, मूल्य पहले से ही पेड़ में है
   
   

 <?php class BinaryTree { ... public function insert($item) { $node = new BinaryNode($item); if ($this->isEmpty()) { //  1 $this->root = $node; } else { //  1 $this->insertNode($node, $this->root); } } protected function insertNode($node, &$subtree) { if ($subtree === null) { //  2 $subtree = $node; } else { if ($node->value > $subtree->value) { //  2b $this->insertNode($node, $subtree->right); } else if ($node->value < $subtree->value) { //  2c $this->insertNode($node, $subtree->left); } else { //  ,  2d } } } } 

नोड्स को हटाना एक पूरी तरह से अलग कहानी है और प्रभावित नहीं होगी। शायद कुछ और समय।

पेड़ की टहनी

याद रखें कि हमने रूट से कैसे शुरू किया था और एक खाली नोड को खोजने के लिए नोड के बाद एक पेड़, नोड के माध्यम से चला गया। 4 मुख्य पेड़ ट्रैवर्सल रणनीतियाँ हैं:

• प्री-ऑर्डर (प्रत्यक्ष आदेश) - वर्तमान नोड को संसाधित करना, और फिर बाईं और दाईं ओर बढ़ना।
• इन-ऑर्डर (सममित) - पहले बाईं ओर से गुजरें, वर्तमान नोड की प्रक्रिया करें और दाईं ओर से बायपास करें।
• पोस्ट-ऑर्डर - बाएं और दाएं पक्षों को उल्टा करें, फिर वर्तमान मूल्य को संसाधित करें।
• स्तर-क्रम (विस्तृत) - वर्तमान मूल्य को संसाधित करना, फिर वंशजों को संसाधित करना और अगले स्तर तक ले जाना।

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

यह समझने के लिए कि एक सममित मार्ग कैसे काम करता है, आपको हमारे उदाहरण को थोड़ा संशोधित करने की आवश्यकता है:

 <?php class BinaryNode { ... //      public function dump() { if ($this->left !== null) { $this->left->dump(); } var_dump($this->value); if ($this->right !== null) { $this->right->dump(); } } } class BinaryTree { ... public function traverse() { //        $this->root->dump(); } } 

निष्कर्ष

मैं हर किसी को धन्यवाद देता हूं जो निष्कर्ष पर पढ़ता है, थोड़ा अधिक पाठ और चित्र :)

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

इसके अलावा kpuzuc के इस लेख पर ध्यान देने योग्य है
इन संरचनाओं का विज़ुअलाइज़ेशन, लिंक जिन्हें टेंग्रो से एक पोस्ट में पाया जा सकता है

यहाँ से कॉपी किए गए इन संरचनाओं के कार्यान्वयन के प्रदर्शन के बेंचमार्क

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

पीएस हमेशा की तरह मूल के पाठ और अनुवाद में पीएम त्रुटियों को स्वीकार किया जाता है।