Estamos procurando uma agulha em uma pilha sem usar algoritmos conhecidos

Qual método de encontrar uma agulha é mais rápido? Classificar através de um canudo ou procurá-lo acidentalmente?

Acho que a melhor maneira é experimentar, infelizmente não tenho um palheiro, mas tenho conhecimentos básicos de programação, um microcontrolador Arduino, um ambiente conveniente para escrever código, para que todos possam repeti-lo.

Etapa 1 "Compreensão"

Quais dados eu quero receber? Tempo gasto para encontrar a solução certa. A única execução não é adequada devido às especificidades do experimento. Você precisa verificar o método várias vezes; o tempo em que me interessa é médio. Eu decidi sobre isso. O próximo passo é quantas e quais variáveis ​​declarar. Precisamos de uma variável separada para cada método, a fim de armazenar a soma das vezes, vamos chamá-lo:

"Time_poslMetod" e "Time_randMetod".

Precisa de uma constante no número de iterações:

#define Iter 1000.

O valor de saída é obtido dividindo o primeiro pelo número de iterações.

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

Etapa dois "escrever código"

O loop For gerencia o número de iterações; dentro dele, jogaremos a agulha no palheiro, procurá-lo, medir o tempo de cada método separadamente, economizar tempo em uma variável "global" (Time_poslMetod / Time_randMetod) (para o futuro).

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

É assim que meus métodos se parecem.

Método sequencial:

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

Antes do início, memorizamos a hora e depois a subtraímos da hora em que a pesquisa terminou. Percorremos a matriz (pilha) do primeiro elemento ao último. Quando encontrarmos a agulha, escreva a hora, conclua a pesquisa, adicione a hora à variável "global" (Time_poslMetod) e saia do método.

Método aleatório:

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

A diferença é que verificamos um elemento aleatório do array (um lugar na pilha), confiamos na sorte até termos sorte e encontramos uma agulha , por isso usamos um loop infinito, o principal é que temos uma condição de saída, para não nos preocuparmos. Quando encontrarmos a agulha , anote o horário, conclua a pesquisa, adicione o horário à variável "global" (Time_randMetod) e saia do método.

Você pode notar que o método não nos garante nenhuma garantia de que é mais rápido; nesse sentido, ele parece ainda mais lento, porque se a sorte não estiver do nosso lado, é possível que façamos mais de 100 verificações nos lugares da pilha e falhemos naquele momento como em um método seqüencial de 100 verificações, significa que verificamos toda a pilha e definitivamente encontramos uma agulha gastando o tempo máximo para esse método. No entanto, sou a favor do experimento, então vamos continuar.

Juntando tudo, polindo o código, tornando a saída conveniente para a compreensão:

Etapa três "Análise de resultados"

Temos:



Sinceramente, estou surpreso com os resultados. Tendo apostado o dinheiro que os tempos estarão próximos, eu perderia.

Exatamente do que eu tinha medo, a sorte se afastou de mim (nós). Isso seria verificar como as coisas teriam sido se, se selecionássemos cada célula seguinte na pilha, não tivéssemos selecionado as já verificadas. Enquanto isso, teremos em mente que estudar programação, matemática e ciências exatas é útil para reduzir o tempo para operações rotineiras chatas, deixando tempo para algo divertido.