vitesse de recherche dans un tableau
Bonjour,
il m'arrive un truc je n'y comprends rien.
L'idée est la suivante: je créé un tableau "c-style", ainsi qu'une fonction exists qui regarde si un élément donné k existe dans ce tableau.
J'utilise une méthode basique, brutale, moche, je sais qu'on peut faire beaucoup mieux et surtout beaucoup plus rapide, mais là n'est pas le problème.
Prenons donc ce bout de code:
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <chrono>
using namespace std;
bool exists(int ints[], int size, int k)
{
bool found = false;
int i = 0;
while (!found && i<size)
found = (ints[i++] == k);
return found;
}
void main()
{
const int size = 100000;
const int k = 90000;
int ints[size];
for (int i = 0; i < size; ++i)
ints[i] = i;
auto start = chrono::steady_clock::now();
cout << exists(ints, size, k) << endl;
cout << chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count() << endl << endl;
start = chrono::steady_clock::now();
cout << exists(ints, size, k) << endl;
cout << chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count() << endl << endl;
getchar();
} |
Ce que je fais, c'est que je fais exactement 2 fois la même chose. Mais voilà l'output que j'obtiens:
La première recherche et plus lente que la deuxième!
Et c'est systématique, quelques soient les options de compilation que je choisis! Même en mode Debug!
Je suis sous Windows, je compile avec Visual Studio 2017.
J'ai relancé le test des dizaines de fois, et j'ai toujours le même ordre de différence de vitesse d'exécution.
Comment est-ce possible? J'imagine que le compilateur doit effectuer quelque optimisation? Mais c'est étrange puisque le résultat est le même en Debug et/ou sans optimisation.
Une idée?
