We are looking for a needle in a stack without using well-known algorithms.

Which needle search method is faster? Go through a straw, or accidentally look for it?

I believe that the best way is to experiment, unfortunately I don’t have haystacks, but there is a basic programming knowledge, an Arduino microcontroller, a convenient environment for writing code, so everyone can repeat.

Step One “Comprehension”

What data do I want to get? The time spent on finding the right solution. The only execution does not suit because of the specifics of the experiment, you need to check the method several times, then the time of interest is the average. Determined with this. The next step is how many and which variables to declare. We need a separate variable for each method to store the sum of times, let's call it:

“Time_poslMetod” and “Time_randMetod”.

We need a constant about the number of iterations:

#define Iter 1000.

The output value will be obtained by dividing the first by the number of iterations.

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

Step Two “Write Code”

With the number of iterations of loop handle For , inside it will "throw" a needle in a haystack search, measure time for each method separately, save time in the "global" (Time_poslMetod / Time_randMetod) variable (in the future).

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

Here are my methods.

Serial method:

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

Before we begin, we memorize the time, in order to subtract it from the time the search was completed. Run through the array (stack) from the first element to the last. When we find the needle, we record the time, end the search, add the time to the “global” (Time_poslMetod) variable, and exit the method.

Random method:

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

The difference is that we check the random element of the array (place in the stack), we rely on luck until we are lucky and find the needle , so we use an infinite loop, the main thing is that we have an exit condition, so do not worry. When we find the needle , we record the time, we complete the search, we add the time to the “global” (Time_randMetod) variable and exit the method.

It can be noted that the method does not guarantee us any guarantee that it is faster, it looks even slower in this vein, because if luck is not on our side, we may well make more than 100 checks of the stack locations and fail, while as in the sequential method, 100 checks would have meant that we checked the entire stack and would have accurately found the needle having spent the maximum time for this method. Still, I'm for the experiment, so let's continue.

Putting it all together, polishing the code, making the output convenient for understanding:

Step Three “Analysis of Results”

We



get : Honestly, I am surprised by the results. Putting money on the fact that the times will be close, I would have lost.

Just what I was afraid of happened, luck turned away from me (us). That would be to check how things would be if choosing each next cell in a stack, we would not have already checked. In the meantime, we will keep in mind that studying programming, mathematics, and exact sciences is useful for reducing the time for boring routine operations, leaving time for something fun.