快速初始化大鋸齒陣列

Question

我有一個鋸齒陣列，代表Grid，每個陣列項目是Cell。 Grid有2600行和2600列。我需要計算每個Cell的座標，創建對象Cell的實例並將其添加到數組中。現在我使用的代碼在我的電腦上大約需要3200-3800 ms。有什麼辦法可以讓它更快嗎？

public GridCell[][] Cells; 
private void CreateCells(int cellWidth, int cellHeight, int startX, int startY) 
    {   
     Cells = new GridCell[RowsCount][]; 
     for (int i = 0; i < RowsCount; i++) 
     { 
      Cells[i] = new GridCell[ColumnsCount]; 
      for (int j = 0; j < ColumnsCount; j++) 
      { 
       Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i); 
       Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate); 
      } 
     } 
    } 

Answer 1

您在這兩個GridCell和Point是類的評論中提到。類是迄今爲止最常見的創建類，但如果你對不同的語義可以接受，並且它們大多數保存數據而不是功能，那麼可以將它們轉換爲結構。

結構幾乎像一個類，但它是一個值類型而不是引用類型。這意味着，這樣的代碼：

Point a = new Point(0, 0); 
Point b = a; 
b.X = 5; 
Console.WriteLine(a); 

...將打印0，如果它是一個結構和5如果它是一個類。

這些語義允許將結構體嵌入其他事物中，而不必在堆上擁有自己的空間。從堆中分配可能會很昂貴，因此，如果可以分配一組結構，則只需分配一個分配而不是多個分配。

Answer 2

考慮使用Parallel.For - 像這樣的東西對於多線程來說是微不足道的。如圖所示，如果你願意改變功能（在這種情況下通過使用結構，但分配單個數組也可能有一些好處），其他地方可以找到更大的初始增益，但仍然可以使用線程來提高性能。

一些簡單的測試：

//Single Threaded   : 1701, 1825, 1495, 1606 
//Multi Threaded   : 1516, 1446, 1581, 1401 
//Struct Single Threaded : 154, 157, 153, 151 
//Struct MultiThreaded  : 104, 107, 106, 103 

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Threading.Tasks; 

namespace ConsoleApplication3 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      while (true) 
      { 
       Benchmark("Single Threaded",() => CreateCells(1, 1, 0, 0)); 
       Benchmark("Multi Threaded",() => CreateCellsThreaded(1, 1, 0, 0)); 
       Benchmark("Struct Single Threaded",() => CreateStructCells(1, 1, 0, 0)); 
       Benchmark("Struct MultiThreaded",() => CreateStructCellsThreaded(1, 1, 0, 0)); 
      } 
     } 

     static void Benchmark(string Name, Action test) 
     { 
      var sw = Stopwatch.StartNew(); 
      test(); 
      UpdateResults(Name, sw.ElapsedMilliseconds.ToString()); 
      GC.Collect(); 
     } 

     static Dictionary<string, string> results = new Dictionary<string, string>(); 
     static void UpdateResults(string key, string value) 
     { 
      value = value.PadLeft(4); 
      if (results.ContainsKey(key)) 
       results[key] += ", " + value; 
      else 
       results[key] = value; 

      Console.Clear(); 
      foreach (var kvp in results) Console.WriteLine(kvp.Key.PadRight(25) + ": " + kvp.Value); 
     } 

     const int RowsCount = 2600; 
     const int ColumnsCount = 2600; 

     public class Point 
     { 
      public int x; 
      public int y; 
      public Point(int x, int y) 
      { 
       this.x = x; 
       this.y = y; 
      } 
     } 

     public class GridCell 
     { 
      public int width; 
      public int height; 
      public Point point; 
      public GridCell(int width, int height, Point point) 
      { 
       this.width = width; 
       this.height = height; 
       this.point = point; 
      } 
     } 

     public struct StructPoint 
     { 
      public int x; 
      public int y; 
      public StructPoint(int x, int y) 
      { 
       this.x = x; 
       this.y = y; 
      } 
     } 


     public struct StructGridCell 
     { 
      public int width; 
      public int height; 
      public StructPoint point; 
      public StructGridCell(int width, int height, StructPoint point) 
      { 
       this.width = width; 
       this.height = height; 
       this.point = point; 
      } 
     } 

     private static void CreateCells(int cellWidth, int cellHeight, int startX, int startY) 
     { 
      var Cells = new GridCell[RowsCount][]; 
      for (int i = 0; i < RowsCount; i++) 
      { 
       Cells[i] = new GridCell[ColumnsCount]; 
       for (int j = 0; j < ColumnsCount; j++) 
       { 
        Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i); 
        Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate); 
       } 
      } 
     } 
     private static void CreateCellsThreaded(int cellWidth, int cellHeight, int startX, int startY) 
     { 
      var Cells = new GridCell[RowsCount][]; 
      Parallel.For(0, RowsCount, new ParallelOptions { MaxDegreeOfParallelism = 4 }, i => 
      { 
       Cells[i] = new GridCell[ColumnsCount]; 
       for (int j = 0; j < ColumnsCount; j++) 
       { 
        Point coordinate = new Point(startX + cellWidth * j, startY + cellHeight * i); 
        Cells[i][j] = new GridCell(cellWidth, cellHeight, coordinate); 
       } 
      }); 
     } 

     private static void CreateStructCells(int cellWidth, int cellHeight, int startX, int startY) 
     { 
      var Cells = new StructGridCell[RowsCount][]; 
      for (int i = 0; i < RowsCount; i++) 
      { 
       Cells[i] = new StructGridCell[ColumnsCount]; 
       for (int j = 0; j < ColumnsCount; j++) 
       { 
        var coordinate = new StructPoint(startX + cellWidth * j, startY + cellHeight * i); 
        Cells[i][j] = new StructGridCell(cellWidth, cellHeight, coordinate); 
       } 
      } 
     } 
     private static void CreateStructCellsThreaded(int cellWidth, int cellHeight, int startX, int startY) 
     { 
      var Cells = new StructGridCell[RowsCount][]; 
      Parallel.For(0, RowsCount, i => 
      { 
       Cells[i] = new StructGridCell[ColumnsCount]; 
       for (int j = 0; j < ColumnsCount; j++) 
       { 
        var coordinate = new StructPoint(startX + cellWidth * j, startY + cellHeight * i); 
        Cells[i][j] = new StructGridCell(cellWidth, cellHeight, coordinate); 
       } 
      }); 
     } 
    } 
} 

Answer 3

考慮您正在使用676萬個對象時，你有一個優良的性能。主要的時間可能是花在堆上構建新的對象。正如你所觀察到的，所以使用結構而非班級可以提高你的興趣。

如果您有大量的CPU緩存你也可以嘗試使用單一陣列中，如：

public GridCell[] Cells = new GridCell[RowsCount * ColumnsCount]; 

與解決，如：

Cells[i * ColumnsCount + j] = x;