Below is the code I used for comparing:
// Example program
#include <iostream>
#include <string>
#include <vector>
#include <chrono>
using namespace std::chrono;
using namespace std;
bool existHelperArrayVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
if(i>=word.length())
{
return true;
}
else
{
bool answer = false;
if(Board[u_i][u_j] == word[i])
{
char temp = Board[u_i][u_j];
Board[u_i][u_j] = '?';
int row_len = Board.size();
int col_len = Board[0].size();
// Uses Array
int row_offset[4]={0, 0, 1, -1};
int col_offset[4]={1, -1, 0, 0};
for(int k=0; k<4; k )
{
int v_i = u_i row_offset[k];
int v_j = u_j col_offset[k];
if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len) && (Board[v_i][v_j] != '?'))
answer |= existHelperArrayVersion(word, i 1, v_i, v_j, Board);
}
if(i 1 == word.length())
answer |= true;
Board[u_i][u_j] = temp;
}
return answer;
}
}
bool existHelperVectorVersion(string &word, int i, int u_i, int u_j, vector<vector<char>>& Board)
{
if(i>=word.length())
{
return true;
}
else
{
bool answer = false;
if(Board[u_i][u_j] == word[i])
{
char temp = Board[u_i][u_j];
Board[u_i][u_j] = '?';
int row_len = Board.size();
int col_len = Board[0].size();
//Uses Vectors
vector<int> row_offset = {0, 0, 1, -1};
vector<int> col_offset = {1, -1, 0, 0};
for(int k=0; k<4; k )
{
int v_i = u_i row_offset[k];
int v_j = u_j col_offset[k];
if( !(0 >v_i || v_i >= row_len || 0>v_j || v_j >= col_len) && (Board[v_i][v_j] != '?'))
answer |= existHelperVectorVersion(word, i 1, v_i, v_j, Board);
}
if(i 1 == word.length())
answer |= true;
Board[u_i][u_j] = temp;
}
return answer;
}
}
bool exist(vector<vector<char>>& board, string word, int option)
{
if(option == 0)
cout << "----ARRAY------\n";
else if(option == 1)
cout << "---VECTOR-----\n";
bool answer = false;
for(int i=0; i<board.size(); i )
{
for(int j=0; j<board[i].size(); j )
{
if(option == 0)
answer |= existHelperArrayVersion( word, 0, i, j, board);
else if(option == 1)
answer |= existHelperVectorVersion( word, 0, i, j, board);
if(answer)
{
return true;
}
}
}
return false;
}
int main()
{
string word = "AAAAAAAAAAAAAAB";
vector<vector<char>> board = {{'A','A','A','A','A','A'},
{'A','A','A','A','A','A'},
{'A','A','A','A','A','A'},
{'A','A','A','A','A','A'},
{'A','A','A','A','A','A'},
{'A','A','A','A','A','A'}};
auto start = high_resolution_clock::now();
bool answer = exist(board, word, 0);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout << "Time taken when Using C-style Array : " << duration.count() << " microseconds" << endl;
start = high_resolution_clock::now();
answer = exist(board, word, 1);
stop = high_resolution_clock::now();
duration = duration_cast<microseconds>(stop - start);
cout << "Time taken when Using STL vector : " << duration.count() << " microseconds" << endl;
}
output
----ARRAY------
Time taken when Using C-style Array : 112931 microseconds
---VECTOR-----
Time taken when Using STL vector : 330641 microseconds
As you can see the array version of my function performs on average 3 times faster than that of its Vector version. (I ran it multiple times and got similar results)
Question:
Are vectors really that slow compared to arrays?
I thought their performance was supposed to be on par.
This is the URL I run it on an online environment http://cpp.sh/6x22b
CodePudding user response：
vector<int> row_offset = {0, 0, 1, -1};
vector<int> col_offset = {1, -1, 0, 0};
this causes 2 heap allocations of data (almost) every time the function is called.
int row_offset[4]={0, 0, 1, -1};
int col_offset[4]={1, -1, 0, 0};
this does not cause 2 heap allocations of data (almost) every time the function is called.
std::vector<int> foo = {1,2,3} is similar to int* foo = new int[]{1,2,3}, not int foo[] = {1,2,3} in creation costs.
std::array<int, 3> foo={1,2,3}
is the std library version of "fixed size buffer with data in it". std::vector is a dynamically sized buffer.
Here is a live example where I swapped std::vector for std::array, and changed the C-array version to dynamically create and destroy the arrays. You'll notice the time swaps.
CodePudding user response：
You create your vectors in your function, so each function invocation allocates their memory anew and destroys them at the end of the function. An array is instead constantly baked into your program.
Try moving your vectors out of your function, then both functions are equally fast: http://cpp.sh/53t2z
CodePudding user response：
If you replace:
vector<int> row_offset = { 0, 0, 1, -1 };
vector<int> col_offset = { 1, -1, 0, 0 };
with:
static vector<int> row_offset; row_offset = { 0, 0, 1, -1 };
static vector<int> col_offset; col_offset = { 1, -1, 0, 0 };
the difference will be much less. With the second version the vectors won't be constructed from scratch each time.
This is only for demonstration purposes, and it's not an example to follow.
At any rate the best approach here is to replace std::vector with std::array since you have fixed sizes here.
BTW on http://cpp.sh the version with std::array even seems to be somewhat faster than the raw array version.