تبحث عن إبرة في مكدس دون استخدام خوارزميات معروفة

ما طريقة العثور على إبرة أسرع؟ من خلال فرز القش ، أو البحث عن غير قصد لذلك؟

أعتقد أن أفضل طريقة للتجربة ، لسوء الحظ ، ليس لدي كومة قش ، لكن لديّ معرفة أساسية في البرمجة ، متحكم في Arduino ، بيئة ملائمة لكود الكتابة ، حتى يتمكن الجميع من تكرارها.

الخطوة الأولى "فهم"

ما البيانات التي أريد تلقيها؟ الوقت الذي يقضيه في إيجاد الحل الصحيح. التنفيذ الوحيد غير مناسب بسبب تفاصيل التجربة ، تحتاج إلى التحقق من الطريقة عدة مرات ، ثم يكون متوسط ​​الوقت الذي أهتم به متوسطًا. قررت في هذا. والخطوة التالية هي عدد المتغيرات التي يجب الإعلان عنها. نحتاج إلى متغير منفصل لكل طريقة لتخزين مجموع المرات ، دعنا نسميها:

"Time_poslMetod" و "Time_randMetod".

تحتاج إلى ثابت على عدد التكرارات:

#define Iter 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; 

الخطوة الثانية "كتابة التعليمات البرمجية"

تقوم حلقة For بإدارة عدد التكرارات ، بداخلها سنقوم "بإلقاء" الإبرة في كومة قش ، وإجراء بحث ، وقياس الوقت لكل طريقة على حدة ، وتوفير الوقت في متغير "عام" (Time_poslMetod / Time_randMetod) (للمستقبل).

  //   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; } 

قبل البداية ، نحفظ الوقت ، ثم نطرحه من وقت انتهاء البحث. نحن ندير الصفيف (المكدس) من العنصر الأول إلى الأخير. عندما نعثر على الإبرة ، اكتب الوقت ، أكمل البحث ، أضف الوقت إلى المتغير "global" (Time_poslMetod) واخرج من الطريقة.

طريقة عشوائية:

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

الفرق هو أننا نتحقق من عنصر الصفيف العشوائي (مكان في الحزمة) ، نعتمد على الحظ حتى نكون محظوظين ونجد إبرة ، لذلك نستخدم حلقة لا نهائية ، والشيء الرئيسي هو أن لدينا حالة خروج ، لذلك لا داعي للقلق. عندما نعثر على الإبرة ، سجل الوقت ، أكمل البحث ، أضف الوقت إلى المتغير "global" (Time_randMetod) واخرج من الطريقة.

قد تلاحظ أن هذه الطريقة لا تضمن لنا أي ضمان بأنها أسرع ، في هذا السياق تبدو أبطأ ، لأنه إذا لم يكن الحظ في صالحنا ، فقد نجري أكثر من 100 فحص لأماكن الرصة وتفشل ، في ذلك الوقت كما هو الحال في الطريقة المتسلسلة المكونة من 100 شيك ، فهذا يعني أننا فحصنا المجموعة بالكامل ومن المؤكد أننا وجدنا إبرة تقضي أقصى وقت لهذه الطريقة. ومع ذلك ، أنا مع التجربة ، لذلك دعونا نستمر.

وضع كل ذلك معًا ، تلميع الشفرة ، مما يجعل الإخراج ملائمًا للفهم:

الخطوة الثالثة "تحليل النتائج"

نحصل على:



بصراحة ، أنا مندهش من النتائج. بعد أن راهنت على أن الأوقات ستكون قريبة ، سأخسر.

فقط ما كنت أخاف حدوثه ، تحول الحظ عني (نحن). سيكون ذلك للتحقق من كيفية حدوث الأشياء إذا اخترنا كل خلية تالية في المجموعة ، فلن نختار الخلايا التي تم فحصها بالفعل. في غضون ذلك ، سنضع في اعتبارنا أن دراسة البرمجة والرياضيات والعلوم الدقيقة مفيدة لتقليل الوقت لعمليات روتينية مملة ، وترك الوقت لشيء ممتع.