Почему мои числа времени выполнения неверны, когда я пытаюсь измерить, сколько времени требуется функции, чтобы вернуться?

Question

У меня есть 30 векторов отсортированных целых, размеры векторов варьируются от 2 ⁰ до 2 ³⁰ . Я пытаюсь измерить, сколько времени займет двоичный поиск, чтобы найти значение в каждом из них, но сообщенное время ускоряется , поскольку векторы становятся больше. На самом деле время не занимает больше времени, отчетность ошибочна.

Вот мой код:

int main() {
    const unsigned int maxPower = 30;  // 2^maxPower
    long long n = 1 << maxPower;  // n = 2^i

    for (int i = 0;  i <= maxPower; ++i) {

        std::vector<long long> haystack = getVector(i);  // returns a sorted vector of size i
        long long needle = haystack.size()/2 + 1;

        clock_t t1 = clock();  // start timer
        binary_search(haystack, needle);
        clock_t t2 = clock();  // end timer

        clock_t dt = t2 - t1;
        double clocks_per_rep = ((double)dt)/n;
        double seconds = clocks_per_rep/CLOCKS_PER_SEC;

        std::cout << seconds << std::endl;
    }

    return 0;
}

Я тоже пытался использовать high_resolution_clock, но не смог этого получить даже отображать что-либо, кроме 0.

---

РЕДАКТИРОВАТЬ: Моя первоначальная проблема была решена, но теперь у меня есть новая: вряд ли есть какие-либо изменения в моем времени, даже когда некоторые занимают гораздо больше времени, чем другие. Вот мой новый код и вывод:

int main() {
    const unsigned int maxPower = 30;  // 2^maxPower
    long long n = 1 << maxPower;  // n = 2^i

    for (int i = 0;  i <= maxPower; ++i) {

        std::vector<long long> haystack = getVector(i);  // returns a sorted vector of size i
        long long needle = haystack.size()/2 + 1;

        clock_t t1 = clock();  // start timer
        ternary_search(haystack, needle);
        clock_t t2 = clock();  // end timer

        clock_t dt = t2 - t1;
        double seconds = (double)dt/CLOCKS_PER_SEC;

        std::cout << seconds << std::endl;
    }

    return 0;
}

1e-06
1e-06
1e-06
0
1e-06
1e-06
0
0
1e-06
0
0
1e-06
0
0
0
0
1e-06
1e-06
1e-06
4e-06
3e-06
3e-06
1e-06
2e-06
3e-06
3e-06
3e-06
2e-06
3e-06
3e-06
3e-06

Answer 1

При условии отсутствия смещения в поиске, dt ожидается равным O(log(N)). При вычислении

double clocks_per_rep = ((double)dt)/n;

clock_per_rep равно O(log(N)/N). Имеет смысл, что значение уменьшается с ростом N.

Для меня имеет смысл опустить деление на n.

clock_t dt = t2 - t1;
double seconds = (double(dt))/CLOCKS_PER_SEC;

Answer 2

Двоичный поиск принимает наихудший случай O (log N). В вашем случае это означает от 1 до 30 сравнений. В лучшем случае первое сравнение уже правильное и возвращает напрямую.

Вы пытаетесь измерить время, необходимое для выполнения 1-30 сравнений, поэтому, по сути, времени вообще нет. Я немного удивлен, что вы получаете что-нибудь кроме 0 и 1e-06. Кажется, это точность ваших часов. Вероятно, ваш процессор работает более чем в 1000 раз быстрее.

Вы должны выполнить все операции oop, чтобы выполнить много поисков, а затем усреднить их по каждому запросу, чтобы получить более высокую точность. Вы также тестируете только нахождение одного указанного значения c. Вы тщательно продумали этот выбор, чтобы он был худшим? Если нет, то почему бы не выполнить поиск по каждому значению в векторе один раз?

Мое предложение будет использовать 3 l oop:

N = 1
Outer loop: loop until the time difference between start and finish is >1s.
    N = 2 * N
    start clock
    Middle loop: repeat N times
        Inner loop: search for every value in the vector once
    end clock here

Моя лучшая догадка относительно того, почему вывод занимает экспоненциально каждый раз дольше это getVector(i) занимает это время. Вы должны инициализировать весь вектор, и каждый проход в два раза больше. Так что это отчасти ожидается. Но это, вероятно, можно оптимизировать много. Скорее всего, вы увеличиваете вектор, а не инициализируете его нужным размером.