我们正在寻找不使用众所周知算法的堆栈中的针


哪种找到针的方法更快? 用吸管整理还是不小心找?

我认为最好的方法是进行实验,很遗憾,我没有大海捞针,但是我具有基本的编程知识,Arduino微控制器,方便的代码编写环境,因此每个人都可以重复。

第一步“理解”


我想接收什么数据? 花时间寻找正确的解决方案。 由于实验的特殊性,唯一的执行方式不合适,您需要多次检查该方法,然后我平均感兴趣的时间。 我决定了。 下一步是要声明多少个变量。 为了存储时间总和,我们需要为每个方法使用一个单独的变量,让我们称之为:

“ Time_poslMetod”和“ Time_randMetod”。

在迭代次数上需要一个常数:

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


第三步“结果分析”


我们得到:



老实说,我对结果感到惊讶。 赌钱将时代关闭,我会输。

正是我害怕的事情发生了,运气转离了我(我们)。 那将是检查如果如果我们选择堆栈中的每个下一个单元格,而不会选择已经检查过的单元格,情况将会如何。 同时,我们将牢记,学习编程,数学和精确科学对于减少无聊的日常操作时间,为一些有趣的事情留出时间很有用。

Source: https://habr.com/ru/post/zh-CN439336/


All Articles