下面是我用來比較的代碼：
// 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
uj5u.com熱心網友回復：
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 陣列版本以動態創建和銷毀陣列。你會注意到時間交換。
uj5u.com熱心網友回復：
您在函式中創建向量，因此每個函式呼叫都會重新分配它們的記憶體并在函式結束時銷毀它們。相反，陣列會不斷地烘焙到您的程式中。
嘗試將向量移出函式，然后兩個函式同樣快：http : //cpp.sh/53t2z
uj5u.com熱心網友回復：
如果更換：
vector<int> row_offset = { 0, 0, 1, -1 };
vector<int> col_offset = { 1, -1, 0, 0 };
和：
static vector<int> row_offset; row_offset = { 0, 0, 1, -1 };
static vector<int> col_offset; col_offset = { 1, -1, 0, 0 };
差異會小很多。在第二個版本中，向量不會每次都從頭開始構建。
這僅用于演示目的，并不是要遵循的示例。
無論如何，這里最好的方法是替換為std::vector，std::array因為這里有固定的尺寸。
順便說一句，http: //cpp.sh 上的std::arrayeven版本似乎比原始陣列版本快一些。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/354258.html
上一篇：合并具有相同日期的物件資料
下一篇：在JSONB陣列中強制唯一性