हम अच्छी तरह से ज्ञात एल्गोरिदम का उपयोग किए बिना एक स्टैक में सुई की तलाश कर रहे हैं

सुई खोजने की कौन सी विधि तेज है? एक तिनके के माध्यम से क्रमबद्ध करें, या गलती से इसके लिए देखो?

मुझे लगता है कि सबसे अच्छा तरीका प्रयोग है, दुर्भाग्य से मेरे पास एक बाधा नहीं है, लेकिन मेरे पास बुनियादी प्रोग्रामिंग ज्ञान, एक Arduino माइक्रोकंट्रोलर, कोड लिखने के लिए एक सुविधाजनक वातावरण है, इसलिए हर कोई इसे दोहरा सकता है।

एक कदम "समझ"

मुझे कौन सा डेटा प्राप्त करना है? सही समाधान खोजने में समय व्यतीत हुआ। केवल निष्पादन प्रयोग की बारीकियों के कारण उपयुक्त नहीं है, आपको कई बार विधि की जांच करने की आवश्यकता है, फिर जिस समय में मेरी रुचि है वह औसत है। मैंने इस पर फैसला किया। अगला चरण है कि कितने और कौन से चर को घोषित करना है। समय की राशि को स्टोर करने के लिए हमें प्रत्येक विधि के लिए एक अलग चर की आवश्यकता होती है, इसे कॉल करते हैं:

"Time_poslMetod" और "Time_randMetod"।

पुनरावृत्तियों की संख्या पर एक निरंतरता की आवश्यकता है:

# डेफिन इटर 1000।

आउटपुट मान पुनरावृत्तियों की संख्या से पहले को विभाजित करके प्राप्त किया जाता है।

#define Iter 10000 #define cell 100 uint8_t potenArr[cell]; //  uint8_t needle = 0; //  uint32_t startTime = 0; //    uint32_t endTime = 0; //    uint32_t calculationStartTime = 0; uint32_t calculationEndTime = 0; uint32_t Time_poslMetod = 0; uint32_t Time_randMetod = 0; 

चरण दो "कोड लिखें"

के लिए लूप पुनरावृत्तियों की संख्या का प्रबंधन करता है, इसके अंदर हम सुई को धड़ में "फेंक" करेंगे, खोज करेंगे, प्रत्येक विधि के लिए समय को अलग से मापेंगे, समय को "वैश्विक" (Time_poslMetod / Time_andandMetod) चर (भविष्य के लिए) में सहेजें।

  //   Iter  for(uint32_t j = 0; j <= Iter; j++){ //      cleanArr(); //     needle = random(cell + 1); potenArr[needle] = 1; //          poslMetod(); randMetod(); } 

यह मेरे तरीकों की तरह लग रहा है।

अनुक्रमिक विधि:

 void poslMetod(){ startTime = millis(); for(uint16_t i = 0; i < cell; i++){ if(potenArr[i] == 1){ endTime = millis() - startTime; break; } } Time_poslMetod += endTime; } 

बहुत शुरुआत से पहले, हम समय को याद करते हैं, फिर खोज समाप्त होने के समय से इसे घटाते हैं। हम पहले तत्व से अंतिम तक सरणी (स्टैक) के माध्यम से चलाते हैं। जब हम सुई ढूंढते हैं, तो समय लिखें, खोज को पूरा करें, "वैश्विक" (Time_poslMetod) चर में समय जोड़ें और विधि से बाहर निकलें।

यादृच्छिक विधि:

 void randMetod(){ startTime = millis(); for(;;){ uint16_t r = random(cell + 1); if(potenArr[r] == 1){ endTime = millis() - startTime; break; } } Time_randMetod += endTime; } 

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

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

यह सब एक साथ रखना, कोड को चमकाना, समझ के लिए आउटपुट को सुविधाजनक बनाना:

चरण तीन "परिणाम विश्लेषण"

हमें मिलता है:



ईमानदारी से, मैं परिणामों पर हैरान हूं। शर्त लगाते हुए कि समय करीब होगा, मैं हार जाऊंगा।

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