下面是我用來比較的代碼:
// 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;
}
輸出
----ARRAY------
Time taken when Using C-style Array : 112931 microseconds
---VECTOR-----
Time taken when Using STL vector : 330641 microseconds
如您所見,我的函數的數組版本的執行速度平均比其 Vector 版本快 3 倍。(我多次運行並得到了類似的結果)
問:
與數組相比,向量真的那麼慢嗎?
我認為他們的表現應該是相提並論的。
這是我在在線環境中運行的 URL http://cpp.sh/6x22b
vector<int> row_offset = {0, 0, 1, -1};
vector<int> col_offset = {1, -1, 0, 0};
每次調用該函數時,這都會導致 2 堆數據分配(幾乎)。
int row_offset[4]={0, 0, 1, -1};
int col_offset[4]={1, -1, 0, 0};
每次調用該函數時,這不會(幾乎)導致 2 堆數據分配。
std::vector<int> foo = {1,2,3}
類似於int* foo = new int[]{1,2,3}
,而不是int foo[] = {1,2,3}
創建成本。
std::array<int, 3> foo={1,2,3}
是“帶有數據的固定大小緩衝區”的標準庫版本。std::vector
是一個動態大小的緩衝區。
這是一個實時示例,我交換std::vector
了std::array
,並更改了 C 數組版本以動態創建和銷毀數組。你會注意到時間交換。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句