Quelle méthode pour trouver une
aiguille est plus rapide? Trier à travers une paille, ou chercher accidentellement?
Je pense que le meilleur moyen est d'expérimenter, malheureusement je n'ai pas de meule de foin, mais j'ai des connaissances de base en programmation, un microcontrôleur Arduino, un environnement pratique pour écrire du code, donc tout le monde peut le répéter.
Première étape «Comprendre»
Quelles données dois-je recevoir? Temps passé à trouver la bonne solution. La seule exécution ne convient pas en raison des spécificités de l'expérience, vous devez vérifier la méthode plusieurs fois, puis le temps qui m'intéresse est moyen. J'ai décidé. L'étape suivante consiste à déterminer le nombre et les variables à déclarer. Nous avons besoin d'une variable distincte pour chaque méthode afin de stocker la somme des temps, appelons-la:
"Time_poslMetod" et "Time_randMetod".
Besoin d'une constante sur le nombre d'itérations:
# définir Iter 1000.
La valeur de sortie est obtenue en divisant la première par le nombre d'itérations.
#define Iter 10000 #define cell 100 uint8_t potenArr[cell];
Deuxième étape «écrire du code»
La boucle For gère le nombre d'itérations, à l'intérieur nous allons «jeter» l'
aiguille dans la botte de foin, effectuer une recherche, mesurer le temps pour chaque méthode séparément, enregistrer le temps dans une variable «globale» (Time_poslMetod / Time_randMetod) (pour l'avenir).
Voici à quoi ressemblent mes méthodes.
Méthode séquentielle:
void poslMetod(){ startTime = millis(); for(uint16_t i = 0; i < cell; i++){ if(potenArr[i] == 1){ endTime = millis() - startTime; break; } } Time_poslMetod += endTime; }
Avant le tout début, nous mémorisons l'heure, puis la soustrayons de l'heure de fin de la recherche. Nous parcourons le tableau (pile) du premier élément au dernier. Lorsque nous trouvons l'
aiguille, écrivez l'heure, mettez fin à la recherche, ajoutez l'heure à la variable «globale» (Time_poslMetod) et quittez la méthode.
Méthode aléatoire:
void randMetod(){ startTime = millis(); for(;;){ uint16_t r = random(cell + 1); if(potenArr[r] == 1){ endTime = millis() - startTime; break; } } Time_randMetod += endTime; }
La différence est que nous vérifions un élément de tableau aléatoire (une place dans la pile), comptons sur la chance jusqu'à ce que nous soyons chanceux et trouvions une
aiguille , donc nous utilisons une boucle infinie, l'essentiel est que nous ayons une condition de sortie, donc ne nous inquiétons pas. Lorsque nous trouvons l'
aiguille , enregistrons l'heure, terminez la recherche, ajoutez l'heure à la variable «globale» (Time_randMetod) et quittez la méthode.
Vous remarquerez peut-être que la méthode ne nous garantit aucune garantie qu'elle est plus rapide, de cette façon, elle semble encore plus lente, car si la chance n'est pas de notre côté, nous pouvons bien faire plus de 100 vérifications des emplacements de la pile et échouer, à ce moment-là comme dans une méthode séquentielle de 100 contrôles, cela signifierait que nous avons vérifié la pile entière et que nous aurions certainement trouvé une aiguille passant le temps maximum pour cette méthode. Néanmoins, je suis pour l'expérience, alors continuons.
Mettre tout cela ensemble, polir le code, rendre la sortie pratique pour la compréhension:
Code entier #define Iter 10000 #define cell 100 uint8_t potenArr[cell];
Troisième étape «Analyse des résultats»
Nous obtenons:
Honnêtement, je suis surpris des résultats. Ayant parié l'argent que les temps seront proches, je perdrais.
Juste ce dont j'avais peur, la chance s'est détournée de moi (nous). Ce serait de vérifier comment les choses auraient été si si nous avions sélectionné chaque cellule suivante de la pile, nous n'aurions pas sélectionné celles déjà vérifiées. En attendant, nous garderons à l'esprit que l'étude de la programmation, des mathématiques et des sciences exactes est utile pour réduire le temps nécessaire aux opérations de routine ennuyeuses, laissant du temps pour quelque chose d'amusant.