Измерение скорости выполнения сортировки [дубликат]

#c_sharp #net

        
             
                
                    
                        
                            На этот вопрос уже даны ответы здесь:
                            
                        
                    
                
                        
                            Время счета Bubble sort
                                
                                    (3 ответа)
                                
                        
                                Закрыт 2 года назад.
            
                    
В общем захотелось начать оптимизировать что-либо, например хочу начать с оптимизации
алгоритмов сортировки.

Как узнать скорость выполнения сортировки? 

По сути мне нужно узнать время, за которое программа выполняется. Как это сделать?
Пишу на C#
    

Ответы

Ответ 1

Прямой ответ на вопрос уже дан, но есть ощущение, что нужно многое уточнить.

Во-первых, нет смысла заниматься оптимизацией ради оптимизации.
Вот вам цитата из то ли Кнутта, то ли Дейкстры:


  Преждевременная оптимизация — корень всех (или большинства) проблем в программировании.


Оптимизация должна преследовать строго определённые цели - улучшить производительность
приложения в строго определённое количество раз (определяется нуждами пользователя)
в строго определённых местах, в которых текущая производительность ниже той, которая
необходима пользователю приложения. Реалии таковы, что оптимизацию можно производить
тысячью разных способов: смена алгоритма, смена структур данных, смена средств языка,
смена языка и так далее. Предела совершенству нет, поэтому любая оптимизация без чёткого
запроса пользователя - это время, потраченное впустую. Если в приложении не возникает
заметных провисаний, которые мешают приложению выполнять бизнес-функции, то никакая
оптимизация в действительности не нужна.

Во-вторых, что касается оптимизаций в .Net. Для 90% хорошего кода оптимизации не
нужны вовсе. Из оставшихся 10% в 90% случаев потребуется только оптимизация алгоритма.
В оставшихся 10% от 10% могут потребоваться различные хаки, специфичные структуры данных
и так далее. К последней категории относятся такие нагруженные продукты с большим мемори
траффиком, как компиляторы, ReSharper и ему подобные вещи. Проводя оптимизацию через
использование специфичных средств языка и структур данных, вы неизбежно снижаете сопровождаемость
продукта. И тут естественно встает вопрос поиска баланса между читаемостью кода и выигрышем
в производительности.

В-третьих, чтобы заниматься оптимизацией в .Net, нужно понимать, как работает компилятор,
как работает Jit, нужно понимать, что разные версия Jit'а делают различные оптимизации
вашего кода и ваш супер твик, который работает быстрее на вашей системе, в конечном
счете под другой версией Jit'а может работать медленнее. Различные гениальные советы,
которые тут и там всплывают в интернете, типа:


Никогда не используйте foreach, for - быстрее.
Вместо List<> используйте массивы, они быстрее
Не пользуйтесь Linq, он медленный
Разматывайте циклы (имеется в виду, например, возведение в степень, кратную 4, где
в каждоё итерации происходит a *= b 4 раза)


это всё от лукавого, ибо foreach, List и Linq достаточно быстры в подавляющем большинстве
случаев, а извращения, вроде разматывания циклов, могут убить оптимизацию компилятора,
который и без вас бы мог этот цикл размотать.

В-четвёртых, заниматься бенчмаркингом в .Net сложно корректно по тем же причинам,
что озвучены выше для занятия оптимизацией. Работа разных версий Jit, необходимость
"прогревать" метод перед бенчмарком, особенности работы сборщика мусора и так далее
- всё это осложняет получение честных данных замеров. Золотым стандартом в этой области
является использование BenchmarkDotNet - крутейшей библиотеки для проведения бенчмарков,
автором которой является Андрей Акиньшин из JetBrains, собственно, я так понимаю, продукт
был написан для внутреннего пользования и в частности для разработки ReSharper. И даже
этим фреймворком нужно пользоваться с головой.

Очень советую посмотреть вот это видео, в котором Андрей сам рассказывает о BenchmarkDotNet
и проблемах замеров времени в .Net.

Также советую посмотреть совсем недавний доклад Сергея Теплякова на тему паттернов
оптимизации в .Net приложениях.

В заключение хочу сказать, что если ваша цель - просто реализовать несколько алгоритмов
сортировки и сравнить их производительность на разных наборах данных - то использование
Stopwatch может дать вам вполне неплохие результаты в рамках исследовательской задачи.
Но если вопрос задан в контексте коммерческой разработки ПО, то тут уже появляется
множество нюансов, касающихся целесообразности и корректности проводимых оптимизаций.


Ответ 2

Для точных измерений с прогоном по несколько раз и вычичления среднего времени выполнения
кода следует воспользоваться готовыми библиотеками, наподобие BenchmarkDotNET, у них
отличное API, при чём удобное, в том числе, и для встраивания Ваших бенчмарков прямо
в Ваши тесты. 
Более простой способ измерения скорости выполнения без использования стандартных
библиотек - класс Stopwatch из пространства имён System.Diagnostics. Измерять скорость
выполнения кода можно таким образом:

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

//Замените на измеряемый код:
Thread.Sleep(1800);

stopwatch.Stop();

//Время, за которое выполнился Ваш код будет храниться в этой переменной:
var elapsedTime = stopwatch.Elapsed;


Значение переменной elapsedTime можете выводить на консоль или в Trace вашего теста
- как угодно. Опять же, если нужно замерять скорость выполнения кода во многих местах,
при чём регулярно, можно создать обёртку класса Stopwatch для выполнения измерений
с использованием IDisposable и помещать измеряемый код в блок using.