Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
Существует несколько способов уменьшения этих накладных расходов. Во‑первых, не следует использовать большого количества ненужных переменных. Даже если подпрограмма не использует их, Visual Basic все равно будет отводить память под эти переменные. Следующая версия функции BigAdd еще быстрее приводит к переполнению стека, чем предыдущая.
Private Function BigAdd(N As Double) As Double
Dim I1 As Integer
Dim I2 As Integer
Dim I3 As Integer
Dim I4 As Integer
Dim I5 As Integer
If N <= 1 Then
BigAdd = 1
Else
BigAdd = N + BigAdd (N - 1)
End If
End Function
Если вы не уверены, нужна ли переменная, используйте оператор Option Explicit и закомментируйте определение переменной. При попытке выполнить программу, Visual Basic сообщит об ошибке, если переменная используется в программе.
Вы также можете уменьшить использование стека за счет применения глобальных переменных. Если вы определите переменные в секции Declarations модуля вместо того, чтобы определять их в подпрограмме, то системе не понадобится отводить память при каждом вызове подпрограммы.
Лучшим решением будет определение переменных в процедуре при помощи зарезервированного слова Static. Статические переменные используются совместно всеми экземплярами процедуры, и системе не нужно отводить память под новые копии переменных при каждом вызове подпрограммы.
Необоснованное применение рекурсии
Менее очевидной опасностью является необоснованное применение рекурсии. При этом использование рекурсии не является наилучшим способом решения задачи. Приведенные выше функции факториала, наибольшего общего делителя, чисел Фибоначчи и функции BigAdd не обязательно должны быть рекурсивными. Лучшие, не рекурсивные версии этих функций описываются позже в этой главе.
=====98
В случае факториала и наибольшего общего делителя, ненужная рекурсия является по большей части безвредной. Обе эти функции выполняются достаточно быстро для достаточно больших выходных значений. Их выполнение также не будет ограничено размером стека, если вы не использовали большую часть стекового пространства в других частях программы.
С другой стороны, применение рекурсии ухудшает алгоритм вычисления чисел Фибоначчи. Для вычисления Fib(N), алгоритм вначале вычисляет Fib(N - 1) и Fib(N - 2). Но для вычисления Fib(N - 1) он должен сначала вычислить Fib(N - 2) и Fib(N - 3). При этом Fib(N - 2) вычисляется дважды.
Предыдущий анализ этого алгоритма показал, что Fib(1) и Fib(0) вычисляются Fib(N + 1) раз во время вычисления Fib(N). Так как Fib(30) = 832.040 то, чтобы вычислить Fib(29), приходится вычислять одни и те же значения Fib(0) и Fib(1) 832.040 раз. Алгоритм вычисления чисел Фибоначчи тратит огромное количество времени на вычисление этих промежуточных значений снова и снова.
В функции BigAdd существует другая проблема. Хотя она выполняется быстро, она приводит к большой глубине вложенности рекурсии, и очень быстро приводит к исчерпанию стекового пространства. Если бы не переполнение стека, то эта функция могла бы вычислять результаты для больших входных значений.
Похожая проблема существует и в функции факториала. Для входного значения N глубина рекурсии для факториала и функции BigAdd равна N. Функция факториала не может быть вычислена для таких больших входных значений, которые допустимы для функции BigAdd. Максимальное значение факториала, которое может уместиться в переменной типа double, равно 170! » 7,257E+306, поэтому это наибольшее значение, которое может вычислить эта функция. Хотя эта функция приводит к глубокой рекурсии, она вызывает переполнение до того, как наступит переполнение стека.
Когда нужно использовать рекурсию
Эти рассуждения могут заставить вас думать, что рекурсия всегда нежелательна. Но это определенно не так. Многие алгоритмы являются рекурсивными по своей природе. И хотя любой алгоритм можно переписать так, чтобы он не содержал рекурсии, многие алгоритмы сложнее понимать, анализировать, отлаживать и поддерживать, если они написаны нерекурсивно.
В следующих разделах приведены методы устранения рекурсии из любого алгоритма. Некоторые из полученных нерекурсивных алгоритмов также просты в понимании. Функции, вычисляющие без применения рекурсии факториал, наибольший общий делитель, числа Фибоначчи, и функцию BigAdd, относительно просты.
С другой стороны, нерекурсивные версии алгоритмов построений кривых Гильберта и Серпинского намного сложнее. Их труднее понять, поддерживать, и они даже выполняются немного медленнее, чем рекурсивные версии. Они приведены лишь для того, чтобы продемонстрировать методы, которые вы можете использовать для устранения рекурсии из сложных алгоритмов, а не потому, что они лучше, чем рекурсивные версии соответствующих алгоритмов.
Если алгоритм рекурсивен по природе, записывайте его с использованием рекурсии. В лучшем случае, вы не встретитесь ни одной из описанных проблем. Если же вы столкнетесь с некоторыми из них, вы сможете переписать алгоритм без использования рекурсии при помощи методов, представленных в следующих разделах. Переписать алгоритм часто гораздо проще, чем с самого начала написать его без применения рекурсии.
======99
Хвостовая рекурсия
Вспомним представленные ранее функции для вычисления факториалов и наибольшего общего делителя, а также функцию BigAdd, которая приводит к переполнению стека даже для относительно небольших входных значений.
Private Function Factorial(num As Integer) As Integer
If num <= 0 Then
Factorial = 1
Else
Factorial = num * Factorial(num - 1)
End If
End Function
Private Function GCD(A As Integer, B As Integer) As Integer
If B Mod A = 0 Then
GCD = A
Else
GCD = GCD(B Mod A, A)
End If
End Function
Private Function BigAdd(N As Double) As Double
If N <= 1 Then
BigAdd = 1
Else
BigAdd = N + BigAdd(N - 1)
End If
End Function
Во всех этих функциях, последнее действие перед завершением функции — это рекурсивный шаг. Этот тип рекурсии в конце процедуры называется хвостовой рекурсией (tail recursion или end recursion).
Так как после рекурсии в процедуре ничего не происходит, существует простой способ ее устранения. Вместо рекурсивного вызова функции, процедура сбрасывает свои параметры, устанавливая те, которые бы она получила при рекурсивном вызове, и затем выполняется снова.
Рассмотрим общий случай рекурсивной процедуры:
Private Sub Recurse(A As Integer)
' Выполняются какие‑либо действия, вычисляется B, и т.д.
Recurse B
End Sub
======100
Эту процедуру можно переписать без рекурсии как:
Private Sub NoRecurse(A As Integer)
Do While (not done)
' Выполняются какие‑либо действия, вычисляется B, и т.д.
A = B
Loop
End Sub
Эта процедура называется устранением хвостовой рекурсии (tail recursion removal или end recursion removal). Этот прием не изменяет время выполнения программы. Рекурсивные шаги просто заменяются проходами в цикле While.
Устранение хвостовой рекурсии, тем не менее, устраняет вызовы подпрограмм, и поэтому может увеличить скорость работы алгоритма. Что более важно, этот метод также уменьшает использование стека. Алгоритмы типа функции BigAdd, которые ограничены глубиной рекурсии, могут от этого значительно выиграть.
Некоторые компиляторы автоматически устраняют хвостовую рекурсию, но компилятор Visual Basic этого не делает. В противном случае, функция BigAdd, приведенная в предыдущем разделе, не приводила бы к переполнению стека.
Используя устранение хвостовой рекурсии, легко переписать функции факториала, наибольшего общего делителя, и BigAdd без рекурсии. Эти версии используют зарезервированное слово ByVal для сохранения значений своих параметров для вызывающей процедуры.
Private Function Factorial(ByVal N As Integer) As Double
Dim value As Double
value = 1# ' Это будет значением функции.
Do While N > 1
value = value * N
N = N - 1 ' Подготовить аргументы для "рекурсии".
Loop
Factorial = value
End Function
Private Function GCD(ByVal A As Double, ByVal B As Double) As Double
Dim B_Mod_A As Double
B_Mod_A = B Mod A
Do While B_Mod_A <> 0
' Подготовить аргументы для "рекурсии".
B = A
A = B_Mod_A
B_Mod_A = B Mod A
Loop
GCD = A
End Function
Private Function BigAdd(ByVal N As Double) As Double
Dim value As Double
value = 1# ' ' Это будет значением функции.
Do While N > 1
value = value + N
N = N - 1 ' подготовить параметры для "рекурсии".
Loop
BigAdd = value
End Function
=====101
Для алгоритмов вычисления факториала и наибольшего общего делителя практически не существует разницы между рекурсивной и нерекурсивной версиями. Обе версии выполняются достаточно быстро, и обе они могут оперировать задачами большой размерности.
Для функции BigAdd, тем не менее, разница огромна. Рекурсивная версия приводит к переполнению стека даже для довольно небольших входных значений. Поскольку нерекурсивная версия не использует стек, она может вычислять результат для значений N вплоть до 10154. После этого наступит переполнение для данных типа double. Конечно, выполнение 10154 шагов алгоритма займет очень много времени, поэтому возможно вы не станете проверять этот факт сами. Заметим также, что значение этой функции совпадает со значением более просто вычисляемой функции N * N(N + 1) / 2.
Программы Facto2, GCD2 и BigAdd2 демонстрируют эти нерекурсивные алгоритмы.
Нерекурсивное вычисление чисел Фибоначчи
К сожалению, нерекурсивный алгоритм вычисления чисел Фибоначчи не содержит только хвостовую рекурсию. Этот алгоритм использует два рекурсивных вызова для вычисления значения, и второй вызов следует после завершения первого. Поскольку первый вызов не находится в самом конце функции, то это не хвостовая рекурсия, и от ее нельзя избавиться, используя прием устранения хвостовой рекурсии.
Это может быть связано и с тем, что ограничение рекурсивного алгоритма вычисления чисел Фибоначчи связано с тем, что он вычисляет слишком много промежуточных значений, а не глубиной вложенности рекурсии. Устранение хвостовой рекурсии уменьшает глубину рекурсии, но оно не изменяет время выполнения алгоритма. Даже если бы устранение хвостовой рекурсии было бы применимо к алгоритму вычисления чисел Фибоначчи, этот алгоритм все равно остался бы чрезвычайно медленным.
Проблема этого алгоритма в том, что он многократно вычисляет одни и те же значения. Значения Fib(1) и Fib(0) вычисляются Fib(N + 1) раз, когда алгоритм вычисляет Fib(N). Для вычисления Fib(29), алгоритм вычисляет одни и те же значения Fib(0) и Fib(1) 832.040 раз.
Поскольку алгоритм многократно вычисляет одни и те же значения, следует найти способ избежать повторения вычислений. Простой и конструктивный способ сделать это — построить таблицу вычисленных значений. Когда понадобится промежуточное значение, можно будет взять его из таблицы, вместо того, чтобы вычислять его заново.
=====102
В этом примере можно создать таблицу для хранения значений функции Фибоначчи Fib(N) для N, не превосходящих 1477. Для N >= 1477 происходит переполнение переменных типа double, используемых в функции. Следующий код содержит измененную таким образом функцию, вычисляющую числа Фибоначчи.
Const MAX_FIB = 1476 ' Максимальное значение.
Dim FibValues(0 To MAX_FIB) As Double
Private Function Fib(N As Integer) As Double
' Вычислить значение, если оно не находится в таблице.
If FibValues(N) < 0 Then _
FibValues(M) = Fib(N - 1) + Fib(N - 2)
Fib = FibValues(N)
End Function
При запуске программы, она присваивает каждому элементу в массиве FibValues значение -1. Затем она присваивает FibValues(0) значение 0, и FibValues(1) — значение 1. Это условия остановки рекурсии.
При выполнении функции, она проверяет, находится ли уже в массиве значение, которое ей требуется. Если его там нет, она, как и раньше, рекурсивно вычисляет это значение и сохраняет его в массиве для дальнейшего использования.
Программа Fibo2 использует этот метод для вычисления чисел Фибоначчи. Программа может быстро вычислить Fib(N) для N до 100 или 200. Но если вы попытаетесь вычислить Fib(1476), то программа выполнит последовательность рекурсивных вызовов глубиной 1476 уровней, которая вероятно переполнит стек вашей системы.
Тем не менее, по мере того, как программа вычисляет новые значения, она заполняет массив FibValues. Значения из массива позволяют функции вычислять все большие и большие значения без глубокой рекурсии. Например, если вычислить последовательно Fib(100), Fib(200), Fib(300), и т.д. то, в конце концов, можно будет заполнить массив значений FibValues и вычислить максимальное возможно значение Fib(1476).
Процесс медленного заполнения массива FibValues приводит к новому методу вычисления чисел Фибоначчи. Когда программа инициализирует массив FibValues, она может заранее вычислить все числа Фибоначчи.
Private Sub InitializeFibValues()
Dim i As Integer
FibValues(0) = 0 ' Инициализация условий остановки.
FibValues(1) = 1
For i = 2 To MAX_FIB
FibValues(i) = FibValues(i - 1) + FibValues(i - 2)
Next i
End Sub
Private Function Fib(N As Integer) As Duble
Fib - FibValues(N)
End Function
=====104
Определенное время в этом алгоритме занимает составление массива с табличными значениями. Но после того как массив создан, для получения элемента из массива требуется всего один шаг. Ни процедура инициализации, ни функция Fib не используют рекурсию, поэтому ни одна из них не приведет к исчерпанию стекового пространства. Программа Fibo3 демонстрирует этот подход.
Стоит упомянуть еще один метод вычисления чисел Фибоначчи. Первое рекурсивное определение функции Фибоначчи использует подход сверху вниз. Для получения значения Fib(N), алгоритм рекурсивно вычисляет Fib(N - 1) и Fib(N - 2) и затем складывает их.
Подпрограмма InitializeFibValues, с другой стороны, работает снизу вверх. Она начинает со значений Fib(0) и Fib(1). Она затем использует меньшие значения для вычисления больших, до тех пор, пока таблица не заполнится.
Вы можете использовать тот же подход снизу вверх для прямого вычисления значений функции Фибоначчи каждый раз, когда вам потребуется значение. Этот метод требует больше времени, чем выборка значений из массива, но не требует дополнительной памяти для таблицы значений. Это пример пространственно‑временного компромисса. Использование большего объема памяти для хранения таблицы значений делает выполнение алгоритма более быстрым.
Private Function Fib(N As Integer) As Double
Dim Fib_i_minus_1 As Double
Dim Fib_i_minus_2 As Double
Dim fib_i As Double
Dim i As Integer
If N <= 1 Then
Fib = N
Else
Fib_i_minus_2 = 0 ' Вначале Fib(0)
Fib_i_minus_1 = 1 ' Вначале Fib(1)
For i = 2 To N
fib_i = Fib_i_minus_1 + Fib_i_minus_2
Fib_i_minus_2 = Fib_i_minus_1
Fib_i_minus_1 = fib_i
Next i
Fib = fib_i
End If
End Function
Этой версии требуется порядка O(N) шагов для вычисления Fib(N). Это больше, чем один шаг, который требовался в предыдущей версии, но намного быстрее, чем O(Fib(N)) шагов в исходной версии алгоритма. На компьютере с процессором Pentium с тактовой частотой 90 МГц, исходному рекурсивному алгоритму потребовалось почти 52 секунды для вычисления Fib(32) = 2.178.309. Время вычисления Fib(1476) » 1,31E+308 при помощи нового алгоритма пренебрежимо мало. Программа Fibo4 использует этот метод для вычисления чисел Фибоначчи.
Страницы: 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
