PHP में सरणियों को कैसे व्यवस्थित किया जाता है

पिछले लेख में मैंने चर के बारे में बात की थी, अब हम सरणियों के बारे में बात करेंगे।

PHP स्तर पर सरणियाँ क्या हैं?

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

PHP सरणियाँ एक महान एक आकार-फिट-सभी डेटा संरचना हैं। लेकिन सभी एक आकार-फिट-सभी <कुछ भी> की तरह, जैक-ऑफ-ऑल-ट्रेडों का मतलब आमतौर पर कोई भी नहीं होता है।

पत्र का लिंक

(चित्र बाल्टी के साथ एक हैशटेबल दिखाता है, वी। वासंतोसेव)

और यहां हम शुरू करते हैं - चलो प्रत्येक सम्मिलित मूल्य द्वारा खपत की गई मेमोरी और समय को मापने की कोशिश करते हैं। हम निम्नलिखित लिपियों का उपयोग करके ऐसा करेंगे:

// time.php $ar = array(); $t = 0; for ($i = 0; $i < 9000; ++$i) { $t = microtime(1); $ar[] = 1; echo $i . ":" . (int)((microtime(1) - $t) * 100000000) . "\n"; } // memory.php $ar = array(); $m = 0; for ($i = 0; $i < 9000; ++$i) { $m = memory_get_usage(); $ar[] = 1; echo $i . ":" . (memory_get_usage() - $m) . "\n"; } 

ये स्क्रिप्ट php time.php > time और php memory.php > memory , और उन पर रेखांकन php memory.php > memory , क्योंकि बहुत अधिक डेटा है और संख्याओं को लंबे समय तक देखते हैं (समय डेटा को कई बार एकत्र किया गया था और ग्राफ पर अनावश्यक पंपों से बचने के लिए संरेखित किया गया था)।


(एक्स अक्ष पर - सरणी में एल-टूव की संख्या)

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

और इसे कैसे लागू किया जाता है?

वास्तव में, PHP में सरणियों को लागू करने के लिए, हम पूरी तरह से मानक हैश टेबल डेटा संरचना का उपयोग करते हैं, जिसे हम कार्यान्वयन विवरण के बारे में बात करेंगे।

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

क्यों
हमारे लिए
बाल्टी की जरूरत है
और कहाँ
हमारे लिए
उन्हें लेटाओ

हश टेबल में दो मुख्य इकाइयाँ हैं, पहली हैश टेबल है और दूसरी है बकेट (इसके बाद बाल्टी, ताकि ऊब न हो)।

बाल्टियाँ स्वयं मानों को संचित करती हैं, अर्थात् प्रत्येक मान की अपनी बाल्टी होती है। लेकिन इसके अलावा, मूल कुंजी को बाल्टी में संग्रहीत किया जाता है, अगले और पिछले बाल्टी को इंगित करता है (उन्हें सरणी की व्यवस्था करने की आवश्यकता होती है, क्योंकि PHP में चाबियाँ किसी भी क्रम में आप चाहें जा सकती हैं), और, फिर से, कुछ और।

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

लेकिन सबसे दिलचस्प बात यह है कि इन बाल्टी को हैश टेबल में कैसे संग्रहीत किया जाता है।

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

• यदि कुंजी स्ट्रिंग है, तो स्ट्रिंग को पूर्णांक- (DJBX33A हैश एल्गोरिथम का उपयोग किया जाता है) के लिए हैशेड किया गया है:
  
  • हैश का मूल मूल्य जादू 5381 के रूप में लिया जाता है
  • प्रत्येक प्रमुख प्रतीक के लिए, हैश को 33 से गुणा करें और ASCII में वर्ण संख्या जोड़ें
• एक मुखौटा (बिट वाइज) हमेशा परिणामी संख्यात्मक कुंजी पर लागू होता है, जो हमेशा सरणी के आकार के बराबर होता है (जो बाल्टी के साथ होता है) 1
• नतीजतन, इस कुंजी का उपयोग इंडेक्स के रूप में किया जा सकता है ताकि सरणी से बकेट को वांछित पॉइंटर प्राप्त किया जा सके

मास्क के बारे में: मान लीजिए कि व्यूअर के सरणी में 4 तत्व हैं, इसलिए मास्क तीन है, जो कि बाइनरी सिस्टम में 11 है।
अब, अगर हमें कुंजी के रूप में 123 (1111011) जैसा नंबर मिलता है, तो मास्किंग के बाद हमें 3 (3 & 123) मिलता है, इस नंबर को पहले से ही एक सूचकांक के रूप में इस्तेमाल किया जा सकता है।

उसके बाद, हम हाश टेबल में चाबियाँ 54 और 90 के साथ तत्वों को जोड़ने की कोशिश करेंगे, मास्क 3 के साथ। और ये दोनों चाबियां मास्किंग के बाद दो के बराबर होंगी।

टक्करों के साथ क्या करना है?

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



आइए 54 और 90 की चाबियाँ के साथ हमारे मामले में वापस जाएं, और मुखौटा 3. आपके द्वारा 54 जोड़ने के बाद, एचटी संरचना कुछ इस तरह दिखाई देगी:

 { nTableSize: 4, //      nTableMask: 3, //  nNumOfElements: 1, //    HT nNextFreeElement: 55, //    ,         ( ) ..., arBuckets: [ NULL, NULL, 0xff0, // ,     Bucket,      NULL ] } 0xff0: { h: 54, //   nKeyLength: 0, //   ,      pData: 0xff1, //   ,      zval ... } 

अब 90 की कुंजी के साथ एक तत्व जोड़ें, अब सब कुछ इस तरह दिखेगा:

 { nTableSize: 4, nTableMask: 3, nNumOfElements: 2, nNextFreeElement: 91, ..., arBuckets: [ NULL, NULL, 0xff0, //       Bucket NULL ] } 0xff0: { h: 54, pListNext: 0xff2, //      Bucket   ( ) pNext: 0xff2, //     Bucket     ... } 0xff2: { h: 90, pListLast: 0xff0, //    pLast: 0xff0, //       ... } 

अब nTableSize ओवरफ्लो होने से पहले कुछ तत्व जोड़ते हैं (मैं आपको याद दिलाता हूं कि ओवरफ्लो केवल तभी होगा जब nNumOfElements> nTableSize)।
चाबियाँ 0, 1, 3 वाले तत्व जोड़ें (जो वहां नहीं थे, और मास्क लगाने के बाद भी वे वही रहेंगे), यही होगा:

 { nTableSize: 8, //     (    ) nTableMask: 7, nNumOfElements: 5, nNextFreeElement: 91, //     ..., arBuckets: [ //       ,         0xff3, // key = 0 0xff4, // key = 1 0xff2, // key = 90 -     90 (  90 & 7 = 2),       6-  0xff5, // key = 3 NULL, NULL, 0xff0, // key = 54 NULL ] } 0xff0: { h: 54, pListNext: 0xff2, //    ,     pNext: NULL, //     ... } 0xff2: { h: 90, pListNext: 0xff3, pListLast: 0xff0, pLast: NULL, ... } 0xff3: { h: 0, pListNext: 0xff4, pListLast: 0xff2, ... } 0xff4: { h: 1, pListNext: 0xff5, pListLast: 0xff3, ... } 0xff5: { h: 3, pListNext: NULL, //     pListLast: 0xff4, ... } 

सरणी ओवरफ्लो होने के बाद क्या होता है, इसे रिहाश कहा जाता है। अनिवार्य रूप से, सभी मौजूदा बाल्टियों (pListNext के माध्यम से) पर पुनरावृत्ति, अपने पड़ोसियों (टकरावों) को असाइन करते हुए, और arBuckets में उनके संदर्भ जोड़ते हैं।

लेकिन वास्तव में क्या होता है जब एक तत्व कुंजी द्वारा प्राप्त होता है? पिछले एल्गोरिथम में कुछ और जोड़ा जाएगा:

• यदि कुंजी स्ट्रिंग है, तो स्ट्रिंग को पूर्णांक- (DJBX33A हैश एल्गोरिथम का उपयोग किया जाता है) के लिए हैशेड किया गया है:
  
  • हैश का मूल मूल्य जादू 5381 के रूप में लिया जाता है
  • प्रत्येक प्रमुख प्रतीक के लिए, हैश को 33 से गुणा करें और ASCII में वर्ण संख्या जोड़ें
• एक मुखौटा (बिट वाइज) हमेशा परिणामी संख्यात्मक कुंजी पर लागू होता है, जो हमेशा सरणी के आकार के बराबर होता है (जो बाल्टी के साथ होता है) 1
• हम एक सूचकांक पर एक बाल्टी निकालते हैं
• यदि इस बाल्टी की कुंजी वांछित के बराबर है, तो खोज पूरी हो गई है, अन्यथा:
• लूप में हम pNext (यदि यह मौजूद है) से एक बाल्टी लेते हैं और देखें कि क्या कुंजी बराबर है

इसलिए जब तक या तो pNext में बाल्टियाँ बाहर निकल जाती हैं (तब नोटिस फेंका जाएगा), या जब तक एक मैच नहीं मिलता है।

यह ध्यान देने योग्य है कि PHP में लगभग सब कुछ इस हैशटेबल संरचना पर अकेले बनाया गया है: किसी भी दायरे में पड़े हुए सभी चर वास्तव में HT, सभी वर्ग विधियों, सभी वर्ग क्षेत्रों, यहां तक ​​कि वर्ग परिभाषाओं में स्वयं झूठ बोलते हैं, HT में झूठ बोलते हैं। यह वास्तव में एक बहुत ही लचीली संरचना है। अन्य बातों के अलावा, HT लगभग समान गति प्राप्त करने / डालने / हटाने की सुविधा प्रदान करता है और तीनों की जटिलता O (1) है, लेकिन टकराव के मामले में एक छोटे से ओवरहेड के लिए चेतावनी के साथ।

वैसे, यहाँ मैंने PHP में ही एक हैश टेबल लागू किया है। खैर, यह है कि, PHP में PHP सरणियों को लागू किया =)