Wir suchen nach einer Nadel in einem Stapel, ohne bekannte Algorithmen zu verwenden

Welche Methode zum Auffinden einer Nadel ist schneller? Durch einen Strohhalm sortieren oder versehentlich danach suchen?

Ich denke, der beste Weg ist das Experimentieren. Leider habe ich keinen Heuhaufen, aber ich habe grundlegende Programmierkenntnisse, einen Arduino-Mikrocontroller und eine praktische Umgebung zum Schreiben von Code, sodass jeder ihn wiederholen kann.

Erster Schritt „Verstehen“

Welche Daten möchte ich erhalten? Zeitaufwand für die Suche nach der richtigen Lösung. Die einzige Ausführung ist aufgrund der Besonderheiten des Experiments nicht geeignet. Sie müssen die Methode mehrmals überprüfen. Dann ist die Zeit, an der ich interessiert bin, durchschnittlich. Ich habe mich dafür entschieden. Der nächste Schritt ist, wie viele und welche Variablen deklariert werden sollen. Wir benötigen für jede Methode eine separate Variable, um die Summe der Zeiten zu speichern. Nennen wir sie:

"Time_poslMetod" und "Time_randMetod".

Benötigen Sie eine Konstante für die Anzahl der Iterationen:

#define Iter 1000.

Der Ausgabewert wird erhalten, indem der erste durch die Anzahl der Iterationen geteilt wird.

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

Schritt zwei "Code schreiben"

Die For-Schleife verwaltet die Anzahl der Iterationen. In ihr wird die Nadel in den Heuhaufen „geworfen“, gesucht, die Zeit für jede Methode separat gemessen und die Zeit in einer „globalen“ Variablen (Time_poslMetod / Time_randMetod) (für die Zukunft) gespeichert.

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

So sehen meine Methoden aus.

Sequentielle Methode:

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

Vor dem Beginn merken wir uns die Zeit und subtrahieren sie dann von der Zeit, zu der die Suche endete. Wir durchlaufen das Array (Stapel) vom ersten bis zum letzten Element. Wenn wir die Nadel gefunden haben, schreiben Sie die Zeit, schließen Sie die Suche ab, fügen Sie die Zeit der Variablen „global“ (Time_poslMetod) hinzu und beenden Sie die Methode.

Zufällige Methode:

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

Der Unterschied besteht darin, dass wir ein zufälliges Element des Arrays (eine Stelle im Stapel) überprüfen, uns auf das Glück verlassen, bis wir Glück haben und eine Nadel finden. Daher verwenden wir eine Endlosschleife. Hauptsache, wir haben eine Ausgangsbedingung, sodass wir uns keine Sorgen machen. Wenn wir die Nadel gefunden haben , notieren Sie die Zeit, schließen Sie die Suche ab, fügen Sie die Zeit der Variablen „global“ (Time_randMetod) hinzu und beenden Sie die Methode.

Möglicherweise stellen Sie fest, dass die Methode uns keine Garantie dafür gibt, dass sie schneller ist. Auf diese Weise sieht sie sogar noch langsamer aus. Wenn das Glück nicht auf unserer Seite ist, können wir möglicherweise mehr als 100 Überprüfungen der Stapelplätze durchführen und zu diesem Zeitpunkt fehlschlagen Wie bei einer sequentiellen Methode mit 100 Überprüfungen würde dies bedeuten, dass wir den gesamten Stapel überprüft haben und definitiv eine Nadel gefunden hätten, die die maximale Zeit für diese Methode verbringt. Trotzdem bin ich für das Experiment, also lasst uns fortfahren.

Alles zusammenfügen, den Code polieren und die Ausgabe verständlich machen:

Schritt drei "Ergebnisanalyse"

Wir bekommen:



Ehrlich gesagt bin ich über die Ergebnisse überrascht. Wenn ich das Geld gewettet hätte, dass die Zeiten nahe sein werden, würde ich verlieren.

Genau das, wovor ich Angst hatte, geschah, das Glück wandte sich von mir (uns) ab. Das wäre zu überprüfen, wie es gewesen wäre, wenn wir, wenn wir jede nächste Zelle im Stapel ausgewählt hätten, nicht bereits geprüfte ausgewählt hätten. In der Zwischenzeit werden wir bedenken, dass das Studium von Programmierung, Mathematik und exakten Wissenschaften nützlich ist, um die Zeit für langweilige Routineoperationen zu verkürzen und Zeit für etwas Spaß zu lassen.