C ++ Array vs Vector Sorting (вектор в 2,5 раза медленнее массива в моем случае (без оптимизации))

Question

Я делаю вставку сортировки для 100000 элементов.Я написал две функции.

1 - в нем я копирую данный вектор для сортировки в массив, затем применяю сортировку и затем копирую массив обратно в вектор для возврата.

2- Я применяю сортировку к данному вектору, а затем возвращаю ее.

Теперь, согласно моим знаниям, векторы также динамически создают массив, и разница в скорости оператора C ++ Vector [] должна бытьне существует или, по крайней мере, не так много.Поэтому метод 2 должен быть быстрее, чем метод 1.Но, к моему удивлению, все наоборот.Я пытаюсь найти конкретный ответ, а не просто массив быстрее.:)

версия компилятора => версия gcc 6.2.0 (Rev2, построена проектом MSYS2) g ++ main.cpp -o main

#include <time.h>
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

vector<long> InsertionSort1(vector<long> nums){
    int vsize = nums.size();
    long* arr = new long[vsize];
    int swap, j;

    // Coping the vector to an array
    for(int i=0;i<vsize;i++){
        arr[i] = nums[i];
    }

    //sorting
    for(int i=1;i<vsize;i++){
        swap = arr[i];
        j = i-1;
        while(j>=0 && arr[j] > swap){
            arr[j+1] = arr[j];
            j--; 
        }

        arr[j+1] = swap;   

    }

    // Coping the array back to vector
    for(int i=0;i<vsize;i++){
        nums[i] = arr[i];
    }

    return nums;
}

vector<long> InsertionSort2(vector<long> nums){
    int vsize = nums.size();
    int swap, j;

    for(int i=1;i<vsize;i++){
        swap = nums[i];
        j = i-1;
        while(j>=0 && nums[j] > swap){
            nums[j+1] = nums[j];
            j--; 
        }

        nums[j+1] = swap;   

    }

    return nums;
}

int main(){

    vector<long> entries;
    for(int i=0;i<100000;i++){
        entries.push_back(rand()%100000);
    }

    double start = time(0);
    InsertionSort1(entries);
    double end = time(0);

    cout<<"With Array => "<<end-start<<endl;

    start = time(0);
    InsertionSort2(entries);
    end = time(0);

    cout<<"With Vector => "<<end-start<<endl;
}

Результат приведенного выше кода:

With Array 100000 => 8
With Vector 100000 => 19

Answer 1

Я думаю, что это хорошая вещь, чтобы измерить производительность!std::chrono::high_resolution_clock или google benchmark лучше подходят для работы.

Вам необходимо включить надлежащий уровень оптимизации, скажем, -O3, чтобы получить значимые результаты.

Почему вам нравится реализовывать алгоритм сортировки.Я сравнил ваш подход с std::sort?Для академических целей это нормально, в противном случае вам нужно иметь веские основания и веские доказательства того, что вы справились лучше.

С массивом => 2.55608

С вектором => 1.74857

С std :: sort => 0.00657156

#include <time.h>
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

vector<long> InsertionSort1(vector<long> nums){
    int vsize = nums.size();
    long* arr = new long[vsize];
    int swap, j;

    // Coping the vector to an array
    for(int i=0;i<vsize;i++){
        arr[i] = nums[i];
    }

    //sorting
    for(int i=1;i<vsize;i++){
        swap = arr[i];
        j = i-1;
        while(j>=0 && arr[j] > swap){
            arr[j+1] = arr[j];
            j--; 
        }

        arr[j+1] = swap;   

    }

    // Coping the array back to vector
    for(int i=0;i<vsize;i++){
        nums[i] = arr[i];
    }
    // delete of is missing arr;
    return nums;
}

vector<long> InsertionSort2(vector<long> nums){
    int vsize = nums.size();
    int swap, j;

    for(int i=1;i<vsize;i++){
        swap = nums[i];
        j = i-1;
        while(j>=0 && nums[j] > swap){
            nums[j+1] = nums[j];
            j--; 
        }

        nums[j+1] = swap;   

    }

    return nums;
}

int main(){

    vector<long> entries;
    for(int i=0;i<100000;i++){
        entries.push_back(rand()%100000);
    }

    double start = time(0);
    InsertionSort1(entries);
    double end = time(0);

    cout<<"With Array => "<<end-start<<endl;

    start = time(0);
    InsertionSort2(entries);
    end = time(0);

    cout<<"With Vector => "<<end-start<<endl;
}