優化此代碼的方法

Question

我正在探索如何優化下面的代碼。代碼循環遍歷一個字符串。對於字符串中的第i個 字符， 代碼會在第i列的第二個數組中增加一個條目。第i列 的確切值遞增取決於字符串中第i個字符的值; 字符串中的每個字母都有一行。 通過循環多個字符串並遞增相同的2d數組（count）， 爲字符串計算每個字符的出現次數。

的代碼如下：

string read = getReadFromData(); 
vector< vector<int> > count(4,vector<int>(read.size(),0)); 
for (int i = 0; i < read.size(); i++) { 
    switch(read[i]) {           
    case 'A': count[0][i]++; break; 
    case 'T': count[1][i]++; break; 
    case 'C': count[2][i]++; break; 
    case 'G': count[3][i]++; break; 
}  

我的優化嘗試一直是使2D陣列的使用一維數組中，代替 ;旨在避免緩存未命中，如果字符串數據本身 在內存中不連續。不幸的是，它並沒有減少計算時間;他們大致相當。

string read = getReadFromData(); 
int width = read.size() 
vector<int> count(4*width,0); 
for (int i = 0; i < width; i++) { 
    switch(read[i]) {           
    case 'A': count[   i]++; break; 
    case 'T': count[ width + i]++; break; 
    case 'C': count[2 * width + i]++; break; 
    case 'G': count[3 * width + i]++; break; 
} 

有沒有人對如何優化這個問題有什麼建議？ 切換行和列？或者改變增量的間隔？ 感謝您的任何建議。

更新：一個優化
所以，我認爲，主要問題是：

1）輸入的不可預測性;在 2D或1D版本中訪問的存儲器位置取決於輸入字符。 2）在1D的例子中，相應位置之間的距離相隔很遠。此外，在2D中，但我正在優化1D示例。

在上面的1D示例中，i+1的潛在位置相隔很遠; i+1，i+1 + width，i+1 + 2*width，i+1 + 3*width。我認爲訪問的不可預測性以及與i+1的較大距離導致緩存失誤過多 - 我會在某些時候緩存緩存。
優化的目的是減少到訪問的距離。 要做到這一點，我交錯的A，T，G，C計數，這樣的i+1 th元素 是最多7個條目;距離要小得多。

string read = getReadFromData(); 
int width = read.size() 
vector<int> count(4*width,0); 
for (int i = 0; i < width; i++) { 
    switch(read[i]) {           
    case 'A': count[i*4 ]++; break; 
    case 'T': count[i*4 + 1]++; break; 
    case 'C': count[i*4 + 2]++; break; 
    case 'G': count[i*4 + 3]++; break; 
} 

現在我得到一個> 5倍加速，這是美味。

Answer 1

一個想法是預先計算陣列作爲指針：
注：未測試的代碼如下

vector< vector<int> > count(4,vector<int>(read.size(),0)); 
std::vector<int> * const p_a_counts = &count[0]; 
std::vector<int> * const p_t_counts = &count[1]; 
std::vector<int> * const p_c_counts = &count[2]; 
std::vector<int> * const p_g_counts = &count[3]; 

for (int i = 0; i < read.size(); i++) { 
    switch(read[i]) {           
    case 'A': p_a_counts->[i]++; break; 
    case 'T': p_t_counts->[i]++; break; 
    case 'C': p_c_counts->[i]++; break; 
    case 'G': p_g_counts->[i]++; break; 
} 

的想法是減小計算對於各種陣列。

注：您的代碼看起來不正確。如果讀取的第二個字母是'T'，則第二個位置遞增，而不是第一個。雖然你可以計算'T'在第二位的次數。

編輯1：不同的角度
處理器更喜歡訪問相同的數據區域，換句話說，利用他們的數據緩存。

所以，角度改變的視圖數據點：

string read = getReadFromData(); 
vector< vector<int> > count(4,vector<int>(read.size(),0)); 

for (int i = 0; i < read.size(); i++) 
{ 
    if (read[i] == 'A') 
    {           
    count[0][i]++; 
    } 
} 
for (int i = 0; i < read.size(); i++) 
{ 
    if (read[i] == 'T') 
    {           
    count[1][i]++; 
    } 
} 
for (int i = 0; i < read.size(); i++) 
{ 
    if (read[i] == 'C') 
    {           
    count[2][i]++; 
    } 
} 
for (int i = 0; i < read.size(); i++) 
{ 
    if (read[i] == 'G') 
    {           
    count[3][i]++; 
    } 
} 

上述應保持數據的高速緩存內的count陣列用於不同的目的。

Answer 2

正如托馬斯馬修斯在他的評論中提出的使用不同數據結構的建議，經常標準庫給出的數據結構比你想象的要慢。嘗試使用只是一個普通的數組工作代碼

int *count = new int [4 * width];