PHP में जुडी सरणियाँ

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

थोड़ा इतिहास

2000 की शुरुआत में डगलस बेसकिंस द्वारा जुडी सरणियों का आविष्कार किया गया था। उनके विकास परियोजना को एचपी द्वारा वित्त पोषित किया गया था, लेकिन लगभग दो साल बाद बंद कर दिया गया था। इस समय के दौरान, चार संस्करण जारी किए गए थे, और बाद के विकास में एक वर्ष से अधिक समय लगा, और इसमें डेवलपर्स जूडी को आधे से गति देने में सक्षम थे, स्मृति की खपत को आधे से कम कर दिया, हालांकि यह एक आसान मूल्य नहीं था: कोड की मात्रा 5 गुना बढ़ी, और इसकी जटिलता - परिमाण का एक क्रम।

जुडी सरणियों के काम करने के लिए एल्गोरिथ्म का पेटेंट कराया गया है , हालांकि, C में मूल कार्यान्वयन LGPL लाइसेंस के तहत आधिकारिक वेबसाइट पर उपलब्ध है।
परियोजना का नाम सिस्टर बेसकिन्स के नाम पर रखा गया था, क्योंकि डेवलपर्स एक बेहतर विकल्प के साथ नहीं आ सकते थे।

पेड़ की गिरफ्तारी

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

जूडी सरणियों के कई प्रकार हैं:

• Judy1 - एक बिटमैप (बिटमैप), सूचकांक एक पूर्णांक (पूर्णांक-> बिट) है;
• जूडीएल - इंडेक्स के रूप में पूर्णांक के साथ एक सरणी (पूर्णांक-> पूर्णांक / सूचक);
• JudySL - एक इंडेक्स (स्ट्रिंग-> पूर्णांक / सूचक) के रूप में स्ट्रिंग के साथ संकेत की एक सरणी;
• जूडीएचएस - बाइट्स के एक सेट के साथ पॉइंटर्स की एक सरणी एक इंडेक्स (बाइट्स-> पूर्णांक / सूचक) के रूप में।

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

मानक

PHP में अंतर्निहित सरणियाँ सार्वभौमिक हैं और, परिणामस्वरूप, कुछ मामलों में बेहद अक्षम हैं। जूडी की तुलना में, उन्हें काफी तुच्छ तरीके से लागू किया जाता है: ये हैश टकराव के मामले में प्रत्येक तत्व के अंदर एक दोगुनी लिंक की गई सूची के साथ हैश एरे हैं। PHP सरणियों PHP चर, अर्थात् स्टोर ज़वल संरचनाओं के संकेत। अधिकांश मामलों में, यह वही है जो उनके लिए आवश्यक है, लेकिन अपवाद हैं।
यह प्रदर्शित करने के लिए कि हमने जूडी का उपयोग करने का निर्णय क्यों लिया, हम जूडी और पीएचपी सरणियों का तुलनात्मक परीक्षण करेंगे। PHP से जूडी के इंटरफ़ेस के रूप में, हम php-judy मॉड्यूल का उपयोग करते हैं, जिसमें ArrayAccess इंटरफ़ेस के कार्यान्वयन के साथ जूडी वर्ग को लागू किया जाता है। परीक्षण में, फॉर्म पूर्णांक -> पूर्णांक (सरणी), जुडी :: INT_TO_INT, जूडी :: INT_TO_MIXED) या पूर्णांक-> बूलियन (जूडी :: BITSET) के सरणियों का निर्माण करें और उन्हें अनुक्रमिक कुंजियों वाले तत्वों से भरें।
पहले, हम समान कोड का उपयोग करके सरणियों के लिए लिखने की गति को मापेंगे:

<?php $arr = array(); for ($i = 0; $i < 10000000; $i++) {  $arr[] = 1; } ?> 

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

फिर हम सरणियों से अनुक्रमिक पढ़ने की गति को मापेंगे:

 <?php /* …*/ /*   ,        */ $arr = array(); for ($i = 0; $i < 10000000; $i++) { $val = $arr[$i]; } ?> 

यहां इंटरेक्टिव चार्ट देखें।
यह ग्राफ से देखा जा सकता है कि जूडी :: बिट्स और जूडी :: INT_TO_INT को पढ़ते समय वे अंतर्निहित PHP सरणी में थोड़ा खो देते हैं। ऐसा इसलिए है क्योंकि ये सरणियाँ PHP के चर (यानी zval) की बजाय क्रमशः बिट और पूर्णांक को संग्रहीत करती हैं। यह वैरिएबल बनाने और भरने का ओवरहेड है जो हमें प्रदर्शन लाभ के लिए लूटता है।
दूसरी ओर, सरणी () और जुडी :: INT_TO_MIXED स्टोर के अंदर बस PHP चर हैं, और उन्हें बनाने में समय खर्च नहीं करना पड़ता है, इसलिए वे गति में लगभग बराबर हैं।

अंत में, हम एरे को भरते समय मेमोरी खपत को मापते हैं और निम्नलिखित ग्राफ प्राप्त करते हैं:


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