हैश खोज का उपयोग करें, सरणी खोज नहीं

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

अर्रे खोज

आमतौर पर चेक इस तरह से होता है:

 <?php $words = get_all_words_in_text($text); $badWords = ['$$$$', '@#$%', 'crud' /** ... */ ]; foreach ($words as $word) { if (in_array(strtolower($word), $badWords)) { echo 'Found bad word: ' . $word . "\n"; } } 

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

हैश सर्च

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

यदि हम बुरे शब्दों की सारणी की संरचना को बदल देते हैं ताकि उसके मान कुंजियाँ बन जाएँ, और इन कुंजियों के लिए मान बिलकुल true , तो हम isset() फ़ंक्शन का उपयोग कर सकते हैं और गति में उल्लेखनीय वृद्धि प्राप्त कर सकते हैं।

 <?php $words = get_all_words_in_text($text); $badWords = [ '$$$$' => true, '@#$%' => true, 'crud' => true // ... ]; foreach ($words as $word) { if (isset($badWords[strtolower($word)])) { echo 'Found bad word: ' . $word . "\n"; } } 

प्रदर्शन परीक्षण

आइए नए तरीके से परीक्षण करने का प्रयास करें। मैंने एक साधारण परीक्षण लिखा जो विधियों के लिए समान डेटा सेट पर बिताए गए समय को दिखाएगा: "सरणी खोजें" और "हैश द्वारा खोजें"।

 <?php $total = 10000; $paragraph = 'this is a sentence. Crud! $$$$!'; $words = explode(' ', $paragraph); $badWordList = ['$$$$', '@#$%', 'crud', 'fud', 'fudd', 'dud']; $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { in_array(strtolower($word), $badWordList); } } echo "in_array: " . (microtime(true) - $s) . "\n"; $badWordHash = [ '$$$$' => true, '@#$%' => true, 'crud' => true, 'fud' => true, 'fudd' => true, 'dud' => true ]; $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { isset($badWordHash[strtolower($word)]); } } echo "hash: " . (microtime(true) - $s) . "\n"; 

जैसा कि आप लिस्टिंग से देख सकते हैं, परीक्षण 10,000 पुनरावृत्तियों का उपयोग करता है। परिणाम इस प्रकार है:

 in_array: 0.033491134643555 hash: 0.0069370269775391 

जैसा कि आप देख सकते हैं, हैश खोज ने सरणी की खोज की तुलना में 480% की वृद्धि प्राप्त की।

यह समझना महत्वपूर्ण है कि जैसे ही निषिद्ध शब्दों की संख्या बढ़ जाती है, in_array() फ़ंक्शन के साथ सरणी को खोजने के लिए आवश्यक समय in_array() । लेकिन isset() तत्वों की संख्या पर निर्भर नहीं करता है, और इसका संचालन समय स्थिर रहेगा। मैं तुम्हें दिखाता हूं कि मेरा क्या मतलब है। निम्नलिखित उदाहरण में, निषिद्ध शब्दों की सूची में 10,000 तत्व शामिल होंगे।

 <?php $total = 10000; $paragraph = 'this is a sentence. Crud! $$$$!'; $words = explode(' ', $paragraph); //     $sequence = []; for ($j = 0; $j < 10000; $j++) { $sequence[] = 'a' . $j; } $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { in_array(strtolower($word), $sequence); } } echo "in_array: " . (microtime(true) - $s) . "\n"; //     $hash = array_fill_keys($sequence, true); $s = microtime(true); for ($j = 0; $j < $total; $j++) { foreach ($words as $word) { isset($hash[strtolower($word)]); } } echo "hash: " . (microtime(true) - $s) . "\n"; 

गति में अंतर बहुत बेहतर दिखाई दे रहा है। हैश खोज एक सरणी खोज की तुलना में 3 162 प्रतिशत तेज है।

 in_array: 20.464313983917 hash: 0.0064699649810791 

सामान्य तौर पर, कोई नई बात नहीं है

यह कोई नया विचार नहीं है। यह कई भाषाओं में एक काफी सामान्य दृष्टिकोण है। मुझे हाल ही में अचानक एहसास हुआ कि मैं लगातार " प्रोग्रामिंग ऑन लुआ " पुस्तक पढ़ते हुए ऐसे कार्यों के लिए हैश खोज का उपयोग करता हूं।

अगली बार जब आप जांच करने के लिए in_array() का उपयोग करते हैं, तो सोचें कि क्या आप काम की गति in_array() यदि आप साहचर्य सरणी की कुंजी पर isset() फ़ंक्शन का उपयोग करते हैं।