C＃緩慢搜索

Question

我做了一個簡單的數組，其中包含2,000,000個整數，用於保存所有RGB，另一個數組保存2,000,000個整數，用於檢測rgb的次數。然後我把它通過所有600萬個字節的圖片，像這樣的循環：

 uint[] colors = new uint[rawImageBytes.Length/3]; 
     int[] hits = new int[rawImageBytes.Length/3]; 

     int colorAmount  = 0; 
     int totalRepeats = 0; 
     int lastTime  = Environment.TickCount; 
     int lastCount  = 0; 
     uint currentColor = 0; 
     bool found; 

     for (int i = 0; i < rawImageBytes.Length - 3; i += 3) 
     { 
      if (Environment.TickCount - lastTime > 10000) 
      { 
       setStatus(((i - lastCount)/10) + " checks per second"); 
       lastTime = Environment.TickCount; 
       lastCount = i; 
      } 


      currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16)); 

      //set it to false to see if pattern exists 
      found = false; 

      //check all patterns 
      for (int k = 0; k < colorAmount; k++) 
      { 
       //if pattern exists 
       if (colors[k] == currentColor) 
       { 
        //dont add it and increase the hit instead 
        found = true; 
        hits[k]++; 
       } 
      } 

      //if pattern does not exist, set it 
      if (found == false) 
      { 
       colors[colorAmount] = currentColor; 
       hits[colorAmount] = 0; 
       colorAmount++; 
      } 
     } 

我的日誌顯示，他們的速度從搜索範圍每秒

增加

5724檢查顯著減慢每秒

5959檢查

5847檢查每秒

6044檢查每每秒鐘

11469檢查每秒

7096檢查第二

6318檢查每秒

8530檢查每秒

10680檢查每秒

16233檢查

如何使我的搜索更高效，以便不需要20分鐘？

Answer 1

第一個問題我看到的是，你的命中陣列ecxessively大。如果你認爲一種顏色可能會被多次擊中，那麼你的命中數組必須比你的顏色數組短。

我看到的第二個問題是，你不停止迭代後，你發現你的顏色在顏色數組。你應該放置休息;found = true;聲明。

爲什麼你不喜歡字典< uint，int> type for your hits collection？你的顏色應該是一個重點和命中數應該是一個值：

uint[] colors = new uint[rawImageBytes.Length/3]; 
    Dictionary<uint,int> hits = new Dictionary<uint,int>(); 

    int colorAmount  = 0; 
    int totalRepeats = 0; 
    int lastTime  = Environment.TickCount; 
    int lastCount  = 0; 
    uint currentColor = 0; 


    for (int i = 0; i < rawImageBytes.Length - 3; i += 3) 
    { 
     if (Environment.TickCount - lastTime > 10000) 
     { 
      setStatus(((i - lastCount)/10) + " checks per second"); 
      lastTime = Environment.TickCount; 
      lastCount = i; 
     } 


     currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16)); 


     if (hits.ContainsKey(currentColor)) 
     { 
      hits[currentColor]++; 
     } 
     else 
     { 
      hits.Add(currentColor,1); 
     } 

    } 

而且還嘗試啓用optimization instruction for compiler。

Answer 2

有一個原則，我認爲這不適用於此，這將增加性能。從我所看到的，你的數組沒有排序和搜索是線性的。因此，對於第一個數組中的每一行，都會搜索第二個數組中的所有行。

這裏有一些事情進行測試： - 排序第二陣列（在其上執行搜索） - Array.find（）代替循環自行

Answer 3

你可以嘗試使用color-列表計數對（而不是你的兩個數組），並保持它在顏色索引上排序。然後使用二進制搜索來查找重複的顏色。我懷疑這會比使用字典更快，但這可能也值得嘗試（？）。

排序和二進制搜索：http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx#Y700

詞典：http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

Answer 4

這看起來像一個良好的用例進行並行 而不是做所有的計算/等填充自己，讓剛剛讓LINQ要小心，

首先，讓我們把你的迭代器的邏輯到它自己的方法，這樣您可以在單獨調整：

IEnumerable<uint> GetColors(byte[] rawImageBytes) 
{ 
    int lastTime  = Environment.TickCount; 
    for (int i = 0; i < rawImageBytes.Length - 3; i += 3) 
    { 
     if (Environment.TickCount - lastTime > 10000) 
     { 
      setStatus(((i - lastCount)/10) + " checks per second"); 
      lastTime = Environment.TickCount; 
      lastCount = i; 
     } 


     currentColor = (uint)((rawImageBytes[i] << 0) | (rawImageBytes[i + 1] << 8) | (rawImageBytes[i + 2] << 16)); 

     yield return currentColor; 
    } 
} 

現在讓我們來重寫你的方法一點用PLINQ：

var results = (from color in GetColors(rawImageBytes).AsParallel() 
       group by color into g 
       select new { Color = g.Key, Count = g.Count()}).ToList(); 

var uniqueColours = results.Count(); 
var totalHits = results.Select(r=>r.Count()).Sum(); 

（writt EN沒有編譯器方便，所以你可能需要調整它）

看看是怎麼回事。