() और foreach () के माध्यम से सरणियों के माध्यम से लूप अभिगम की तुलना

मैं php की स्पष्ट विशेषता पर ध्यान आकर्षित करना चाहूंगा।
मान लीजिए कि हमारे पास पूर्णांक सूचकांकों के साथ एक सरणी है

$arr = array( $val1, $val2, ..., $valn ); 

इस सरणी को दो तरीकों से देखा जा सकता है

 foreach($arr as $k => $v ) {...} 

और

 $n = count( $arr ); for($k = 0; $k < $n; $k++ ) {...} 

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

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

तो ऐसा क्यों हो रहा है

आइए php में एक सरणी के आंतरिक भाग को देखें ।
आंतरिक रूप से, Zend कोर में, एक सरणी को कई परस्पर संरचनाओं द्वारा दर्शाया जाता है:

Bucket संरचना सरणी की वर्तमान स्थिति के लिए "सूचक" का वर्णन करती है

 typedef struct bucket { ulong h; //    // (  ) uint nKeyLength; //   ( ) void *pData; //    // [   : (zval **)pos->pData ] void *pDataPtr; struct bucket *pListNext; //      struct bucket *pListLast; //      struct bucket *pNext; //      arBuckets struct bucket *pLast; //      arBuckets const char *arKey; //   ,    } Bucket; typedef Bucket* HashPosition; 

HashTable संरचना - यह आंतरिक अभ्यावेदन में स्वयं सरणी है:

 typedef struct _hashtable { uint nTableSize; uint nTableMask; uint nNumOfElements; //     ulong nNextFreeElement; Bucket *pInternalPointer; Bucket *pListHead; //      Bucket *pListTail; //      Bucket **arBuckets; // ,  . //      //     dtor_func_t pDestructor; zend_bool persistent; unsigned char nApplyCount; zend_bool bApplyProtection; } HashTable; 

यहां तक ​​कि पहले से प्रस्तुत जानकारी भी कारण को समझने के लिए पर्याप्त है। एरे को दोगुनी लिंक की गई सूचियों के रूप में लागू किया जाता है।
संदेह से जुड़ी सूचियाँ त्वरित प्रविष्टि की अनुमति देती हैं, बल्कि त्वरित खोज, लेकिन उनके लिए यादृच्छिक पहुँच एक धीमा ऑपरेशन है।

आइए देखें कि आखिरकार, Zend एक एरे के तत्वों के माध्यम से कैसे पुनरावृत्त होता है।

 //     . int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos) { HashPosition *current = pos ? pos : &ht->pInternalPointer; if (*current) { *current = (*current)->pListNext; return SUCCESS; } else return FAILURE; } //     . //  php   ,    Zend //       . int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos) { HashPosition *current = pos ? pos : &ht->pInternalPointer; if (*current) { *current = (*current)->pListLast; return SUCCESS; } else return FAILURE; } 

यहां, मुझे लगता है, आगे की व्याख्या के बिना सबकुछ स्पष्ट है - वर्तमान तत्व के लिए सूचक को एक सूचक द्वारा अगले तत्व से बदल दिया जाता है, जिस लिंक को वर्तमान एक में संग्रहीत किया जाता है।

अब देखते हैं कि इंडेक्स द्वारा कैसे एक्सेस किया जाता है।

 int zend_hash_index_find(const HashTable *ht, ulong h, void **pData) { uint nIndex; Bucket *p; nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; while (p != NULL) { if ((p->h == h) && (p->nKeyLength == 0)) { *pData = p->pData; return SUCCESS; } p = p->pNext; } return FAILURE; } 

कुछ स्पष्टीकरण यहां दिए गए हैं।
मैं पाठकों को अधिक विस्तृत विवरण के साथ बोर नहीं करना चाहता कि कैसे arBuckets सरणी की arBuckets की arBuckets ( C HashPosition से C सरणी है - Bucket संकेत)।
मैं केवल यह कह सकता हूँ कि यहाँ arBuckets तालिका के आंतरिक हैश का भाग arBuckets जब तक कि वांछित मान नहीं मिलता है।

निष्कर्ष

 foreach($arr as $i => $v ){...} 

सरणी के सभी तत्वों के माध्यम से तेज़ी से पर्याप्त हो जाता है, उन्हें एक-एक करके प्राप्त करना। इस ऑपरेशन की जटिलता ओ (एन) है।

 for($i = 0; $i < $n; $i++ ){...} 

प्रत्येक पुनरावृत्ति पर, यह आंतरिक हैश तालिका में सूचकांक की खोज करता है।

अनुमानित रूप से, पिछले ऑपरेशन की जटिलता अंकगणितीय प्रगति n * (n + 1) / 2 अर्थात के योग द्वारा व्यक्त की जाएगी। और यह O (n ² ) के क्रम का होगा यदि सूचकांक द्वारा मूल्य की खोज करते समय संपूर्ण हैश तालिका को सॉर्ट किया जाएगा। वास्तव में, सभी मूल्यों का चयन नहीं किया जाता है, लेकिन उनमें से केवल एक हिस्सा होता है, इसलिए जटिलता O (n) से O (n ² ) तक भिन्न होगी। और बड़े सरणियों के लिए, यह O (n) के करीब होगा। लेकिन इस मामले में भी, मुख्य पहुंच के साथ एक सरणी पर पुनरावृत्ति एक अधिक संसाधन-गहन ऑपरेशन है।

स्ट्रिंग कुंजी (या मिश्रित - पूर्णांक और स्ट्रिंग) के साथ सरणियों के लिए के रूप में।
उपर्युक्त सभी उनके लिए इस अंतर के साथ भी सही हैं कि एक स्ट्रिंग कुंजी तक पहुंच की गति औसतन 8 (अधिकतम 16) बार एक पूर्णांक से अधिक है