Быстрый поиск

Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Dim I As Integer

Dim J As Integer

Dim K As Integer

For I = 1 To N

For J = 1 To N

For K = 1 To N

' Выполнить какие‑либо действия.

Next K

Next J

Next I

End Sub

Sub Fast()

Dim I As Integer

Dim J As Integer

For I = 1 To N

For J = 1 To N

' Выполнить какие‑либо действия.

Next J

Next I

End Sub

Sub MainProgram()

Slow

Fast

End Sub

==============5

Сложность рекурсивных алгоритмов

Рекурсивными процедурами (recursive procedure) называются процедуры, вызывающие сами себя. Во многих рекурсивных алгоритмах именно степень вложенности рекурсии определяет сложность алгоритма, при этом не всегда легко оценить порядок сложности. Рекурсивная процедура может выглядеть простой, но при этом вносить большой вклад в сложность программы, многократно вызывая саму себя.

Следующий фрагмент кода содержит подпрограмму всего из двух операторов. Тем не менее, для заданного N подпрограмма выполняется N раз, таким образом, вычислительная сложность фрагмента порядка O(N).

Sub CountDown(N As Integer)

If N <= 0 Then Exit Sub

CountDown N - 1

End Sub

===========6

Многократная рекурсия

Рекурсивный алгоритм, вызывающий себя несколько раз, является примером многократной рекурсии (multiple recursion). Процедуры с множественной рекурсией сложнее анализировать, чем просто рекурсивные алгоритмы, и они могут давать больший вклад в общую сложность алгоритма.

Нижеприведенная подпрограмма похожа на предыдущую подпрограмму CountDown, только она вызывает саму себя дважды:

Sub DoubleCountDown(N As Integer)

If N <= 0 Then Exit Sub

DoubleCountDown N - 1

End Sub

Можно было бы предположить, что время выполнения этой процедуры будет в два раза больше, чем для подпрограммы CountDown, и оценить ее сложность порядка 2*O(N)=O(N). На самом деле ситуация немного сложнее.

Если T(N) — число раз, которое выполняется процедура DoubleCountDown с параметром N, то легко заметить, что T(0)=1. Если вызвать процедуру с параметром N равным 0, то она просто закончит свою работу после первого шага.

Для больших значений N процедура вызывает себя дважды с параметром, равным N-1, выполняясь 1+2*T(N-1) раз. В табл. 1.1 приведены некоторые значения функции T(0)=1 и T(N)=1+2*T(N-1). Если обратить внимание на эти значения, можно увидеть, что T(N)=2(N+1)-1, что дает оценку сложности процедуры порядка O(2N). Хотя процедуры CountDown и DoubleCountDown и похожи, вторая процедура требует выполнения гораздо большего числа шагов.

@Таблица 1.1. Значения функции времени выполнения для подпрограммы DoubleCountDown

Косвенная рекурсия

Процедура также может вызывать другую процедуру, которая в свою очередь вызывает первую. Такие процедуры иногда даже сложнее анализировать, чем процедуры с множественной рекурсией. Алгоритм вычисления кривой Серпинского, который обсуждается в 5 главе, включает в себя четыре процедуры, которые используют как множественную, так и непрямую рекурсию. Каждая из этих процедур вызывает себя и другие три процедуры до четырех раз. После довольно сложных подсчетов можно показать, что этот алгоритм имеет сложность порядка O(4N).

Требования рекурсивных алгоритмов к объему памяти

Для некоторых рекурсивных алгоритмов важен объем доступной памяти. Можно легко написать рекурсивный алгоритм, который будет запрашивать

============7

небольшой объем памяти при каждом своем вызове. Объем занятой памяти может увеличиваться в процессе последовательных рекурсивных вызовов.

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

Приведенная ниже подпрограмма запрашивает память при каждом вызове. После 100 или 200 рекурсивных вызовов, процедура займет всю свободную память, и программа аварийно остановится с ошибкой «Out of Memory».

Sub GobbleMemory(N As Integer)

Dim Array() As Integer

ReDim Array (1 To 32000)

GobbleMemory N + 1

End Sub

Даже если внутри процедуры память не запрашивается, система выделяет память из системного стека (system stack) для сохранения параметров при каждом вызове процедуры. После возврата из процедуры память из стека освобождается для дальнейшего использования.

Если в подпрограмме встречается длинная последовательность рекурсивных вызовов, программа может исчерпать стек, даже если выделенная программе память еще не вся использована. Если запустить на исполнение следующую подпрограмму, она быстро исчерпает всю свободную стековую память и программа аварийно прекратит работу с сообщением об ошибке «Out of stack Space». После этого вы сможете узнать значение переменной Count, чтобы узнать, сколько раз подпрограмма вызывала себя перед тем, как исчерпать стек.

Sub UseStack()

Static Count As Integer

Count = Count + 1

UseStack

End Sub

Определение локальных переменных внутри подпрограммы также может занимать память из стека. Если изменить подпрограмму UseStack из предыдущего примера так, чтобы она определяла три переменных при каждом вызове, программа исчерпает стековое пространство еще быстрее:

Sub UseStack()

Static Count As Integer

Dim I As Variant

Dim J As Variant

Dim K As Variant

Count = Count + 1

UseStack

End Sub

В 5 главе рекурсивные алгоритмы обсуждаются более подробно.

==============8

Наихудший и усредненный случай

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

Function LocateItem(target As Integer) As Integer

For I = 1 To N

If Value(I) = target Then Exit For

Next I

LocateItem = I

End Sub

Если искомый элемент находится в конце списка, придется перебрать все N элементов для того, чтобы его найти. Это займет N шагов, значит сложность алгоритма порядка O(N). В этом, так называемом наихудшем случае (worst case) время выполнения алгоритма будет наибольшим.

С другой стороны, если искомое число в начале списка, алгоритм завершит работу практически сразу, совершив всего несколько итераций. Это так называемый наилучший случай (best case) со сложностью порядка O(1). Обычно и наилучший, и наихудший случаи встречаются относительно редко, и интерес представляет оценка усредненного или ожидаемого (expected case) поведения.

Если первоначально числа в списке распределены случайно, искомый элемент может оказаться в любом месте списка. В среднем потребуется проверить N/2 элементов для того, чтобы его найти. Значит, сложность этого алгоритма в усредненном случае порядка O(N/2), или O(N), если убрать постоянный множитель.

Для некоторых алгоритмов порядок сложности для наихудшего и наилучшего вариантов различается. Например, сложность алгоритма быстрой сортировки из 9 главы в наихудшем случае порядка O(N2), но в среднем его сложность порядка O(N*log(N)), что намного быстрее. Иногда алгоритмы типа быстрой сортировки бывают очень длинными, чтобы наихудший случай достигался крайне редко.

Часто встречающиеся функции оценки порядка сложности

В табл. 1.2 приведены некоторые функции, которые обычно встречаются при оценке сложности алгоритмов. Функции приведены в порядке возрастания вычислительной сложности сверху вниз. Это значит, что алгоритмы со сложностью порядка функций, расположенных вверху таблицы, будут выполняться быстрее, чем те, сложность которых определяется функциями из нижней части таблицы.

==============9

@Таблица 1.2. Часто встречающиеся функции оценки порядка сложности

Сложность алгоритма, определяемая уравнением, которое представляет собой сумму функций из таблицы, будет сводиться к сложности той из функций, которая расположена в таблице ниже. Например, O(log(N)+N2) — это то же самое, что и O(N2).

Обычно алгоритмы со сложностью порядка N*log(N) и менее сложных функций выполняются очень быстро. Алгоритмы порядка NC при малых C, например N2 выполняются достаточно быстро. Вычислительная же сложность алгоритмов, порядок которых определяется функциями CN или N! очень велика и эти алгоритмы пригодны только для решения задач с небольшим N.

В качестве примера в табл. 1.3 показано, как долго компьютер, выполняющий миллион инструкций в секунду, будет выполнять некоторые медленные алгоритмы. Из таблицы видно, что при сложности порядка O(CN) могут быть решены только небольшие задачи, и еще меньше параметр N может быть для задач со сложностью порядка O(N!). Для решения задачи порядка O(N!) при N=24 потребовалось бы время, большее, чем время существования вселенной.

Логарифмы

Перед тем, как продолжить дальше, следует остановиться на логарифмах, так как они играют важную роль в различных алгоритмах. Логарифм числа N по основанию B это степень P, в которую надо возвести основание, чтобы получить N, то есть BP=N. Например, если 23=8, то соответственно log2(8)=3.

==================10

@Таблица 1.3. Время выполнения сложных алгоритмов

Можно привести логарифм к другому основанию при помощи соотношения logB(N)=logC(N)/logC(B). Например, чтобы вычислить логарифм числа по основанию 10, зная его логарифм по основанию 2, можно воспользоваться формулой log10(N)=log2(N)/log2(10). При этом log2(10) — это табличная константа, примерно равная 3,32. Так как постоянные множители при оценке сложности алгоритма можно опустить, то O(log2(N)) — это же самое, что и O(log10(N)) или O(logB(N)) для любого B. Поскольку основание логарифма не имеет значения, часто просто пишут, что сложность алгоритма порядка O(log(N)).

В программировании часто встречаются логарифмы по основанию 2, что обусловлено применяемой в компьютерах двоичной системой исчисления. Поэтому мы для упрощения выражений будем везде писать log(N), подразумевая под этим log2(N). Если используется другое основание алгоритма, это будет обозначено особо.

Реальные условия — насколько быстро?

Хотя при исследовании сложности алгоритма обычно полезно отбросить малые члены уравнения и постоянные множители, иногда их все‑таки необходимо учитывать, особенно если размерность данных задачи N мала, а постоянные множители достаточно велики.

Допустим, мы рассматриваем два алгоритма решения одной задачи. Один выполняется за время порядка O(N), а другой — порядка O(N2). Для больших N первый алгоритм, вероятно, будет работать быстрее.

Тем не менее, если взять конкретные функции оценки времени выполнения для каждого из двух алгоритмов, например, для первого f(N)=30*N+7000, а для второго f(N)=N2, то в этом случае при N меньше 100 второй алгоритм будет выполняться быстрее. Поэтому, если известно, что размерность данных задачи не будет превышать 100, возможно будет целесообразнее применить второй алгоритм.

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

==================11

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

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

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

Обращение к файлу подкачки

Важным фактором при работе в реальных условиях является частота обращения к файлу подкачки (page file). Операционная система Windows отводит часть дискового пространства под виртуальную память (virtual memory). Когда исчерпывается оперативная память, Windows сбрасывает часть ее содержимого на диск. Освободившаяся память предоставляется программе. Этот процесс называется подкачкой, поскольку страницы, сброшенные на диск, могут быть подгружены системой обратно в память при обращении к ним.

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

Приведенная в числе примеров программа Pager запрашивает все больше и больше памяти под создаваемые массивы до тех пор, пока программа не начнет обращаться к файлу подкачки. Введите количество памяти в мегабайтах, которое программа должна запросить, и нажмите кнопку Page (Подкачка). Если ввести небольшое значение, например 1 или 2 Мбайт, программа создаст массив в оперативной памяти, и будет выполняться быстро.

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

Программа Pager может использовать память одним из двух способов. Если вы нажмете кнопку Page, программа начнет последовательно обращаться к элементам массива. По мере перехода от одной части массива к другой, системе может потребоваться подгружать их с диска. После того, как часть массива оказалась в памяти, программа может продолжить работу с ней.

============12

Если же вы нажмете на кнопку Thrash (Пробуксовка), программа будет случайно обращаться к разным участкам памяти. При этом вероятность того, что нужная страница находится в этот момент на диске, намного возрастает. Это избыточное обращение к файлу подкачки называется пробуксовкой[RP2] памяти (thrashing). В табл. 1.4 приведено время исполнения программы Pager на компьютере с процессором Pentium с тактовой частотой 90 МГц и 24 Мбайт оперативной памяти. В зависимости от конфигурации вашего компьютера, скорости работы с диском, количества установленной оперативной памяти, а также наличия других запущенных параллельно приложений время выполнения программы может сильно различаться.

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

Для уменьшения числа обращений к файлу подкачки есть несколько способов. Основной прием — экономное расходование памяти. При этом надо помнить, что программа обычно не может занять всю физическую память, потому что часть ее занимает система и другие программы. Компьютер, на котором были получены результаты, приведенные в табл. 1.4, начинал интенсивно обращаться к диску, когда программа занимала 20 Мбайт из 24 Мбайт физической памяти.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48