Ich muss hinzufügen: Ich rufe meine lineare Suche 15.000 Mal auf und der niedrigste Bereich, in dem ich suche, ist bis zu 50.000 bei jeder Iteration. Dies bedeutet, dass bei der ersten Iteration 15.000 * 50.000 Suchvorgänge durchgeführt werden. Dies sollte länger als 0ms dauern.

Ich habe diese grundlegende lineare Suche:

bool linearSearch(std::vector<int>&primes, int number, int range) {

    for (int i = 0; i < range; i++) {
        if (primes[i] == number)
            return true;
    }
    return false;
}

Ich nehme mir Zeit mit:

void timeLinearSearch(std::vector<int>& primes) {
    clock_t start, stop;
    size_t NRND = 15000;    //  15000 primes per clock

    for (int N = 50000; N <= 500000; N += 50000)    // increase by 50k each iteration
    {
        for (int repeat = 0; repeat < 5; repeat++) {
            start = clock();
            for (int j = 0; j < NRND; j++) {
                linearSearch(primes, rand(), N);
            }
            stop = clock();
            std::cout << stop - start << ", " << N << std::endl;
        }

    }
}

Das Problem hierbei ist, dass die benötigte Zeit 0ms beträgt. Der Vektor 'Primzahlen' enthält ungefähr 600 000 Elemente, sodass die Suche in Reichweite bleibt.

In der linearen Suche, wenn ich ändere:

if(primes[i] == number)

zu

if(primes.at(i) == number)

dann bekomme ich zeit> 0 für die suche genommen.

Ich habe meine lineare Suche mit der von primes.at (i) mit std :: find () verglichen, indem:

for (int j = 0; j < NRND; j++) {
    std::find(primes.begin(), primes.begin() + N, rand());
}

und das ist ungefähr 200ms schneller als mein .at () find.

Warum gibt mir meine Suche mit std :: vector [i] 0 ms Zeit?