Выбор сортировки - массив против вектора - PullRequest
Новая
       39

Выбор сортировки - массив против вектора

0 голосов
/ 01 мая 2020

Я реализовал SelectionSort алгоритм в C ++, используя простые массивы и векторы. Протестировал их на случайных выборках в диапазоне [1, 65535]. Вот результаты: 

+-------------+-------------------+--------------------+
| Sample Size | Time for impArray | Time for impVector |
+-------------+-------------------+--------------------+
|      50     |      9.263 ns     |      32.329 ns     |
+-------------+-------------------+--------------------+
|     500     |     471.537 us    |     3039.441 us    |
+-------------+-------------------+--------------------+
|     5000    |     117.911 ms    |     1202.402 ms    |
+-------------+-------------------+--------------------+

Если бы это было критичное по времени приложение с большими размерами выборки, реализации бы сильно отличались. Я хочу спросить причину большой разницы во времени выполнения между двумя реализациями? 

Sorting.h

Main.cpp

#include "Sorting.h"
#include <iostream>
#include <chrono>

template <class T>
void printArr(T* pArrBegin, int i32ArrSize)
{
    for(int i=0; i<i32ArrSize; i++)
    {
        std::cout << pArrBegin[i] << " ";
    }
    std::cout << '\n';
}

template <class T>
void printVect(std::vector<T>& vArrHead)
{
    for (auto elem : vArrHead)
        std::cout << elem << " ";
    std::cout << '\n';
}


int main()
{
    std::chrono::steady_clock::time_point begin;
    std::chrono::steady_clock::time_point end;

    static const int i32Size = 1;
    int arr[i32Size] = {0};
    begin = std::chrono::steady_clock::now();
    etpc::sortSelection<int>(arr, i32Size);
    end = std::chrono::steady_clock::now();
    std::cout << "Time difference impArray = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "[ns]" << std::endl;
    //printArr<int>(arr, i32Size);

    std::vector<int> v = {1};
    begin = std::chrono::steady_clock::now();
    etpc::sortSelection<int>(v);
    end = std::chrono::steady_clock::now();
    std::cout << "Time difference impVector = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << "[ns]" << std::endl;
    //printVect(v);

    return 0;
}

Обратите внимание, что я использовал следующие инициализаторы: 

static const int i32Size;
i32Size = 50;
i32Size = 500;
i32Size = 5000;
// Use the following link to access the array list
// https://repl.it/repls/BountifulAggravatingPetabyte

Я запустил код с помощью команды g++ -std=c++17 -O3 -Wall -Wextra -Werror main.cpp -o main на машине со следующими спецификациями: 

CPU:       Single core Intel Xeon (-MCP-) cache: 46080 KB speed: 2300 MHz (max)
System:    Host: erdem-1 Kernel: 5.0.0-1034-gcp x86_64 bits: 64 Console: tty 0
           Distro: Ubuntu 18.04.4 LTS

Кажется, что реализации одинаково эффективны в отношении времени выполнения, а не беспорядка кода. Обновлены результаты: 

+-------------+-------------------+--------------------+
| Sample Size | Time for impArray | Time for impVector |
+-------------+-------------------+--------------------+
|      50     |      3.154 ns     |      3.499 ns      |
+-------------+-------------------+--------------------+
|     500     |     136.928 us    |     240.906 us     |
+-------------+-------------------+--------------------+
|     5000    |     14.550 ms     |     14.496 ms      |
+-------------+-------------------+--------------------+
...