큰 지그재그 배열의 빠른 초기화

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 클래스이다 코멘트에 언급했다. 클래스가 가장 많이 생성되는 클래스이지만, 다른 의미가 있어도 기능성보다는 데이터를 보유하고 있다면 구조체로 변환 할 수 있습니다.

struct는 거의 클래스와 비슷하지만 참조 유형이 아닌 값 유형입니다.

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

... 그것은 클래스의 경우는 구조체 및 5의 경우 0을 인쇄합니다 :이 이런 식으로 그 코드를 의미한다.

이러한 의미 체계를 사용하면 구조체가 다른 것들에 포함될 수 있으며 힙에 자체 공간이있을 필요가 없습니다. 힙에서 할당하는 것은 비용이 많이들 수 있습니다. 예를 들어, 구조체의 배열을 할당 할 수 있다면 많은 할당보다는 하나의 할당 만 수행하면됩니다.

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

당신이 6,760,000 개체를 사용하여 작업하는 고려, 당신은 좋은 성능을 가지고있다. 그리고 주 시간은 아마도 힙에 새로운 객체를 만드는 데 쓰일 것입니다. 따라서 클래스 대신 구조체를 사용하면 관찰 한 것처럼 향상시킬 수 있습니다.

당신이 큰 CPU 캐시가있는 경우 당신은 또한 같은 단일 배열 사용하려고 할 수 있습니다 : 같은 주소로

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

을 :

Cells[i * ColumnsCount + j] = x;