Wir suchen nach einer Nadel im Stapel, ohne bekannte Algorithmen zu verwenden.


Welche Nadelsuchmethode ist schneller? Einen Strohhalm durchlaufen oder aus Versehen danach suchen?

Ich glaube, der beste Weg ist zu experimentieren, leider habe ich keine Heuhaufen, aber es gibt Grundkenntnisse in der Programmierung, einen Arduino-Mikrocontroller und eine praktische Umgebung zum Schreiben von Code, so dass sich jeder wiederholen kann.

Schritt eins "Verständnis"


Welche Daten möchte ich bekommen? Die Zeit, um die richtige Lösung zu finden. Die einzige Leistung passt aufgrund der Besonderheiten des Experiments nicht. Sie müssen die Methode mehrmals überprüfen. Dann ist der interessierende Zeitpunkt der Durchschnitt. Damit bestimmt. Der nächste Schritt ist, wie viele und welche Variablen deklariert werden sollen. Wir benötigen für jede Methode eine eigene Variable, um die Summe der Zeiten zu speichern, nennen wir sie:

"Time_poslMetod" und "Time_randMetod".

Wir brauchen eine Konstante über die Anzahl der Iterationen:

#define Iter 1000.

Der Ausgabewert wird durch Division des ersten durch die Anzahl der Iterationen erhalten.

#define Iter 10000#define cell 100uint8_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“


Mit der Anzahl der Iterationen von Loophandgriff Für innen wird „werfen“ eine Nadel im Heuhaufen sucht, misst Zeit für jedes Verfahren einzeln, Zeit in dem „global“ (Time_poslMetod / Time_randMetod) Variable (in der Zukunft) speichern.

// Проводим испытания Iter разfor(uint32_t j = 0; j <= Iter; j++){
    // Очищаем массив с предыдущим значением
    cleanArr();
    // Бросаем иглу в стог
    needle = random(cell + 1);
    potenArr[needle] = 1;
    // Ищем иглу двумя методами и сохраняем время для каждого
    poslMetod();
    randMetod();
  }

Hier sind meine Methoden.

Serienmethode:

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

Kurz bevor wir beginnen, merken wir uns die Uhrzeit, um sie vom Zeitpunkt des Suchvorgangs abzuziehen. Führen Sie das Array (Stack) vom ersten bis zum letzten Element durch. Wenn wir die Nadel finden, nehmen wir die Zeit auf, beenden die Suche, fügen der globalen Variable (Time_poslMetod) Zeit hinzu und beenden die Methode.

Zufällige Methode:

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

Der Unterschied ist, dass wir das zufällige Element des Arrays überprüfen (Platz im Stapel), wir verlassen uns auf das Glück, bis wir Glück haben und die Nadel finden. Daher verwenden wir eine Endlosschleife. Wenn wir eine Nadel finden , nehmen wir die Zeit auf, schließen die Suche ab, fügen der Variablen "global" (Time_randMetod) Zeit hinzu und beenden die Methode.

Es kann angemerkt werden, 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 mehr als 100 Prüfungen der Heuhaufen vornehmen und dabei versagen Wie bei der sequentiellen Methode hätten 100 Überprüfungen dazu geführt, dass wir den gesamten Stapel geprüft hatten und genau herausgefunden hatten, dass die Nadel die maximale Zeit für diese Methode ausgegeben hat. Trotzdem bin ich für das Experiment, also machen wir weiter.

Alles zusammenstellen, den Code polieren, um die Ausgabe für das Verständnis zu vereinfachen:

Code vervollständigen
#define Iter 10000#define cell 100uint8_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;
voidposlMetod();
voidrandMetod();
voidcleanArr();
voidDataOutPrint();
voidsetup(){
  randomSeed(analogRead(A0));
  Serial.begin(115200);
}
voidloop(){
  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);
}
voidposlMetod(){
  startTime = millis();
  for(uint16_t i = 0; i < cell; i++){
    if(potenArr[i] == 1){
      endTime = millis() - startTime;
      break;
    }
  }
  Time_poslMetod += endTime;
}
voidrandMetod(){
  startTime = millis();
  for(;;){
    uint16_t r = random(cell + 1);
    if(potenArr[r] == 1){
      endTime = millis() - startTime;
      break;
    }
  }
  Time_randMetod += endTime; 
}
voidcleanArr(){
  for(uint16_t i = 0; i < cell; i++){
    potenArr[i] = 0;
  }
}
voidDataOutPrint(){
  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);
}


Schritt drei “Analyse der Ergebnisse”


Wir



bekommen : Ehrlich gesagt bin ich von den Ergebnissen überrascht. Wenn ich das Geld dafür einsetzen würde, dass die Zeiten knapp werden, hätte ich verloren.

Genau das, wovor ich Angst hatte, passierte, das Glück wendete sich von mir (uns) ab. Das wäre zu prüfen, wie die Dinge aussehen würden, wenn wir jede nächste Zelle in einem Stapel auswählen würden, die wir nicht bereits geprüft hätten. In der Zwischenzeit werden wir uns daran erinnern, dass ein Studium der Programmierung, Mathematik und exakten Wissenschaften hilfreich ist, um die Zeit für langweilige Routineoperationen zu reduzieren und Zeit für etwas Spaß zu lassen.

Jetzt auch beliebt: