Основы теории ресурсной эффективности

Дисциплина «Алгоритмы и структуры данных» Лекция № 4 Основы теории ресурсной эффективности. Филатов Вячеслав Валерьевич к.т.н., доцент кафедры КБ-2 «Прикладные информационные технологии» Базовые принципы определения ресурсной и пространственной эффективностей алгоритмов и программ Особенности оценки и требования к алгоритмам в различных проблемных областях При разработке алгоритма необходимо учитывать не только временную эффективность алгоритма, определяемой его функцией трудоемкости и средой реализации, но и ряд дополнительных оценок, отражающих требования алгоритма и реализующей его программы к другим ресурсам компьютера. Таким образом, введём функцию ресурсной эффективности вычислительного алгоритма, учитывающую требования алгоритма к ресурсам компьютера. К таким ресурсам можно отнести • ресурсы оперативной памяти, необходимые для хранения исходных данных, промежуточных и окончательных результатов алгоритма и программы; • машинного кода программы; • ресурс стека. • напомним, что ресурс процессора, требуемый алгоритмом, отражается непосредственно временной оценкой или, опосредованно, функцией трудоемкости. Понятие ресурсной эффективности Определение. Под ресурсной характеристикой ℜ𝐴 алгоритма А и его программной реализации в худшем, лучшем или среднем будем понимать упорядоченную пару функций соответствующие рассматриваемому случаю функции трудоемкости 𝐹𝐴 𝑁 и функции объема памяти 𝑉𝐴 ℜ𝐴∗ = 𝐹𝐴∗ 𝑁 , 𝑉𝐴∗ (𝑁) , где * = ∧ , ∨ , − . Отличительной особенностью функции объема памяти 𝑉𝐴 от функции трудоемкости 𝐹𝐴 𝑁 является тот факт, что вид этой функции может существенно отличаться в зависимости от того алгоритм это или его программной реализации (например, с учетом компилятора), тогда как оценка 𝐹𝐴 𝑁 - только константой. Понятие емкостной сложности Состояние памяти модели вычислений (для реального компьютера это оперативная память), определяется значениями, записанными в ячейках этой памяти. Тогда механизм реализации модели вычислений, выполняя операции, заданные алгоритмом (или программой) переводит исходное состояние модели вычисления (исходные данные задачи – вход алгоритма) в конечное состояние – найденное алгоритмом решение задачи. В ходе решения задачи может быть задействовано некоторое дополнительное количество ячеек памяти. Понятие емкостной сложности Определение. Под объемом памяти VA(D), требуемым алгоритмом А для входа D, будем понимать максимальное количество ячеек памяти модели вычислений, задействованных в ходе выполнения алгоритма, т.е. положительное целочисленное значение. D представляет собой конкретную проблему (вход алгоритма А) размерности N. По аналогии с трудоемкостью, введем понятия 𝑉 𝐴∧ 𝑁 − худший случай функции объема памяти на входной строке N (длине входной последовательности); 𝑉 𝐴∨ 𝑁 − лучший случай функции объема памяти; 𝑉𝐴 𝑁 − средний случай функции объема памяти. Понятие емкостной сложности Определение. Емкостная сложность алгоритма (или программы) есть асимптотическая оценка в классах функций, определяемых обозначениями О и Θ для худшего случая: – 𝑉 𝐴∧ 𝑁 = 𝑂 𝑓 𝑁 – 𝑉 𝐴∧ 𝑁 = Θ(𝑓 𝑁 ) где f(N) – функция, задающая класс О или Θ для 𝑉 𝐴∧ 𝑁 . Виды ресурсов оперативной памяти Можно выделить следующие ресурсы оперативной памяти, которые могут влиять на выбор алгоритма: – 𝑉 𝑖𝑛𝑝 𝐷𝐴 −объем памяти по входу будем различать • алгоритмы «непотоковые по входу» или алгоритмы со статическим (предопределённым) входом, хранящие входные данные в памяти целиком, в этом случае 𝑉 𝑖𝑛𝑝 𝐷𝐴 =𝑉 𝑖𝑛𝑝 𝑁 ; • алгоритмы «потоковые по входу», при котором объекты входа поступают и обрабатываются поэлементно. Однако, например, поэлементное чтение из файла в предопределённый массив характеризует непотоковый вход, при котором требуется фиксированное количество ячеек в качестве буферных, поэтому 𝑉 𝑖𝑛𝑝 𝐷𝐴 =Θ(1). – 𝑉 𝑜𝑢𝑡 𝐷𝐴 − объем памяти по выходу, аналогично • алгоритмы со «статическим выходом». Однако, если в качестве результата используется помять по входу, например, при сортировке, то 𝑉 𝑜𝑢𝑡 𝐷𝐴 =0 ; • алгоритмы «потоковые по выходу», при котором вывод (например, на устройство вывода), а памяти требуется не более, чем на 1 элемент, поэтому 𝑉 𝑜𝑢𝑡 𝐷𝐴 =Θ(1). – 𝑉 𝑡𝑒𝑚𝑝 𝐷𝐴 − объем дополнительной оперативной памяти, требуемый под временные ячейки, массивы и структуры; тогда 𝑉 𝐷𝐴 = 𝑉 𝑖𝑛𝑝 𝐷𝐴 +𝑉 𝑜𝑢𝑡 𝐷𝐴 +𝑉 𝑡𝑒𝑚𝑝 𝐷𝐴 . Виды ресурсов оперативной памяти Можно выделить следующие ресурсы оперативной памяти, которые используются в процессе выполнения программ: – 𝑉 𝑒𝑥𝑒 𝐷𝐴 − ресурс оперативной памяти в области кода, требуемый для размещения машинного кода, реализующий данный алгоритм. Этот объем соотносим с объемом EXE-файла; – 𝑉 𝑠𝑡 𝐷𝐴 − ресурс оперативной памяти в области стека, требуемый алгоритмом для организации вызова внутренних функций. Объем данного ресурса существенного зависит от того, в каком подходе – итерационном или рекурсивном – реализован данный алгоритм; – 𝑉 𝑟𝑎𝑚 𝐷𝐴 − ресурс дополнительной оперативной памяти в области данных, требуемый под временные ячейки, массивы и структуры. Ресурс памяти для входа и выхода алгоритма в этой оценке не учитывается, т.к. является неизменным для всех алгоритмов решения данной задачи; тогда 𝑉 𝐷𝐴 = 𝑉 𝑒𝑥𝑒 𝐷𝐴 +𝑉 𝑠𝑡 𝐷𝐴 +𝑉 𝑟𝑎𝑚 𝐷𝐴 . Практическое использование функции роста ? Практическое использование функции роста Практическое использование функции роста Практическое использование функции роста Пример сравнения программ Пример сравнения программ Пример сравнения программ Пример сравнения программ Основные классы трудоемкости алгоритмов Примеры значений функций Примеры значений функций Спасибо за внимание!