Как найти иголку в стоке сена

Магнит, наверное, единственный способ найти иголку в стогу сена. Но ведь это надо по пучку перебирать весь стог. В любом случае быстро не получится. А из середины стога магнит иголку не вытащит.

Металлоискателем тоже самое, всё сено по частям ворошить придётся.

Есть ещё один вариант, который я знаю, чтобы сено не сжигать, тем более потом в золе иголку найти будет очень тяжело. Надо разложить сено в ясли лошадям. Лошадь это не корова, она чистое животное и никакую гадость есть не будет. Сено съест, иголку в яслях оставит. Гвоздики маленькие, проволока — все подобные штучки всегда в яслях остаются. Там вы иголку и найдёте.

Ищем иголку в стоге без использования всем известных алгоритмов

Какой метод поиска иголки быстрее? Перебирать по соломинке, или же случайно искать ее?

Считаю, что лучший способ — эксперимент, к сожалению стога сена у меня нет, зато есть базовые знания программирования, микроконтроллер 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;
}

Перед самым началом запоминаем время, чтобы потом вычесть его из времени завершения поиска. Пробегаем по массиву(стогу) начиная с первого элемента, до последнего. Когда находим иглу записываем время, завершаем поиск, прибавляем время к “глобальной”(Time_poslMetod) переменной и выходим из метода.

Случайный метод:

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

Отличие в том, что проверяем случайный элемент массива(местечко в стоге), полагаемся на удачу до тех пор, пока не повезет и не найдем иглу, поэтому используем бесконечный цикл, главное что у нас есть условие выхода, так что не беспокоимся. Когда находим иглу, записываем время, завершаем поиск, прибавляем время к “глобальной”(Time_randMetod) переменной и выходим из метода.

Можно заметить, что метод не гарантирует нам никакой гарантии в том, что он быстрее, в таком ключе он выглядит даже медленней, ведь если удача не будет на нашей стороне мы вполне можем совершить больше чем 100 проверок мест стога и потерпеть неудачу, в то время как в последовательном методе 100 проверок означало бы что мы проверили весь стог и точно бы нашли иголку затратив максимальное время для этого метода. Все же я за эксперимент, так что продолжим.

Собираем все вместе, полируем код, делаем выходные данные удобные для осмысления:

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

Шаг третий “Анализ результатов”

Получаем:

Честно сказать я удивлен полученным результатам. Поставив деньги на то, что времена будут близкими я бы проиграл.

Произошло как раз то, чего я боялся, удача отвернулась от меня (нас). Вот бы проверить как обстояли бы дела, если бы выбирая каждую следующую ячейку в стоге, мы бы не выбирали уже проверенные. А пока будем иметь ввиду, что изучать программирование, математику, точные науки полезно для сокращения времени на скучные рутинные операции, оставляя время на что нибудь веселое.