Visual2000 · Архив статей А.Колесова & О.Павловой
Андрей Колесов, Ольга Павлова
© 2000, Андрей Колесов, Ольга ПавловаРеентерабельные процедуры (reentrable, с возможностью повторного входа) — это процедуры, которые позволяют использовать одну копию программы для обработки нескольких одновременных запросов. Если речь идет об однопроцессорной системе, то такая ситуация возможна в случае параллельной (точнее, псевдо-параллельной) работы отдельных исполняемых модулей, которые обращаются в одной библиотеке: первая программа обращается к процедуре некой библиотеки, ее прерывает другая, более приоритетная программа и обращается к той же процедуре.
Такая же ситуация может возникнуть и в однозадачной системе, допускающей распараллеливание вычислительных процессов (для многопроцессорных компьютеров).
Подобный случай возможен и внутри одной программы, работающей на обычном ПК. Например, вы написали процедуру Integral для вычисления определенного интеграла для функции, которая задается в виде указателя (для VB какой режим стал в принципе возможен с появлением в VB 5.0 функции AddressOf). Если же вам нужно взять двойной интеграл, то может легко получиться, что подынтегральная функция в свою очередь еще раз обратится к Intergal.
Идея реентерабельности процедур основывается на реализации двух постулатов:
Очевидно, что второй вариант гораздо проще в реализации, и понятно, что для VB- процедур это означает, что все внутренние переменные должны быть динамическими.
Частным, но наиболее распространенным вариантом реентерабельных процедур для однозадачных программ являются рекурсивные процедуры — те, которые в явном виде обращаются сами к себе. Использование рекурсивных алгоритмов может быть очень полезным, но следует помнить, что в общем случае может падать скорость вычислений (идет очень активное динамическое перераспределение памяти). Кроме того, глубокий уровень вложенности рекурсии может быть причиной выхода программы за пределы стекового пространства, то есть появления ошибки или даже аварийного останова системы.
Приведем несколько примеров использования рекурсивных процедур.
Пример 1. Процедура реверсивного преобразования строковой переменной (перестановка символов задом наперед). Такая встроенная функция появилась в VB 6.0 (SrtReverse) и разные способы ее реализации традиционными средствами Basic мы уже приводили (см. "Особенности работы со строковыми переменными в VB", часть 2). Еще один вариант с помощью рекурсивной функции выглядит следующим образом:
Public Function ReverseRecursion$(s$)
'
' инверсия строковой переменной с помощью
' рекурсивной функции
Dim c$
c$ = Left$(s$, 1)
If c$ = "" Then
' исходная строка пустая, завершаем рекурсию
ReverseRecursion$ = ""
Else
' не пустая строка - продолжаем рекурсию
ReverseRecursion$ = ReverseRecursion$(Mid$(s$, 2)) & c$
End If
End Function
Данный вариант выглядит не сложнее, чем традиционный алгоритм:
Function ReverseString$ (Source$)
Dim sReverse$, i%
For i = Len(Source$) To 1 Step -1
sReverse = sReverse & Mid$(Source, i, 1)
Next I
ReverseString$ = sReverse
End Function
Однако при этом рекурсивный алгоритм работает примерно в 3,5-4 раза медленнее. Обратите внимание, что все внутренние переменные ReverseRecursion (в данном случае это одна переменная c$) являются динамическими. Если же поставить ключевое слово Static в описании функции, то она будет просто неверно работать. (Попробуете сами — будет выдаваться пустая строка! Это объясняется просто — рекурсия заканчивается, когда переменная с$="", и именно она участвует в "обратном" формировании строки.)
Пример 2. Вычисление факториала N! = N * (N-1) *... 1 Это является классическим примером рекурсивного соотношения, которое записывается следующим образом:
N! = N * (N-1)! 0!=1
Такое вычисление также может быть реализовано в виде двух алгоритмов:
Public Function FactorialRecursion&(N%)
' вычисление факториала методом рекурсии
If N% = 0 Then ' Завершаем рекурсию - 0!
FactorialRecursion& = 1 ' 0! = 1
Else ' продолжаем рекурсию
FactorialRecursion& = N% * FactorialRecursion&(N% - 1)
End If
End Function
2) обычный цикл:
Public Function Factorial&(N%)
' вычисление факториала методом рекурсии
Dim Fact&, i%
Fact& = 1
If N% > 1 Then ' нетривиальный вариант
For i% = 2 To N%
Fact& = Fact& * i%
Next
End If
Factorial& = Fact&
End Function
Код в рекурсивной функции заметно короче, но работает в 4 раза медленнее.
Если вы сравните два варианта решения данной задачи, то увидите, что в них используется, казалось бы, один алгоритм - следующее значение функции вычисляется с помощью результата, полученного на предыдущем шаге. Однако при ближайшем рассмотрении мы обнаружим принципиальную разницу: при использовании цикла "значение предыдущего шага" уже известно, а в случае рекурсии — его еще только предстоит вычислить.
Представленные выше примеры являются слишком тривиальными, так как тут речь идет о простых линейных структурах заданной длины. В этом случае использование обычных циклов гораздо эффективнее (мы привели здесь рекурсию чисто из познавательных соображений). Но есть случаи когда рекурсия просто необходима — например, при обработке древовидных структур, когда, двигаясь от корня дерева, вам нужно пройти все его ветки, число и глубина которых заранее неизвестны. Классическим примером здесь является задача передвижения по каталогам файловой системы, которую мы рассмотрим в следующем совете.
Предположим, мы хотим определить число всех файлов, соответствующих заданному шаблону имени, в некотором каталоге. А заодно и количество вложенных подкаталогов. Такая задача решается с помощью процедуры HowManyFilesInThisDirectory, приведенной в листинге 230, а обращение к ней может выглядеть следующими образом:
PathName$ = "d:\qb_lib\" ' стартовый каталог FileName$ = "*.bas" ' шаблон имени файла FileCounter% = 0 ' начальное значение счетчика найденных файлов DirCounter% = 0 ' начальное значение счетчика просмотренных ' подкаталогов Call HowManyFilesInThisDirectory(PathName$, FileName$, FileCounter%)
Алгоритм этой процедуры достаточно прост — сначала выполняется поиск имен файлов в заданном каталоге, там же определяется список подкаталогов, а потом в цикле процедура обращается сама к себе с новым именем каталога. Тут все понятно, но следует обратить внимание на следующие моменты:
MyDir$ = Dir(PathName$, vbDirectory)
Do While MyDir$ <> ""
If MyDir$ <> "." And MyDir$ <> ".." Then
If GetAttr(PathName$ + MyDir$) = vbDirectory Then
' найден каталог
DirCounter% = MyDirCounter% + 1
NewPathName$ = PathName$ + MyDir$(i) + "\"
Call HowManyFilesInThisDirectory(NewPathName$, _
FileName$, FileCounter%)
End If
End If
MyDir$ = Dir ' следующий поиск
Loop
Однако такой код будет неправильным. Дело в том, что функция Dir не является реентерабельной. Более того, ее применение основано на цикле последовательных обращений, когда первое обращение (вызов функции с параметрами) задает шаблон поиска (который запоминается внутри функции в ее статической переменной), а затем (вызов функции без параметров) происходит как бы продолжение первоначально заданной операции.
Приведенный выше код нарушает такой порядок обращения — еще до завершения цикла по текущему шаблону управление передается в процедуру HowManyFilesInThisDirectory, где инициализируется новая операция первого поиска. Поэтому необходимо сначала составить полный список подкаталогов (процедура CurrentDirCounter), а уже потом, перебирая его в цикле, рекурсивно обращаться на обработку очередного каталога.
If MyDirCount% > UBound(arrPath$) Then ReDim Preserve arrPath$(UBound(arrPath$) + 100) End If
Это обеспечивает автоматическое увеличение начального размера динамического массива с сохранением ранее записанной информации.
Public DirCounter% ' текущее число просмотренных каталогов
Public Sub HowManyFilesInThisDirectory(PathName$, FileName$, FileCounter%)
'
' подсчет числа найден файлов по заданному шаблону
' PathName$ - каталог
' FileName$ - шаблон имени файла
' FileCounter% - текущее значение счетчика найденых файлов
'==================================================
Dim MyFile$, MyDirCount%
Dim NewPathName$, i%
DirCounter% = DirCounter% + 1 ' смотрим очередной каталог
'
' подсчет файлов в данном каталоге:
MyFile$ = Dir(PathName$ + FileName$) ' первый поиск
Do While MyFile$ <> ""
FileCounter% = FileCounter% + 1
' тут можно выполнить какую-нибуль операцию с файлом
MyFile$ = Dir ' следующий поиск
Loop
'
' определяем состав подкаталогов в данном каталоге
ReDim arrPath$(100) ' для списка подкаталов
Call CurrentDirCounter(PathName$, "", MyDirCount%, arrPath$(), vbDirectory)
'
If MyDirCount% > 0 Then 'есть подкаталоги
For i% = 1 To MyDirCount%
' !! рекурсивное обращение к САМОЙ СЕБЕ!!
NewPathName$ = PathName$ + arrPath$(i) + "\"
Call HowManyFilesInThisDirectory(NewPathName$, FileName$, FileCounter%)
Next
End If
End Sub
Public Sub CurrentDirCounter(PathName$, FileName$, MyDirCount%,
arrPath$(), attr%)
'
' Формирование списка имен элементов (attr% задает тип)
' в текущем каталоге
'
Dim MyDir$
MyDirCount% = 0 'счетчик подкаталов в текущем каталоге
MyDir$ = Dir(PathName$ + FileName$, attr%) 'первый поиск подкаталогов
Do While MyDir$ <> ""
If MyDir$ <> "." And MyDir$ <> ".." Then
If GetAttr(PathName$ + MyDir$) = attr% Then ' найден каталог
MyDirCount% = MyDirCount% + 1
If MyDirCount% > UBound(arrPath$) Then
' увеличивает размер массива с сохранением старой информации
ReDim Preserve arrPath$(UBound(arrPath$) + 100)
End If
arrPath$(MyDirCount%) = MyDir$
' Debug.Print MyDir$; GetAttr(PathName$ + MyDir$)
End If
End If
MyDir$ = Dir ' следующий поиск
Loop
'
End Sub
Традиционно системы DOS/Windows являются нечувствительными к регистру символов в именах файлов и каталогов: имена FileName, FiLENAME и т.д. являются идентичными. Однако в Unix-системах это не так, и мы, например, столкнулись с этой проблемой, когда начали заниматься созданием Web-узла, переписывая файлы с нашего локального компьютера на сервер.
Мы приняли однозначное правило — имена элементов оглавления пишутся только строчными буквами. Однако, если соблюдение этого правила в тексте HTML-файла не вызывает никаких сложностей — там все видно, то управление физическими названиями в оглавлении оказалось не так просто. Так, вид имени файла в окне Windows Explorer довольно часто совершенно не соответствует тому, каким он является на самом деле (не вполне понятно, почему).
Решением этой проблемы стало создание процедуры, которая автоматически просматривает заданные каталоги и производит замену всех символов в именах файлов и подкаталогов на строчные буквы.
Работа с отдельным файлов выглядит достаточно просто:
' PathName$ - имя каталога ' MyFile$ - исходный файл NewFile$ = LCase$(MyFile$) If NewFile$ <> MyName$ Then ' нужна замена имени Name PathName$ + MyName$ As PathName$ + NewFile$ End If
А как выполнить такую операцию для всех файлов по заданному шаблону? Казалось бы, это можно сделать так:
MyFile$ = Dir(PathName$ + FileName$) ' первый поиск Do While MyFile$ <> "" ' анализ имени и переименование (см. код выше) MyDir$ = Dir ' следующий поиск Loop
Но на самом деле такая конструкция работать не будет, опять же из-за отсутствия реентерабельности Dir. Действительно, еще до завершения операции с заданным шаблоном мы производим коррекцию списка элементов каталога. Поэтому корректная реализация изменения имен файлов в списке выглядит следующим образом (аналогично обработке подкаталогов в примере, приведенном выше):
ReDim arrPath$(100) ' для списка файлов
Call CurrentDirCounter(PathName$, MyDirCount%, _
arrPath$(), vbNormal)
'
If MyDirCount% > 0 Then ' есть подкаталоги
For i% = 1 To MyDirCount%
' анализ имени и переименование (см. код выше)
Next
End If
При работе с массивами довольно часто встречается ситуация, когда оказывается, что его размеров не хватает для реального объема данных и нужно увеличить эти размеры с сохранением уже записанной информации. Типичным примером является запись в массив текстового файла, число строк которого неизвестна (другой случай, связанный с формированием списка элементов каталога, приведен в Совете 230, процедура HowManyFilesInThisDirectory). В этом случае следует использовать ключевое слово Preserve в операторе Redim:
StartSize = 100 ' начальное значение массива
ReDim arrStrings$(1 To StartSize)
AddSize = 20 ' дискретность увеличения длины
Open FileName$ For Input As #1
iLen = 0 ' текущая позиция для записи
While Not EOF(1)
iLen = iLen + 1
If iLen > UBound(arrStrings$) Then
ReDim Preserve arrStrings$(UBound(arrStrings$) + AddSize)
End If
Line Input #1, arrStrings$(iLen)
Wend
Close #1
'
' Если хотите, то после окончания ввода можно уменьшить
' размеры массива до реального числа введенных элементов
ReDim Preserve arrStrings$(iLen)
Коррекция длины массива с использование Preserve возможна и для многомерных массивов, но при этом допускается изменение только последнего индекса (что связано с порядком хранения многомерных данных — по строкам). Например:
ReDim SomeArray(10, 10, 10) ReDim Preserve SomeArray(10, 10, 15) ' допустимо ReDim Preserve SomeArray(10, 15, 10) ' недопустимо
При работе с файлами можно использовать два метода их нумерации: статический, когда номер файла задается константой, например #2, или динамический, когда номер выбирается из списка свободных и хранится в переменной:
FileNumber = FreeFile Open FileName$ For Input As #FileNumber Line Input #FileNumber, a$
Динамический вариант обеспечивает защиту от ситуации, когда номер файла назначается повторно. Но здесь же кроется и определенная опасность: при работе с большим числом динамически открываемых файлов нужно четко следить за их своевременным закрытием. (Номер файла закрепляется за файлом момент открытия и освобождается в момент закрытия. Поэтому обращение к FreeFile нужно выполнять непосредственно перед оператором Open.) Во избежание таких проблем желательно при отладке следить за числом открытых файлов в программе.
Но самое главное — в одной программе нельзя использовать одновременно два метода. В крайнем случае нужно в начале программы открыть все файлы со статическими номерами, а уже потом работать с динамически выделяемыми адресами.