Меры сложности алгоритмов
Размером задачи называется некоторая мера количества входных данных задачи. Например, число строк/столбцов матрицы; количество ребер графа и т.д.
Для оценки сложности алгоритмов существует много критериев. Чаще всего сложность алгоритма – количество необходимых для решения задачи ресурсов как функция от ее размера.
Рассматриваются различные меры сложности в зависимости от вида ресурса. Рассмотрим некоторые из них:
1. Временная сложность алгоритма – «время» выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма, которые необходимо выполнить для достижения результата)
2. Емкостная сложность алгоритма – необходимый для работы алгоритма объём памяти машины.
3. Схемная сложность алгоритма – минимальный размер схемы из функциональных элементов, вычисляющей заданную (булеву) функцию .
4. Коммуникационная сложность алгоритма – минимальное число бит, которыми нужно обменяться участникам вычисления некоторой функции . Замечания:
а) применяя специальные методы кодирования алгоритма, его можно представить как вычисление некоторой функции с аргументами из множества и с аргументами .
б) понятие схемы функциональных элементов – см. курс математической логики и теории алгоритмов.
в) размером схемы называется количество присваиваний в схеме.
г) коммуникационная сложность играет роль в случаях, когда задача решается объединенными усилиями нескольких участников, соединенных локальной сетью. Возникают ограничения по пропускной способности сети и стоимости трафика.
В дальнейшем будем подробно рассматривать вычисление временной сложности алгоритмов. Этот критерий является важным, но не единственным при оценке эффективности алгоритмов. Например, в силу следующих соображений
1. Эффективный по времени алгоритм может быть неэффективным по объему памяти.
2. Эффективные по времени, но сложные алгоритмы нежелательны, если готовые программы будут поддерживать лица, не участвовавшие в их написании.
3. В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.
4. Если программа будет использована только несколько раз, стоимость её написания превосходит стоимость времени ее выполнения. Финансово более выгоден алгоритм простой в реализации.
Массовой задачей называется совокупность задач единой структуры.
Пусть дана некоторая массовая задача и алгоритм для ее решения. Для любой частной задачи обозначим – размер задачи , т.е. количество входных данных задачи .
Через обозначим время работы алгоритма над задачей , измеренное в «шагах» т.е. инструкциях алгоритма.
Единица измерения величины — количество операторов, выполняемых алгоритмом на некотором идеализированном устройстве. Выбор модели такого устройства не имеет принципиального значения для анализа и сравнения временной сложности алгоритмов. Для удобства будем далее рассматривать выполнение алгоритма, записанного на языке Pascal.
Время работы алгоритма над задачей зависит не только от количества входных данных, но и от их характера. Т.е. возможно , но .
Поэтому целесообразно рассмотреть
– временная сложность алгоритма в худшем случае, т.е. максимальное время работы алгоритма над задачей размера .
Пример: Массовая задача – упорядочение одномерного массива по возрастанию.
:упорядочение массива (5,4,3,2,1)
:упорядочение массива (4,5,3,1,2)
:упорядочение массива (1,2,3,4,5)
. Для большинства алгоритмов сортировки и . Таким образом, эта формула определяет временную сложность алгоритма в худшем случае.
Замечание: Наиболее объективной мерой сложности алгоритма является – временная сложность в среднем, где берется среднее значение величины по всем . вычисляется сложнее, т.к. требует дополнительных сведений о характере данных задачи.
Асимптотической временной сложностью алгоритма в худшем случае (в среднем) называется характеристика поведения величин при
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Алгоритмы и структуры данных
1.4. Время выполнения программ
В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям.
1. Быть простым для понимания, перевода в программный код и отладки.
2. Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.
Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значительно превышает стоимость машинного времени выполнении программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если мы имеем дело с задачей, решение которой требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа должна выполняться многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Таким образом, программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать, когда их следует применить (желательно с минимальными программистскими усилиями).
Измерение времени выполнения программ
На время выполнения программы влияют следующие факторы.
1. Ввод исходной информации в программу.
2. Качество скомпилированного кода исполняемой программы.
3. Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.
4. Временная сложность алгоритма соответствующей программы.
Поскольку время выполнения программы зависит от ввода исходных данных; его можно определить как функцию от исходных данных. Но зачастую время выполнения программы зависит не от самих исходных данных, а от их «размера». В этом отношении хорошим примером являются задачи сортировки, которые мы подробно рассмотрим в главе 8. В задачах сортировки в качестве входных данных выступает список элементов, подлежащих сортировке, а в качестве выходного результата — те же самые элементы, отсортированные в порядке возрастания или убывания. Например, входной список 2, 1, 3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2, 3, 5, 8 (в данном случае список отсортирован в порядке возрастания). Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка. В общем случае длина входных данных— подходящая мера объема входной информации, и если не будет оговорено иное, то в качестве меры объема входной информации мы далее будем понимать именно длину входных данных.
Обычно говорят, что время выполнения программы имеет порядок Т(n) от входных данных размера n. Например, некая программа имеет время выполнения Т(n) = сn 2 , где с — константа. Единица измерения Т(n) точно не определена, но мы будем понимать Т(n) как количество инструкций, выполняемых на идеализированном компьютере.
Для многих программ время выполнения действительно является функцией входных данных, а не их размера. В этой ситуации мы определяем Т(n) как время выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Мы также будем рассматривать Тср(n) как среднее (в статистическом смысле) время выполнения по всем входным данным размера n. Хотя Тср(n) является достаточно объективной мерой времени выполнения, но часто нельзя предполагать (или обосновать) равнозначность всех входных данных. На практике среднее время выполнения найти сложнее, чем наихудшее время выполнения, так как математически это трудноразрешимая задача и, кроме того, зачастую не имеет простого определения понятие «средних» входных данных. Поэтому в основном мы будем использовать наихудшее время выполнения как меру временной сложности алгоритмов, но не будем забывать и о среднем времени выполнения там, где это возможно.
Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, и машине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения Т(n) мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные «время выполнения такого-то алгоритма пропорционально n 2 «. Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и других факторов.
Для описания скорости роста функций используется О-символика. Например, когда мы говорим, что время выполнения Т(n) некоторой программы имеет порядок О(n 2 ) (читается «о-большое от n в квадрате» или просто «о от n в квадрате»), то подразумевается, что существуют положительные константы с и n0 такие, что для всех n, больших или равных n0, выполняется неравенство Т(n) ≤ сn 2 .
Пример 1.4. Предположим, что Т(0) = 1, Т(1) = 4 и в общем случае Т(n) = (n + 1) 2 . Тогда Т(n) имеет порядок О(n 2 ): если положить n0 = 1 и с = 4, то легко показать, что для n ≥ 1 будет выполняться неравенство (n + 1) 2 ≤ 4n 2 . Отметим, что нельзя положить n0 = О, так как T(0) = 1 и, следовательно, это значение при любой константе с больше с0 2 = 0.
Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что Т(n) имеет порядок О(f(n)), если существуют константы с и n0 такие, что для всех n ≥ n0 выполняется неравенство Т(n) ≤ cf(n). Для программ, у которых время выполнения имеет порядок О(f(n)), говорят, что они имеют порядок (или степень) роста f(n).
Пример 1.5. Функция Т(n) = Зn 3 + 2n 2 имеет степень роста О(n 3 ). Чтобы это показать, надо положить n0 = 0 и с = 5, так как легко видеть, что для всех целых n ≥ 0 выполняется неравенство Зn 3 + 2n 2 ≤ 5n 3 . Можно, конечно, сказать, что Т(n) имеет порядок О(n 4 ), но это более слабое утверждение, чем то, что Т(n) имеет порядок роста О(n 3 ).В качестве следующего примера докажем, что функция 3 n не может иметь порядок О(2 n ). Предположим, что существуют константы с и п0 такие, что для всех п > nо выполняется неравенство 3 n ≤ c2 n . Тогда с ≥ (3/2) n для всех n ≥ n0. Но (3/2) n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы с, которая могла бы мажорировать (3/2) n для всех п.
Когда мы говорим, что Т(п) имеет степень роста О(f(n)), то подразумевается, что f(n) является верхней границей скорости роста Т(п). Чтобы указать нижнюю границу скорости роста Т(п), используется обозначение: Т(п) есть Ω(g(n)) (читается «омега-большое от g(n)» или просто «омега от g(n)«), это подразумевает существование такой константы с, что бесконечно часто (для бесконечного числа значений n) выполняется неравенство Т(п) > cg(n). (Отметим асимметрию в определениях О- и Ω-символики. Такая асимметрия бывает полезной, когда алгоритм работает быстро на достаточно большом подмножестве, но не на всем множестве входных данных. Например, есть алгоритмы, которые работают значительно быстрее, если длина входных данных является простым числом, а не (к примеру) четным числом. В этом случае невозможно получить хорошую нижнюю границу времени выполнения, справедливую для всех п ≥ nо.)
Пример 1.6. Для проверки того, что Т(п) = n 3 + 2п 2 есть Ω(n 3 ), достаточно положить с = 1. Тогда Т(п) ≥ сп 3 для п = О, 1. .
Для другого примера положим, что Т(п) = п для нечетных п ≥ 1 и Т(п) = n 2 /100 — для четных n ≥ О. Для доказательства того, что Т(п) есть Ω(n 2 ), достаточно положить с = 1/100 и рассмотреть множество четных чисел n = 0, 2, 4, 6. .
Ограниченность показателя степени роста
Итак, мы предполагаем, что программы можно оценить с помощью функций времени выполнения, пренебрегая при этом константами пропорциональности. С этой точки зрения программа с временем выполнения О(n 2 ), например, лучше программы с временем выполнения О(п). Константы пропорциональности зависят не только от используемых компилятора и компьютера, но и от свойств самой программы. Пусть при определенной комбинации компилятор-компьютер одна программа выполняется за 100n 2 миллисекунд, а вторая — за 5n 3 миллисекунд. Может ли вторая программа быть предпочтительнее, чем первая?
Ответ на этот вопрос зависит от размера входных данных программ. При размере входных данных п 3 завершится быстрее, чем программа с временем выполнения 100n 2 . Поэтому, если программы в основном выполняются с входными данными небольшого размера, предпочтение необходимо отдать программе с временем выполнения О(n 3 ). Однако при возрастании n отношение времени выполнения 5n 3 /100n 2 = n/20 также растет. Поэтому при больших n программа с временем выполнения О(n 2 ) становится предпочтительнее программы с временем выполнения О(n 3 ). Если даже при сравнительно небольших n, когда время выполнения обеих программ примерно одинаково, выбор лучшей программы представляет определенные затруднения, то естественно для большей надежности сделать выбор в пользу программы с меньшей степенью роста.
Другая причина, заставляющая отдавать предпочтение программам с наименьшей степенью роста времени выполнения, заключается в том, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Другими словами, если увеличивается скорость вычислений компьютера, то растет также и размер задач, решаемых на компьютере. Однако незначительное увеличение скорости вычислений компьютера приводит только к небольшому увеличению размера задач, решаемых в течение фиксированного промежутка времени, исключением из этого правила являются программы с низкой степенью роста, как О(n) и О(п logn).
Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные в секундах) для четырех программ с различной временной сложностью для одного и того же сочетания компилятор-компьютер. Предположим, что можно использовать 1 000 секунд (примерно 17 минут) машинного времени для решения задачи. Какой максимальный размер задачи, решаемой за это время? За 10 3 секунд каждый из четырех алгоритмов может решить задачи примерно одинакового размера, как показано во втором столбце табл. 1.3.
Предположим, что получен новый компьютер (без дополнительных финансовых затрат), работающий в десять раз быстрее. Теперь за ту же цену можно использовать 10 4 секунд машинного времени — ранее 10 3 секунд. Максимальный размер задачи, которую может решить за это время каждая из четырех программ, показан в третьем столбце табл. 1.3. Отношения значений третьего и второго столбцов приведены в четвертом столбце этой таблицы. Здесь мы видим, что увеличение скорости компьютера на 1 000% приводит к увеличению только на 30% размера задачи, решаемой с помощью программы с временем выполнения О(2 n ). Таким образом, 10-кратное увеличение производительности компьютера дает в процентном отношении значительно меньший эффект увеличения размера решаемой задачи. В действительности, независимо от быстродействия компьютера, программа с временем выполнения О(2 n ) может решать только очень небольшие задачи.
Источник
Единицы измерения времени выполнения алгоритма
Для этой цели можно просто воспользоваться общепринятыми единицами измерения времени — секундой, миллисекундой и т.д. и с их помощью оценить время выполнения программы, реализующей рассматриваемый алгоритм. Однако у такого подхода существуют явные недостатки, поскольку результаты измерений будут зависеть от:
¦ быстродействия конкретного компьютера;
¦ тщательности реализации алгоритма в виде программы;
¦ типа компилятора, использованного для генерации машинного кода;
¦ точности хронометрирования реального времени выполнения программы.
Поскольку перед нами стоит задача измерения эффективности алгоритма, а не реализующей его программы, мы должны воспользоваться такой системой измерений, которая бы не зависела от приведенных выше посторонних факторов.
Таким образом, для анализа временной эффективности алгоритмов этот показатель будет оцениваться по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n.
Рассмотрим один важный пример. Предположим, что сор — время выполнения основной операции алгоритма на конкретном компьютере, а С (n) — количество раз, которые эта операция должна быть выполнена при работе алгоритма. Тогда время выполнения программной реализации этого алгоритма на данном компьютере T(n) можно приблизительно определить по следующей формуле: 
Разумеется, эту формулу нужно использовать очень аккуратно. В значении счетчика С(n) не учитывается количество выполняемых алгоритмом операций, не относящихся к основным. Кроме того, обычно значение этого счетчика можно определить только приблизительно. Более того, значение константы Сор также можно определить лишь приблизительно и оценить ее точность весьма непросто. Тем не менее, эта формула дает приемлемую оценку времени выполнения алгоритма для небесконечно больших и небесконечно малых значений n. Она также позволяет ответить на вопросы: во сколько раз быстрее будет работать реализация данного алгоритма на компьютере, быстродействие которого больше нашего в 10 раз?
В самом деле, для достаточно больших n справедлива следующая формула:
Этому в процессе анализа эффективности при достаточно больших размерах входных данных не учитывают постоянные множители, а сосредотачиваются на оценке порядка роста (order of growth) количества основных операций с точностью до постоянного множителя.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Вечный вопрос измерения времени
Казалось, закончились долгие обсуждения в форумах, как измерить время работы алгоритма, какие функции использовать, какую точность ожидать. Жаль, но опять придется вернуться к этому вопросу. На повестке дня, как лучше измерить скорость работы параллельного алгоритма.
Сразу скажу, что не дам точного рецепта. Я сам недавно столкнулся с проблемой измерения скорости работы параллельных алгоритмов и не являюсь экспертом в этом вопросе. Эта заметка носит скорее исследовательский характер. Я буду рад услышать ваше мнение и рекомендации. Думаю, вместе мы разберемся с проблемой и выработаем оптимальное решение.
Задача состоит в измерении времени работы участка пользовательского кода. Раньше для этой задачи я использовал класс следующего вида:
Данный класс основан на использовании функции GetThreadTimes, которая позволяет разделить время, затраченное на работу пользовательского кода, и время работы системных функций. Класс предназначен для оценки времени работы потока в пользовательском режиме, и поэтому используется только возвращаемый параметр lpUserTime.
Измерять время работы можно используя такие инструментальные средства, как Intel Parallel Amplifier, но часто удобно измерять время изнутри программы. Например, это позволяет записать значения в лог. Поэтому мы все-таки попробуем создать класс для замера скорости.
Рассмотрим пример кода, вычисляющий некоторое число. Используем для измерения времени работы класс Timing.
В таком виде механизм измерения времени ведет себя как ожидалось и на моей рабочей машине выдает, скажем, 7 секунд. Результат корректен даже для многоядерной машины, так как неважно какие ядра будут использованы в процессе работы алгоритма (см. рисунок 1). 
Рисунок 1 — Работа одного потока на многоядерной машине.
Теперь представим, что мы хотим использовать в нашей программе возможности многоядерных процессоров и хотим оценить, что нам дает распараллеливание алгоритма на основе технологии OpenMP. Распараллелим наш код, добавив одну строчку:
Теперь программа печатает на экран время работы 1.6 секунд. Поскольку используется машина с 4 ядрами, хочется сказать «Ура, мы получили ускорение в 4 раза и замер времени работы это подтверждает».
Огорчу. Мы измеряем не время работы алгоритма, а время работы главного потока. В данном случае измерение кажется достоверным, поскольку основной поток работал столько же, сколько и дополнительные. Поставим простой эксперимент. Явно укажем использовать 10 потоков, а не 4:
Логика подсказывает, что данный код должен работать приблизительно тоже время, что и код, распараллеливаемый на 4 потока. У нас четырех ядерный процессор, а следовательно от увеличения количества потоков можно ожидать только замедление. Однако на экране мы увидим значение порядка 0.7 секунд.
Это ожидаемый результат, хотя мы хотели получить совсем иное. Было создано 10 потоков. Каждый из которых отработал порядка 0.7 секунд. Именно это время работал и основной поток, время которого мы замеряем, используя класс Timing. Как видите, такой способ неприменим для измерения скорости программ с параллельными участками кода. Для наглядности отобразим это на рисунке 2. 
Рисунок 2 — Так может выглядеть работа 10 потоков, на машине с четырьмя ядрами.
Конечно, всегда можно использовать функцию time(), но ее разрешающая способность низкая, она не позволяет разделить время работы пользовательского и системного кода. Дополнительно на время могут влиять другие процессы, что также может сильно искажать измерения времени.
Любимой функцией многих разработчиков для измерения скорости является QueryPerformanceCounter. Давайте построим измерение скорости с ее использованием. В простом виде класс для измерения будет выглядеть следующим образом:
К сожалению, на многоядерной машине, так делать больше нельзя. 🙂 Вот что сказано по поводу этой функции в MSDN:
On a multiprocessor computer, it should not matter which processor is called. However, you can get different results on different processors due to bugs in the basic input/output system (BIOS) or the hardware abstraction layer (HAL). To specify processor affinity for a thread, use the SetThreadAffinityMask function.
Произведем усовершенствования и привяжем главный поток к одному ядру:
Данный способ измерения по-прежнему подвержен тому же недостатку, что невозможно отделить время работы системного и пользовательского кода. Если на ядре выполняются другие задачи, то результат измерения также будет весьма неточен. Однако как мне кажется, такой способ все же применим к параллельному алгоритму в отличии GetThreadTimes. Если это не так, то прошу меня поправить!
Измерим, что покажут классы Timing и Timing2 на различном количестве потоков:
Сведем данные в таблицу, показанную на третьем рисунке. 
Рисунок 3 — Время работы алгоритма в секундах измеренное с помощью функций GetThreadTimes и QueryPerformanceCounter на четырехядерной машине.
Как видно из таблицы, пока количество потоков не превышает количества ядер, функция GetThreadTimes дает результат схожий с QueryPerformanceCounter, что может приводить к ощущению, что производятся корректные измерения. Однако при большем количестве потоков на ее результат полагаться уже нельзя.
Жду ваших комментариев и описаний способов, как лучше измерять время работы параллельных алгоритмов.
Источник
Измерение времени выполнения программы
На время выполнения программы влияют следующие факторы:
Ввод исходной информации в программу.
Качество скомпилированного кода исполняемой программы.
Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.
Временнáя сложность алгоритма соответствующей программы.
Поскольку время выполнения программы зависит от ввода исходных данных, его можно определить как функцию от исходных данных. Но зачастую время выполнения программы зависит не от самих исходных данных, а от их «размера». Здесь хорошим примером являются задачи сортировки. В них в качестве исходных данных выступает список элементов, подлежащих сортировке, а в качестве выходного результата – те же самые элементы, отсортированные в порядке возрастания или убывания. Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка. В общем случае длина входных данных – подходящая мера объема входной информации. Иногда под размером понимается общее число битов, необходимых для представления всех входных данных. Иногда размер входа определяется не одним числом, а несколькими, например, числом вершин и числом ребер графа.
Обычно говорят, что время выполнения программы имеет порядок T(n) от входных данных размера n. Единица измерения T(n) не определена и, если не оговорено иначе, мы будем понимать T(n) как количество инструкций, выполняемых на идеализированном компьютере.
Если на время выполнения программы также влияет «качество» информации, мы будем определять T(n) как время выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Почему? Вот несколько причин.
Зная время работы в худшем случае, мы можем гарантировать, что выполнение алгоритма закончится за некоторое время, даже не зная какие данные попадутся на вход.
На практике «плохие» входные данные (для которых время выполнения алгоритма близко к максимальному) могут часто попадаться. Например, для базы данных плохим запросом может быть поиск отсутствующего элемента (довольно частая ситуация).
Также существует понятие: среднее время выполнения по всем входным данным размера n, в статистическом смысле. На практике среднее время выполнения найти сложнее, чем наихудшее время выполнения, так как математически это трудноразрешимая задача и, кроме того, зачастую трудно определить какие входные данные являются «средними». Поэтому среднее время выполнения программы определяется для тех алгоритмов, где это возможно.
Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, и машине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные следующему: «время выполнения такого-то алгоритма пропорционально n 2 ». Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и др. факторов.
Источник
Алгоритмы и структуры данных
1.4. Время выполнения программ
В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям.
1. Быть простым для понимания, перевода в программный код и отладки.
2. Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.
Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значительно превышает стоимость машинного времени выполнении программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если мы имеем дело с задачей, решение которой требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа должна выполняться многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Таким образом, программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать, когда их следует применить (желательно с минимальными программистскими усилиями).
Измерение времени выполнения программ
На время выполнения программы влияют следующие факторы.
1. Ввод исходной информации в программу.
2. Качество скомпилированного кода исполняемой программы.
3. Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.
4. Временная сложность алгоритма соответствующей программы.
Поскольку время выполнения программы зависит от ввода исходных данных; его можно определить как функцию от исходных данных. Но зачастую время выполнения программы зависит не от самих исходных данных, а от их «размера». В этом отношении хорошим примером являются задачи сортировки, которые мы подробно рассмотрим в главе 8. В задачах сортировки в качестве входных данных выступает список элементов, подлежащих сортировке, а в качестве выходного результата — те же самые элементы, отсортированные в порядке возрастания или убывания. Например, входной список 2, 1, 3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2, 3, 5, 8 (в данном случае список отсортирован в порядке возрастания). Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка. В общем случае длина входных данных— подходящая мера объема входной информации, и если не будет оговорено иное, то в качестве меры объема входной информации мы далее будем понимать именно длину входных данных.
Обычно говорят, что время выполнения программы имеет порядок Т(n) от входных данных размера n. Например, некая программа имеет время выполнения Т(n) = сn 2 , где с — константа. Единица измерения Т(n) точно не определена, но мы будем понимать Т(n) как количество инструкций, выполняемых на идеализированном компьютере.
Для многих программ время выполнения действительно является функцией входных данных, а не их размера. В этой ситуации мы определяем Т(n) как время выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Мы также будем рассматривать Тср(n) как среднее (в статистическом смысле) время выполнения по всем входным данным размера n. Хотя Тср(n) является достаточно объективной мерой времени выполнения, но часто нельзя предполагать (или обосновать) равнозначность всех входных данных. На практике среднее время выполнения найти сложнее, чем наихудшее время выполнения, так как математически это трудноразрешимая задача и, кроме того, зачастую не имеет простого определения понятие «средних» входных данных. Поэтому в основном мы будем использовать наихудшее время выполнения как меру временной сложности алгоритмов, но не будем забывать и о среднем времени выполнения там, где это возможно.
Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, и машине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения Т(n) мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные «время выполнения такого-то алгоритма пропорционально n 2 «. Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и других факторов.
Для описания скорости роста функций используется О-символика. Например, когда мы говорим, что время выполнения Т(n) некоторой программы имеет порядок О(n 2 ) (читается «о-большое от n в квадрате» или просто «о от n в квадрате»), то подразумевается, что существуют положительные константы с и n0 такие, что для всех n, больших или равных n0, выполняется неравенство Т(n) ≤ сn 2 .
Пример 1.4. Предположим, что Т(0) = 1, Т(1) = 4 и в общем случае Т(n) = (n + 1) 2 . Тогда Т(n) имеет порядок О(n 2 ): если положить n0 = 1 и с = 4, то легко показать, что для n ≥ 1 будет выполняться неравенство (n + 1) 2 ≤ 4n 2 . Отметим, что нельзя положить n0 = О, так как T(0) = 1 и, следовательно, это значение при любой константе с больше с0 2 = 0.
Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что Т(n) имеет порядок О(f(n)), если существуют константы с и n0 такие, что для всех n ≥ n0 выполняется неравенство Т(n) ≤ cf(n). Для программ, у которых время выполнения имеет порядок О(f(n)), говорят, что они имеют порядок (или степень) роста f(n).
Пример 1.5. Функция Т(n) = Зn 3 + 2n 2 имеет степень роста О(n 3 ). Чтобы это показать, надо положить n0 = 0 и с = 5, так как легко видеть, что для всех целых n ≥ 0 выполняется неравенство Зn 3 + 2n 2 ≤ 5n 3 . Можно, конечно, сказать, что Т(n) имеет порядок О(n 4 ), но это более слабое утверждение, чем то, что Т(n) имеет порядок роста О(n 3 ).В качестве следующего примера докажем, что функция 3 n не может иметь порядок О(2 n ). Предположим, что существуют константы с и п0 такие, что для всех п > nо выполняется неравенство 3 n ≤ c2 n . Тогда с ≥ (3/2) n для всех n ≥ n0. Но (3/2) n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы с, которая могла бы мажорировать (3/2) n для всех п.
Когда мы говорим, что Т(п) имеет степень роста О(f(n)), то подразумевается, что f(n) является верхней границей скорости роста Т(п). Чтобы указать нижнюю границу скорости роста Т(п), используется обозначение: Т(п) есть Ω(g(n)) (читается «омега-большое от g(n)» или просто «омега от g(n)«), это подразумевает существование такой константы с, что бесконечно часто (для бесконечного числа значений n) выполняется неравенство Т(п) > cg(n). (Отметим асимметрию в определениях О- и Ω-символики. Такая асимметрия бывает полезной, когда алгоритм работает быстро на достаточно большом подмножестве, но не на всем множестве входных данных. Например, есть алгоритмы, которые работают значительно быстрее, если длина входных данных является простым числом, а не (к примеру) четным числом. В этом случае невозможно получить хорошую нижнюю границу времени выполнения, справедливую для всех п ≥ nо.)
Пример 1.6. Для проверки того, что Т(п) = n 3 + 2п 2 есть Ω(n 3 ), достаточно положить с = 1. Тогда Т(п) ≥ сп 3 для п = О, 1. .
Для другого примера положим, что Т(п) = п для нечетных п ≥ 1 и Т(п) = n 2 /100 — для четных n ≥ О. Для доказательства того, что Т(п) есть Ω(n 2 ), достаточно положить с = 1/100 и рассмотреть множество четных чисел n = 0, 2, 4, 6. .
Ограниченность показателя степени роста
Итак, мы предполагаем, что программы можно оценить с помощью функций времени выполнения, пренебрегая при этом константами пропорциональности. С этой точки зрения программа с временем выполнения О(n 2 ), например, лучше программы с временем выполнения О(п). Константы пропорциональности зависят не только от используемых компилятора и компьютера, но и от свойств самой программы. Пусть при определенной комбинации компилятор-компьютер одна программа выполняется за 100n 2 миллисекунд, а вторая — за 5n 3 миллисекунд. Может ли вторая программа быть предпочтительнее, чем первая?
Ответ на этот вопрос зависит от размера входных данных программ. При размере входных данных п 3 завершится быстрее, чем программа с временем выполнения 100n 2 . Поэтому, если программы в основном выполняются с входными данными небольшого размера, предпочтение необходимо отдать программе с временем выполнения О(n 3 ). Однако при возрастании n отношение времени выполнения 5n 3 /100n 2 = n/20 также растет. Поэтому при больших n программа с временем выполнения О(n 2 ) становится предпочтительнее программы с временем выполнения О(n 3 ). Если даже при сравнительно небольших n, когда время выполнения обеих программ примерно одинаково, выбор лучшей программы представляет определенные затруднения, то естественно для большей надежности сделать выбор в пользу программы с меньшей степенью роста.
Другая причина, заставляющая отдавать предпочтение программам с наименьшей степенью роста времени выполнения, заключается в том, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Другими словами, если увеличивается скорость вычислений компьютера, то растет также и размер задач, решаемых на компьютере. Однако незначительное увеличение скорости вычислений компьютера приводит только к небольшому увеличению размера задач, решаемых в течение фиксированного промежутка времени, исключением из этого правила являются программы с низкой степенью роста, как О(n) и О(п logn).
Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные в секундах) для четырех программ с различной временной сложностью для одного и того же сочетания компилятор-компьютер. Предположим, что можно использовать 1 000 секунд (примерно 17 минут) машинного времени для решения задачи. Какой максимальный размер задачи, решаемой за это время? За 10 3 секунд каждый из четырех алгоритмов может решить задачи примерно одинакового размера, как показано во втором столбце табл. 1.3.
Предположим, что получен новый компьютер (без дополнительных финансовых затрат), работающий в десять раз быстрее. Теперь за ту же цену можно использовать 10 4 секунд машинного времени — ранее 10 3 секунд. Максимальный размер задачи, которую может решить за это время каждая из четырех программ, показан в третьем столбце табл. 1.3. Отношения значений третьего и второго столбцов приведены в четвертом столбце этой таблицы. Здесь мы видим, что увеличение скорости компьютера на 1 000% приводит к увеличению только на 30% размера задачи, решаемой с помощью программы с временем выполнения О(2 n ). Таким образом, 10-кратное увеличение производительности компьютера дает в процентном отношении значительно меньший эффект увеличения размера решаемой задачи. В действительности, независимо от быстродействия компьютера, программа с временем выполнения О(2 n ) может решать только очень небольшие задачи.
Источник
Единицы измерения времени выполнения алгоритма
Для этой цели можно просто воспользоваться общепринятыми единицами измерения времени — секундой, миллисекундой и т.д. и с их помощью оценить время выполнения программы, реализующей рассматриваемый алгоритм. Однако у такого подхода существуют явные недостатки, поскольку результаты измерений будут зависеть от:
¦ быстродействия конкретного компьютера;
¦ тщательности реализации алгоритма в виде программы;
¦ типа компилятора, использованного для генерации машинного кода;
¦ точности хронометрирования реального времени выполнения программы.
Поскольку перед нами стоит задача измерения эффективности алгоритма, а не реализующей его программы, мы должны воспользоваться такой системой измерений, которая бы не зависела от приведенных выше посторонних факторов.
Таким образом, для анализа временной эффективности алгоритмов этот показатель будет оцениваться по количеству основных операций, которые должен выполнить алгоритм при обработке входных данных размера n.
Рассмотрим один важный пример. Предположим, что сор — время выполнения основной операции алгоритма на конкретном компьютере, а С (n) — количество раз, которые эта операция должна быть выполнена при работе алгоритма. Тогда время выполнения программной реализации этого алгоритма на данном компьютере T(n) можно приблизительно определить по следующей формуле: Разумеется, эту формулу нужно использовать очень аккуратно. В значении счетчика С(n) не учитывается количество выполняемых алгоритмом операций, не относящихся к основным. Кроме того, обычно значение этого счетчика можно определить только приблизительно. Более того, значение константы Сор также можно определить лишь приблизительно и оценить ее точность весьма непросто. Тем не менее, эта формула дает приемлемую оценку времени выполнения алгоритма для небесконечно больших и небесконечно малых значений n. Она также позволяет ответить на вопросы: во сколько раз быстрее будет работать реализация данного алгоритма на компьютере, быстродействие которого больше нашего в 10 раз?
В самом деле, для достаточно больших n справедлива следующая формула:
Этому в процессе анализа эффективности при достаточно больших размерах входных данных не учитывают постоянные множители, а сосредотачиваются на оценке порядка роста (order of growth) количества основных операций с точностью до постоянного множителя.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Вечный вопрос измерения времени
Казалось, закончились долгие обсуждения в форумах, как измерить время работы алгоритма, какие функции использовать, какую точность ожидать. Жаль, но опять придется вернуться к этому вопросу. На повестке дня, как лучше измерить скорость работы параллельного алгоритма.
Сразу скажу, что не дам точного рецепта. Я сам недавно столкнулся с проблемой измерения скорости работы параллельных алгоритмов и не являюсь экспертом в этом вопросе. Эта заметка носит скорее исследовательский характер. Я буду рад услышать ваше мнение и рекомендации. Думаю, вместе мы разберемся с проблемой и выработаем оптимальное решение.
Задача состоит в измерении времени работы участка пользовательского кода. Раньше для этой задачи я использовал класс следующего вида:
Данный класс основан на использовании функции GetThreadTimes, которая позволяет разделить время, затраченное на работу пользовательского кода, и время работы системных функций. Класс предназначен для оценки времени работы потока в пользовательском режиме, и поэтому используется только возвращаемый параметр lpUserTime.
Измерять время работы можно используя такие инструментальные средства, как Intel Parallel Amplifier, но часто удобно измерять время изнутри программы. Например, это позволяет записать значения в лог. Поэтому мы все-таки попробуем создать класс для замера скорости.
Рассмотрим пример кода, вычисляющий некоторое число. Используем для измерения времени работы класс Timing.
В таком виде механизм измерения времени ведет себя как ожидалось и на моей рабочей машине выдает, скажем, 7 секунд. Результат корректен даже для многоядерной машины, так как неважно какие ядра будут использованы в процессе работы алгоритма (см. рисунок 1).
Рисунок 1 — Работа одного потока на многоядерной машине.
Теперь представим, что мы хотим использовать в нашей программе возможности многоядерных процессоров и хотим оценить, что нам дает распараллеливание алгоритма на основе технологии OpenMP. Распараллелим наш код, добавив одну строчку:
Теперь программа печатает на экран время работы 1.6 секунд. Поскольку используется машина с 4 ядрами, хочется сказать «Ура, мы получили ускорение в 4 раза и замер времени работы это подтверждает».
Огорчу. Мы измеряем не время работы алгоритма, а время работы главного потока. В данном случае измерение кажется достоверным, поскольку основной поток работал столько же, сколько и дополнительные. Поставим простой эксперимент. Явно укажем использовать 10 потоков, а не 4:
Логика подсказывает, что данный код должен работать приблизительно тоже время, что и код, распараллеливаемый на 4 потока. У нас четырех ядерный процессор, а следовательно от увеличения количества потоков можно ожидать только замедление. Однако на экране мы увидим значение порядка 0.7 секунд.
Это ожидаемый результат, хотя мы хотели получить совсем иное. Было создано 10 потоков. Каждый из которых отработал порядка 0.7 секунд. Именно это время работал и основной поток, время которого мы замеряем, используя класс Timing. Как видите, такой способ неприменим для измерения скорости программ с параллельными участками кода. Для наглядности отобразим это на рисунке 2.
Рисунок 2 — Так может выглядеть работа 10 потоков, на машине с четырьмя ядрами.
Конечно, всегда можно использовать функцию time(), но ее разрешающая способность низкая, она не позволяет разделить время работы пользовательского и системного кода. Дополнительно на время могут влиять другие процессы, что также может сильно искажать измерения времени.
Любимой функцией многих разработчиков для измерения скорости является QueryPerformanceCounter. Давайте построим измерение скорости с ее использованием. В простом виде класс для измерения будет выглядеть следующим образом:
К сожалению, на многоядерной машине, так делать больше нельзя. 🙂 Вот что сказано по поводу этой функции в MSDN:
On a multiprocessor computer, it should not matter which processor is called. However, you can get different results on different processors due to bugs in the basic input/output system (BIOS) or the hardware abstraction layer (HAL). To specify processor affinity for a thread, use the SetThreadAffinityMask function.
Произведем усовершенствования и привяжем главный поток к одному ядру:
Данный способ измерения по-прежнему подвержен тому же недостатку, что невозможно отделить время работы системного и пользовательского кода. Если на ядре выполняются другие задачи, то результат измерения также будет весьма неточен. Однако как мне кажется, такой способ все же применим к параллельному алгоритму в отличии GetThreadTimes. Если это не так, то прошу меня поправить!
Измерим, что покажут классы Timing и Timing2 на различном количестве потоков:
Сведем данные в таблицу, показанную на третьем рисунке.
Рисунок 3 — Время работы алгоритма в секундах измеренное с помощью функций GetThreadTimes и QueryPerformanceCounter на четырехядерной машине.
Как видно из таблицы, пока количество потоков не превышает количества ядер, функция GetThreadTimes дает результат схожий с QueryPerformanceCounter, что может приводить к ощущению, что производятся корректные измерения. Однако при большем количестве потоков на ее результат полагаться уже нельзя.
Жду ваших комментариев и описаний способов, как лучше измерять время работы параллельных алгоритмов.
Источник