Способы оценки эффективности

Для оценки эффективности выполнения алгоритмов сортировки в программе реализованы одновременно два способа:

1. Подсчет условной эффективности по формуле Eff=Comp+Chang*10, где Comp – кол-во сравнений, Chang – кол-во присваиваний, задействованных в ходе выполнения алгоритма..

2. Замер времени выполнения алгоритма при многочисленных его повторениях (кол-во повторений задается пользователем, по умолчанию равно 1000000).

Эффективность определяется по принципу – чем меньше задействовано операций (или затрачено времени), тем лучше.

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

Для оценки эффективности выполнения алгоритмов поиска условно примем кол-во операций сравнений и общее кол-во итераций в цикле.

Реализация подсчета кол-ва сравнений, присваиваний и эффективности в программе

Для подсчета кол-ва присваиваний и сравнений перед или после соответствующих действий в алгоритме увеличиваются соответствующие счетчики. Например, такой простой код …

for(i=0; i< size; i++)

a++;

будет дополнен следующими строчками кода для подсчета эффективности:

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием начального значения для счетчика в цикле ниже

Compares++; // увеличиваем счетчик сравнений перед предстоящим

// сравнением для условия выхода из цикла (i< size)

for (i=0; i< size; i++) {

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием (a++)

a++;

Changes++; // увеличиваем счетчик присваиваний перед предстоящим

// присваиванием счетчика цикла (i++)

Compares++; // увеличиваем счетчик сравнений перед предстоящим

// сравнением для условия выхода из цикла (i< size)

}

Eff=Compares+Changes*10; // считаем эффективность по формуле

Таким образом, после выполнения данного фрагмента, в программе будут доступны данные об эффективности выполнения этого фрагмента. Аналогичный подход был применен при создании алгоритмов сортировки в программе.