C # Для цикла, в то время как цикл, LastIndexOf, IndexOf, почему последние 2 быстрее?

Question

Я провел некоторое тестирование производительности в C # при использовании цикла For Loop и While Loop для ArrayList для поиска в сравнении.

Кажется, что он имеет квадратичное потребление времени.

Однако, если я использую LastIndexOf или IndexOf для поиска в списке, он набирает скорость «быстрее, чем ожидалось».

Кто-нибудь знает причину?

Answer 1

Используйте ILSpy и взгляните на внутренние методы LastIndexOf / IndexOf.Там лежит ваш ответ о том, почему они быстрее.

У меня есть догадка, что список внутренне использует B-дерево или какое-то другое дерево, которое имеет поиск log (n).То, что вы делаете с for / foreach, выполняет линейный поиск с некоторыми дополнительными издержками.Если вы помните свой класс по математике, вы знаете, что log (n) более плоский, чем линейная линия, поэтому поиск будет быстрее ...

Answer 2

Я не знаю любой C #, и все же я могу выдвинуть вероятный ответ.

Любой метод языка программирования, как правило, написан так, чтобы использовать преимущества ярлыков, предоставляемыхпроцессор, на котором они работают, - который не будет написан вашим собственным написанным кодом (например, вам придется объявлять локальные переменные, которые должны храниться в стеке, требуя более медленного времени поиска, а не просто как временная переменная регистра).Таким образом, все, что делает язык изначально, будет быстрее, чем ваш собственный код.