Почему одна программа выполняется быстрее?

Question

У меня есть два кода, решающих одну и ту же задачу. Но почему то одна выполняется быстрее другой. И у меня вопрос из-за чего скорость одной мешьне.

код медленной программы

#include <iostream>
#include <vector>

using namespace std;

int closeNumber(vector<int> N, int number, int size) {
    int l = 0;
    int r = size - 1; 

    while (r - l > 1) {    
        int mid = (l + r) / 2;

        if (number > N[mid]) {
            l = mid;
        } 
        else {
            r = mid;
        } 
    }   

    if (N[r] - number < number - N[l]) {
        return N[r];
    }

    return N[l];
}

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> N(n);
    vector<int> K(k);

    for (int i = 0; i < n; i++) cin >> N[i];
    
    int number;
    for (int i = 0; i < k; i++) {
        cin >> number;

        cout << closeNumber(N, number, n) << endl;
    }
    


    return 0;
}

код программы быстрой

#include <iostream>

using namespace std;
 
int main()
{
    int n, k, x;
    cin >> n >> k;
    int arr[100000];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    for (int h = 0; h < k; h++)
    {
        cin >> x;
        int L = 0;
        int R = n - 1;

        while (R - L > 1)
        {
            int M = (R + L) / 2;

            if (arr[M] < x)
                L = M;
            else
                R = M;
        }
 
        if (x - arr[L] <= arr[R] - x) cout << arr[L] << endl;
        else cout << arr[R] << endl;
    }
    return 0;
}

Answer 1

Простите, что как ответ, но особо не наблюдаю.

Скомпилировал и прогнал для N = 100000 и K = 10000 обе.

На моей машине с выводом в файл быстрая отработала за 35 мс. Медленная - за 224 мс.

Как только я убрал, гм... очень тяжеловесную передачу вектора по значению и заменил на

int closeNumber(const vector<int>& N, int number, int size) {

медленная отработала за те же 35 мс.

В пределах погрешности они одинаковы - если не копировать каждый раз большие массивы данных.

Update

Переписал поиск с использованием стандартных алгоритмов:

int closeNumber(const vector<int>& N, int number)
{
    auto m = lower_bound(N.begin(),N.end(),number);
    if (m == N.end())   return N[N.size()-1];
    if (m == N.begin()) return N[0];
    if (*m + *(m-1) < 2*number) return *m;
    return *--m;
}

Эксперимент с данными N[i] = i*4 и одной и той же последовательностью из 10000 случайных запросов.

Быстрая программа                - 33,9±1,4 мс
Исправленная медленная программа - 33,7±1,3 мс
Новая программа                  - 33,5±2,2 мс

Погрешность - исходя из 100 запусков программы.

Выводы об одинаковой скорости делайте сами :)

БЛОГ НА HUSL

Почему одна программа выполняется быстрее?

Ответы (1 шт):