SortedList를 통한 순환 - 왜 이렇게 빠른가요?

Question

다음 예제의 List1은 SortedList (Of MyClass)이며 251 개의 멤버가 포함되어 있습니다.

처음 두 개의 코드 블록은 15.5 초 내에 실행됩니다.

 

For cnt As Integer = 1 To 1000000 
     For Each TempDE In List1 
      Dim F As String = TempDE.Key 
      TempDE.Value.x1 = 444 
     Next 
    Next 

는

For cnt As Integer = 1 To 1000000 
     For Each TempDE As KeyValuePair(Of String, phatob) In List2 
      Dim F As String = TempDE.Key 
      TempDE.Value.x1 = 444 
     Next 
    Next 

이것은 5.6 초 행한다.

For cnt As Integer = 0 To 999999 
     For cnt2 As Integer = 0 To 250 
      Dim F As String = List1.Keys(cnt2) 
      List1.Values(cnt2).x1 = 444 
     Next 

    Next 

왜 그렇게 느린 처음 두 codeblocks입니까?

Answer 1

SortedList는 정렬 기능을 제공하기 위해 IComparer를 구현하여 Collection을 확장합니다. 내부적으로는 목록의 요소를 저장하는 2 개의 배열 (키에 대한 배열 하나와 값에 대한 배열)을 구현합니다. .NET Array는 빠른 순서대로 빠른 무작위 액세스에 최적화되어 있습니다.

처음 2 개가 느린 이유는 SortedList의 foreach 문이 열거 자 주위의 래퍼이기 때문입니다. foreach를 호출하면 열거자를 쿼리하고 MoveNext 및 Current를 호출합니다. 또한 일반적인 목록은 잠재적으로 목록을 탐색 할 때 복싱 및 언 박싱과 관련 될 수 있으며 일반적으로 Index를 통해 액세스하지 않으면 얻을 수없는 성능 오버 헤드를 생성 할 수 있습니다.

Answer 2

정확히 어떻게 For Each이 동작하는지에 대한 몇 가지 문서를 살펴 보려고했지만 찾으려고하지 않았습니다.

내 이론은 For Each 문을 사용하면 목록의 개체를 메모리의 다른 지점으로 복사 한 다음 루프의 각 반복이 끝날 때 목록에 다시 복사한다는 것입니다.

또 다른 가능성은 반복 할 때마다 생성자를 호출 한 다음 생성자를 다시 해체하고 호출하여 다음 반복을 다시 설정한다는 것입니다.

나는이 이론 중 하나에 대해서는 잘 모르겠지만, 3과 (1 또는 2) 사이의 주된 차이는 For Each의 부족이다.

편집 : MSDN에서 일부 설명서를 찾았습니다. 각 ... Next 루프의 실행이 시작되면

는 비주얼 베이직 그룹 유효한 컬렉션 오브젝트를 참조하는지 확인 :

여기 발췌이다. 그렇지 않은 경우에는 예외가 발생합니다. 그렇지 않으면 MoveNext 메서드와 열거 자 개체의 Current 속성을 호출하여 첫 ​​번째 요소를 반환합니다. 다음 요소가 없다는 것을 MoveNext가 나타내는 경우, 즉 컬렉션이 비어있는 경우 For Each 루프가 종료되고 제어가 다음 문의 다음 문으로 넘어갑니다. 그렇지 않으면 Visual Basic 요소를 첫 번째 요소로 설정하고 문 블록을 실행합니다.

따라서 전체적으로 For Each은 "관리"되고 모든 것이 일치하는지 확인하는 데 많은 오버 헤드가 발생합니다. 결과적으로 속도가 느려집니다.

Answer 3

저는 컴파일러가 고정 루프 범위 때문에 블록 3을 더 잘 최적화 할 수 있다고 생각합니다. 블록 1과 2에서 컴파일러는 List를 평가할 때까지 루프의 상한이 무엇인지 알지 못하므로 목록을 느리게 만듭니다.

Answer 4

내 임의 추측 : List1에는 750 개 요소 (250 개가 아닌)가 포함되어 있습니다. 세 번째 대문자는 List1이 가진 각 요소를 반복하지 않기 때문에 빠릅니다.