Циклическое перебор 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

Почему первые два кодовых блока настолько медленнее?

Answer 1

SortedList расширяет коллекцию, реализуя IComparer для обеспечения функций сортировки.Внутри он реализует два массива для хранения элементов списка: один для ключа, другой для значений..NET Array оптимизирован для быстрого упорядоченного и быстрого произвольного доступа.

Я подозреваю, что первые два работают медленно потому, что оператор foreach в SortedList является оболочкой Enumerator.Вызов foreach запросит перечислитель, вызовет MoveNext и Current.Кроме того, просмотр общего списка потенциально может включать в себя упаковку и распаковку при перемещении по списку и может привести к увеличению производительности, чего вы обычно не получаете при доступе по индексу.

Answer 2

Я попытался поискать документацию о том, как именно For Each ведет себя, но я не смог его найти.

Моя теория заключается в том, что использование For Each Операторы копируют объект из списка в другое место в памяти, а затем копируют его обратно в список по завершении каждой итерации цикла.

Другая возможность заключается в том, что он вызывает конструктор в начале каждой итерации, а затем деконструирует и снова вызывает конструктор для сброса для следующей итерации.

Я не уверен ни в одной из этих теорий, но основная разница между 3 и (1 или 2) заключается в отсутствии For Each.

РЕДАКТИРОВАТЬ:Нашел документацию на MSDN.

Вот отрывок:

Когда начинается выполнение цикла For Each...Next, Visual Basic проверяет, что группа ссылается на допустимый объект коллекции.Если нет, то выдается исключение.В противном случае он вызывает метод MoveNext и свойство Current объекта перечислителя, чтобы вернуть первый элемент.Если MoveNext указывает, что следующего элемента нет, то есть если коллекция пуста, цикл For Each завершается и управление передается инструкции, следующей за инструкцией Next.В противном случае Visual Basic присваивает элементу значение первого элемента и запускает блок операторов.

В целом это звучит так For Each более «управляемый» и требует больших затрат, чтобы убедиться, что все совпадает.В результате это происходит медленнее.

Answer 3

Я думаю, что компилятор сможет лучше оптимизировать блок 3 из-за диапазона фиксированного цикла.В блоках один и 2 компилятор не будет знать, каков верхний предел цикла, пока не оценит список, что замедляет его работу.

Answer 4

Мое случайное предположение:List1 содержит ~750 элементов (а не только 250).Ваш третий случай быстрее, потому что он не перебирает каждый элемент, который есть в List1.