리사이즈시 불필요한 복사를 방지하는 버퍼가있는 고성능 어레이?

Question

저는 모델링 프로젝트를 위해 C#에서 고성능 배열이 필요합니다. 이 배열은 자주 크기를 조정해야합니다 (내용 보존). 인덱스에 자주 액세스되며 수십억 개의 조회를 수행 할 때 List가 일반적인 배열 []만큼 잘 수행되지 않는다는 느낌이 들게됩니다.

는 원래 VB.NET에서 나는 큰 배열 &을 수동으로 수를 유지하여,이에게 자신을 관리 :

이

private _populations() as Population 
private _populationCount as Integer 

' When adding a population... 
_populationCount += 1 ' Update true count of populations, not the arraysize 
if _populationCount > _populations.Length then 
    'if adding a population & array has run out of space, increase by a buffer of 20%: 
    Redim Preserve _populations(_populationCount * 1.2) 
end if 

내가 쉽게 C#으로이를 구현할 수 있지만, 도구가 이미이 있는지 궁금 하군요 .NET Framework에서이 작업을 수행 할 수 있습니까? 성능이 중요하므로 우아함 또는 모범 사례를 위해 어떤 성능 저하도 허용 할 수 없습니다.

P. 수동으로 요소를 재사용 할 때 삽입 또는 제거에 대해 걱정하지 않습니다.

Answer 1

List<T>으로 시작하십시오. 그런 다음 프로파일 러를 사용하여 응용 프로그램의 병목 지점을 확인하십시오. List<T>이 실제로 병목 현상이 나타나는 경우 List<T>의 코드를 복제하여 이론적으로 최적화 할 수 있으며 필요하지 않은 검사 중 일부를 제거 할 가능성이 있습니다 당신이 색인이 유효하다는 것을 확실하게 보장 할 수 있기 때문에 모든 전화.

초기 용량을 지정하여 List<T> 비트를 최적화 할 수도 있습니다.이 용량은 사용하는 것보다 더 큰 값입니다. 이렇게하면 백킹 어레이를 확장/복사 할 필요가 줄어 듭니다.

Answer 2

나는 Array.Resize<T>을 사용하여 배열 크기를 조정하기 위해 C#에 내장되어 있으며 VB 솔루션을 다시 구현하는 방법이 될 것이라고 생각합니다. 그러나 하나의 배열에서 새로운 배열로 요소 사본을 포함합니다.

고성능이 필요한 경우 배열의 연결된 목록을 관리하는 클래스를 만드는 것이 좋습니다. this answer에 따르면이 개념은 StringBuilder이 효율적으로 작동하는 방식입니다.

노동을 소비하기 전에 측정하십시오. 너는 그것을 필요로하지 않을 수도있다.

Answer 3

답변 해 주셔서 감사합니다. 평범한 구 어레이가리스트 <>보다 성능이 뛰어납니다. 이것은 &을 List <>으로 검색하는 것이 함수 호출 (예 : 심지어 mylist [i]가 인덱스 속성 getter에 대한 함수 호출)을 포함한다는 사실에 기인한다고 생각합니다. 배열에서는 직접 메모리 연산입니다. 크기 조정은 거의 동일하게 수행됩니다. 따라서

-       Array  List 
Instantiating:    0   0 
Iterating/Populating:  324ms  471ms 
Iterating/Retrieving:  215ms  380ms 
Resizing:     160ms  160ms 

, 성능 차이는 거의 모든 실제 애플리케이션에 무시할 수있는 동안 나는 평범한 구식 배열을 사용하는 것이 성능 요구 사항 주어진 다음과 같이

는 40,000,000의 데이터 세트를 처리 성능이었다 .

코드 :

class Program 
{ 
    static void Main(string[] args) 
    { 
     Console.WriteLine("Press A for array; L for list. These are run separately to avoid memory management getting in the way of a clean test."); 
     var key = Console.ReadKey(true); 
     if (key.Key == ConsoleKey.L) 
     { 
      for (var i = 0; i < 5; i++) 
      { 
       Console.WriteLine("List run " + i); 
       TestList(); 
       Console.WriteLine(); 
      } 
     } 
     else if (key.Key == ConsoleKey.A) 
     { 
      for (var i = 0; i < 5; i++) 
      { 
       Console.WriteLine("Array run " + i); 
       TestArray(); 
       Console.WriteLine(); 
      } 
     } 

     Console.WriteLine("Done."); 
     Console.ReadKey(); 
    } 

    private const int DataSize = 40000000; // The limit of my old laptop :(

    private static int[] GetBaseData() 
    { 
     return new int[DataSize]; 
    } 

    private static void TestList() 
    { 
     int[] baseData; 

     using (time("creating base data")) 
     { 
      baseData = GetBaseData(); 
     } 

     List<int> testData; 
     using (time("Initialization")) 
     { 
      testData = new List<int>(DataSize); 
     } 

     using (time("Populating using FOR (not FOREACH)")) 
     { 
      var c = baseData.Count(); 
      for (var i = 0; i < c; i++) 
      { 
       testData.Add(baseData[i]); 
      } 
     } 

     using (time("Iterating & retrieving with FOR (not FOREACH)")) 
     { 
      var c = testData.Count(); 
      var v = 0; 
      var oi = 0; 
      for (var i = 0; i < c; i++) 
      { 
       oi = testData[i]; 
       v += oi; 
      } 
     } 

     using (time("Resizing")) 
     { 
      testData.Add(1); // Enough to push it over the original limit 
     } 
    } 

    private static void TestArray() 
    { 
     int[] baseData; 

     using (time("creating base data")) 
     { 
      baseData = GetBaseData(); 
     } 

     int[] o; 
     using (time("Initialization")) 
     { 
      o = new int[DataSize]; // SomeClass[DataSize]; 
     } 

     using (time("Populating with FOR")) 
     { 
      var c = baseData.Count(); 
      for (var i = 0; i < c; i++) 
      { 
       o[i] = baseData[i]; 
      } 
     } 

     using (time("Iterating FOR")) 
     { 
      var v = 0; 
      var c = o.Count(); 
      var oi = 0; 
      for (var i = 0; i < c; i++) 
      { 
       oi = o[i]; 
       v += oi; 
      } 
     } 

     using (time("Resizing")) 
     { 
      Array.Resize(ref o, DataSize * 2); // NOTE: this doubles to match List behavior but further efficiencies could be gained with lower values eg. 1.2 
     } 
    } 

    private static TimeAdviser time(string message) 
    { 
     return new TimeAdviser(DataSize + ": " + message, (x) => Console.WriteLine(x)); 
    } 

    private class TimeAdviser : IDisposable 
    { 
     public DateTime Start; 
     public string Message; 
     public Action<string> OnComplete; 

     public TimeAdviser(string message, Action<string> onComplete) 
     { 
      Start = DateTime.Now; 
      Message = message; 
      OnComplete = onComplete; 
     } 

     public void Dispose() 
     { 
      OnComplete(Message + " time taken: " + (DateTime.Now -Start).TotalMilliseconds); 
     } 
    } 
}