長陣列性能問題

我有一個長度爲175,000的char指針陣列。每個指針指向一個長度爲100的c字符串數組，每個字符爲1或0。我需要比較字符串之間的差異。長陣列性能問題

char* arr[175000];

到目前爲止，我有兩個for循環，我將每個字符串與每個其他字符串進行比較。比較函數基本上採用兩個c字符串，並返回一個整數，這是數組的差異數。

這對我的4核機器來說真的很長。我上次離開它運行45分鐘，它從未完成執行。請告知更快的解決方案或一些優化。

實施例：

000010 
000001

具有自最後兩個位的2的差不匹配。

後，我計算差值我值存儲在另一個數組

   int holder; 

       for(int x = 0;x < UsedTableSpace; x++){ 
        int min = 10000000; 

        for(int y = 0; y < UsedTableSpace; y++){ 

         if(x != y){ 
          //compr calculates difference between two c-string arrays 
          int tempDiff =compr(similarity[x]->matrix, similarity[y]->matrix); 

          if(tempDiff < min){ 
           min = tempDiff; 
           holder = y; 
          } 
         }  
        } 
        similarity[holder]->inbound++; 

       }

來源

2011-10-26 Mike G

發表一些代碼。 –

「我有一個長度爲175,000的char指針數組，每個指針指向一個長度爲100的c-string數組，每個字符都是1或0。這種設計是否需要修改？看起來*非常*效率低下。 – GManNickG

答案完全取決於「比較字符串之間的差異」的確切含義。平等？大？還有別的嗎？ – vz0

一個簡單的優化就是隻比較一次字符串。如果A和B之間的差值爲12，那麼B和A之間的差值也是12.您的運行時間將減少近一半。

在代碼：

int compr(const char* a, const char* b) { 
    int d = 0, i; 
    for (i=0; i < 100; ++i) 
    if (a[i] != b[i]) ++d; 
    return d; 
} 

void main_function(...) { 

    for(int x = 0;x < UsedTableSpace; x++){ 
     int min = 10000000; 

     for(int y = x + 1; y < UsedTableSpace; y++){ 

      //compr calculates difference between two c-string arrays 
      int tempDiff = compr(similarity[x]->matrix, similarity[y]->matrix); 

      if(tempDiff < min){ 
       min = tempDiff; 
       holder = y; 
      } 
     } 
     similarity[holder]->inbound++; 
    } 
}

注意的第二個for循環，我已經改變了初始索引。

其他一些優化是在單獨的線程上運行run方法以利用您的4個內核。

來源

2011-10-26 01:51:50 vz0

感謝您的回覆請詳細說明。運行運行命令。 –

我在發佈雙循環代碼之前回復。我已經更新了我的答案。 – vz0

+1：這種單一優化可能會爲最少的工作量提供最大的改進。 – StriplingWarrior

隨着越來越多的信息，我們也許可以給你更好的建議，但根據我所理解的問題，這裏有一些想法：

由於您使用每個字符來表示1或0，因此您使用的內存比您需要使用的多幾倍，這對緩存等產生了巨大的性能影響。相反，使用數字值表示您的數據，您可以用一系列位來考慮。
一旦你實現了＃1，你可以一次抓取一個整數或一個長整數，並執行按位XOR操作，最後得到一個數字，在每個地方這兩個數字沒有相同的值。然後你可以使用一些the tricks mentioned here來快速計數這些位。
在某種程度上「展開」循環以避免跳轉次數的需要。例如，下面的代碼：
```
total = total + array[i]; 
total = total + array[i + 1]; 
total = total + array[i + 2]; 
```
...的運行速度更快不僅僅是遍歷total = total + array[i]三次。跳轉很昂貴，並干擾處理器的流水線。 更新：我應該提到你的編譯器可能已經爲你做了一些這個 - 你可以檢查編譯後的代碼來查看。
將整體數據集分成塊，這樣可以充分利用緩存。把你的問題想象成一個「正方形」，一個軸上的i索引和另一個軸上的j軸。如果您從一個i開始並遍歷所有175000 j值，則您訪問的第一個j值將在您到達行末時從緩存中刪除。另一方面，如果從左上角開始並從j = 0到256，那麼當循環將它們與i = 0進行比較時，j軸上的大多數值仍將處於低級高速緩存中， 1,2等

最後，雖然這應該不言而喻，我想這是值得一提的：確保您的編譯器設置爲優化！

來源

2011-10-26 01:51:05 StriplingWarrior

感謝您的回覆。我添加了一些代碼。 –

將兩個字符串轉換爲長整數，xoring和做一些比特魔術似乎比較慢，然後只是比較兩個數組。 – vz0

@ vz0：重點是避免將其存儲在字符串中。 – GManNickG

你的目標是什麼，即想要得到它們之後，你想怎樣處理Hamming Distances（這就是它們）？例如，如果你正在尋找最近的一對，或者最遠的一對，你可能會得到一個O（n ln n）算法，而不是目前建議的O（n^2）方法。（在n = 175000時，n^2是n ln n的15000倍）

例如，可以用8個4位數表示每個100位數m，即8位中設置的位數m的段，並將結果的32位簽名按升序排序。最接近的對的簽名可能在排序列表中附近。如果兩個數字的簽名不同，很容易降低兩個數字之間的距離，從而發現有效的分支和邊界過程，因爲找到的數字較少。

來源

2011-10-26 05:54:21

長陣列性能問題

回答

相關問題