🏰 🅿️ ✍️ Kami mencari jarum di tumpukan tanpa menggunakan algoritma yang terkenal 🤾🏽 🐥 🙌🏿

Metode menemukan jarum yang mana yang lebih cepat? Menyortir sedotan, atau tanpa sengaja mencarinya?

Saya pikir cara terbaik adalah eksperimen, sayangnya saya tidak memiliki tumpukan jerami, tetapi saya memiliki pengetahuan pemrograman dasar, mikrokontroler Arduino, lingkungan yang nyaman untuk menulis kode, sehingga semua orang dapat mengulanginya.

Langkah Satu “Memahami”

Data apa yang ingin saya terima? Waktu yang dihabiskan untuk menemukan solusi yang tepat. Eksekusi satu-satunya tidak cocok karena spesifik dari percobaan, Anda perlu memeriksa metode beberapa kali, maka waktu saya tertarik rata-rata. Saya memutuskan ini. Langkah selanjutnya adalah berapa banyak dan variabel mana yang harus dideklarasikan. Kami membutuhkan variabel terpisah untuk setiap metode untuk menyimpan jumlah kali, sebut saja:

"Time_poslMetod" dan "Time_randMetod".

Perlu konstanta pada jumlah iterasi:

#define Iter 1000.

Nilai output diperoleh dengan membagi yang pertama dengan jumlah iterasi.

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

Langkah dua "tulis kode"

Loop Untuk mengatur jumlah iterasi, di dalamnya kita akan "membuang" jarum ke tumpukan jerami, melakukan pencarian, mengukur waktu untuk setiap metode secara terpisah, menyimpan waktu dalam variabel "global" (Time_poslMetod / Time_randMetod) (untuk masa depan).

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

Seperti inilah metode saya.

Metode berurutan:

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

Sebelum awal, kami menghafal waktu, lalu mengurangkannya sejak pencarian berakhir. Kami menjalankan melalui array (tumpukan) dari elemen pertama hingga yang terakhir. Ketika kami menemukan jarum, tulis waktu, akhiri pencarian, tambahkan waktu ke variabel "global" (Time_poslMetod) dan keluar dari metode.

Metode acak:

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

Perbedaannya adalah bahwa kami memeriksa elemen array acak (tempat di tumpukan), bergantung pada keberuntungan sampai kami beruntung dan menemukan jarum , jadi kami menggunakan loop tak terbatas, yang utama adalah bahwa kami memiliki kondisi keluar, jadi kami tidak khawatir. Ketika kami menemukan jarum , tulis waktu, selesaikan pencarian, tambahkan waktu ke variabel "global" (Time_randMetod) dan keluar dari metode.

Anda mungkin memperhatikan bahwa metode ini tidak menjamin kami ada jaminan bahwa itu lebih cepat, dalam nada ini kelihatannya lebih lambat, karena jika keberuntungan tidak ada di pihak kami, kami mungkin akan melakukan lebih dari 100 pemeriksaan tempat tumpukan dan gagal, pada saat itu seperti dalam metode berurutan dari 100 cek akan berarti bahwa kami memeriksa seluruh tumpukan dan pasti akan menemukan jarum menghabiskan waktu maksimum untuk metode ini. Meskipun demikian, saya untuk eksperimen, jadi mari kita lanjutkan.

Menyatukan semuanya, memoles kode, membuat output nyaman untuk dipahami:

Seluruh kode

 #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; void poslMetod(); void randMetod(); void cleanArr(); void DataOutPrint(); void setup() { randomSeed(analogRead(A0)); Serial.begin(115200); } void loop() { Time_poslMetod = 0; Time_randMetod = 0; Serial.println(" "); Serial.println("Start"); calculationStartTime = millis(); //   Iter  for(uint32_t j = 0; j <= Iter; j++){ //      cleanArr(); //        needle = random(cell + 1); potenArr[needle] = 1; //           poslMetod(); randMetod(); } //       DataOutPrint(); delay(2000); } void poslMetod(){ startTime = millis(); for(uint16_t i = 0; i < cell; i++){ if(potenArr[i] == 1){ endTime = millis() - startTime; break; } } Time_poslMetod += endTime; } void randMetod(){ startTime = millis(); for(;;){ uint16_t r = random(cell + 1); if(potenArr[r] == 1){ endTime = millis() - startTime; break; } } Time_randMetod += endTime; } void cleanArr(){ for(uint16_t i = 0; i < cell; i++){ potenArr[i] = 0; } } void DataOutPrint(){ calculationEndTime = (millis() - calculationStartTime)/1000; float OUTposl = (float)Time_poslMetod/Iter; float OUTrand = (float)Time_randMetod/Iter; Serial.println(" "); Serial.print("Number of iterations = "); Serial.println(Iter); Serial.print("Time for calculate (sec) = "); Serial.println(calculationEndTime); Serial.print("Posledovatelniy metod - AverageTime (ms) = "); Serial.println(OUTposl,3); Serial.print("Randomniy metod - AverageTime (ms) = "); Serial.println(OUTrand,3); }

Langkah Tiga "Analisis Hasil"

Kami mendapatkan:

Jujur, saya terkejut dengan hasilnya. Setelah bertaruh uang bahwa waktunya akan dekat, saya akan kehilangan.

Apa yang saya takutkan terjadi, keberuntungan berpaling dari saya (kita). Itu akan untuk memeriksa bagaimana keadaannya jika jika kita memilih setiap sel berikutnya dalam tumpukan, kita tidak akan memilih yang sudah diperiksa. Sementara itu, kita akan ingat bahwa mempelajari pemrograman, matematika, dan ilmu pasti berguna untuk mengurangi waktu untuk operasi rutin yang membosankan, menyisakan waktu untuk sesuatu yang menyenangkan.

Kami mencari jarum di tumpukan tanpa menggunakan algoritma yang terkenal

Langkah Satu “Memahami”

Langkah dua "tulis kode"

Langkah Tiga "Analisis Hasil"

More articles: