Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 26 (всего у книги 36 страниц)
Исходный код процедуры TDHeapSort и вспомогательных процедур можно найти на web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDSorts.pas.
Расширение очереди по приоритету
Сделав небольшое отступление для ознакомления с пирамидальной сортировкой, пора вернуться к очередям по приоритету и рассмотреть задачу расширения реализованной нами структуры данных.
Мы разработали структуру данных, позволяющую выполнять две основные операции: постановку в очередь, обеспечивающую добавление элемента в структуру, и исключение из очереди, которая возвращает элемент структуры с наивысшим приоритетом (попутно мы рассмотрели определение приоритета за счет использования внешней функции сравнения). Полученную структуру мы назвали очередью по приоритету.
Однако структуры операционных систем, такие как очереди по приоритету потоков или очереди на печать, позволяют выполнять еще две операции: удалять элемент из очереди и возвращать его, независимо от позиции в очереди (элемент не обязательно должен быть наибольшим), а также изменять приоритет любого элемента в очереди.
При работе с очередью на печать операция удаления позволяет отменять задание на печать документа, печать которого больше не требуется, или удалять печатное задание из одной очереди и включать его в другую (например, если принтер, связанный с первой очередью, занят печатью крупного отчета). При работе с очередью по приоритету потоков можно временно повысить приоритет потока для повышения вероятности возобновления выполнения, когда операционная система в следующий раз решит изменить очередность обработки потоков.
На первый взгляд, реализация этих операций за счет использования сортирующего дерева может показаться затруднительной. Однако рассмотрим проблему подробнее. Классу очереди по приоритету нужно было бы передать ссылку на элемент, расположенный где-то в очереди, чтобы его можно было удалить или изменить его приоритет. Как найти элемент в очереди? Это один из тех случаев, когда "свободная" сортировка сортирующего дерева работает против нас. Единственным возможным методом поиска на этом этапе кажется последовательный поиск, но он выполняется достаточно медленно. После того как элемент найден, мы должны либо удалить его, либо изменить его приоритет, а затем восстановить полноту или пирамидальность сортирующего дерева, либо же оба свойства.
Восстановление свойства пирамидальное
Вторую проблему (восстановление свойства пирамидальности) проще решить, чем первую (отыскание элемента, который нужно удалить или изменить его приоритет). Поэтому вначале рассмотрим именно ее.
Чтобы удалить произвольный элемент из сортирующего дерева, его нужно было бы поменять местами с последним элементом и уменьшить размер сортирующего дерева. На этом этапе появляется элемент, который может нарушить свойство пирамидальности.
Для изменения приоритета произвольного элемента следует просто внести изменение, в результате чего элемент может также нарушить свойство пирамидальности.
В обоих случаях мы получаем элемент, который может находиться в сортирующем дереве в неподходящей позиции. Т.е. для этого конкретного элемента нарушается свойство пирамидальности. Но мы знаем, как следует поступить в ситуации подобного рода: ранее мы уже сталкивались с ней при работе со стандартной очередью по приоритету. Если приоритет данного элемента выше приоритета его родительского элемента, мы перемещаем элемент в верхнюю часть сортирующего дерева за счет применения алгоритма пузырькового подъема. В противном случае мы сравниваем его с дочерними элементами. Если он меньше одного или обоих дочерних элементов, то при помощи алгоритма просачивания мы опускаем его в нижнюю часть сортирующего дерева..Со временем элемент окажется в позиции, где он будет меньше своего родительского и больше обоих дочерних элементов.
Отыскание произвольного элемента в сортирующем дереве
Теперь осталось решить первоначальную проблему: эффективно найти элемент в сортирующем дереве. Эта проблема кажется неразрешимой – сортирующее дерево не содержит никакой вспомогательной информации, поскольку оно было разработано лишь для обеспечения эффективного поиска наибольшего элемента. Возврат к сбалансированному дереву двоичного поиска (при использовании которого для поиска элемента за время, пропорциональное O(log(n)), можно применить стандартный алгоритм поиска) кажется почти неизбежным.
Однако вместо этого мы создадим так называемое косвенное сортирующее дерево (indirect heap). При добавлении элемента в очередь по приоритету, управление этим элементом передается очереди. Взамен мы получаем дескриптор (handle). Дескриптор – это значение, по которому очередь "узнает" о добавлении элемента. Если хотите, дескриптор является косвенной ссылкой на реальный элемент в сортирующем дереве.
Итак, чтобы удалить элемент из очереди по приоритету, мы передаем очереди дескриптор этого элемента. Очередь использует этот дескриптор для выяснения позиции элемента в сортирующем дереве, а затем удаляет его, как было описано ранее.
Для изменения приоритета элемента мы просто изменяем значение приоритета элемента и сообщаем очереди о том, что произошло, передавая ей дескриптор элемента. Затем очередь может восстановить свойство пирамидальное™. Операция исключения из очереди работает так же, как и ранее (дескриптор элемента не нужно передавать, поскольку очередь сама определит наибольший элемент). Однако очередь уничтожит дескриптор возвращенного элемента, поскольку он больше не присутствует в очереди. Если элементы являются записями или объектами, дескриптор данного элемента можно хранить внутри самого элемента наряду с приоритетом и другими полями.
В рамках операционной системы дескриптор, который, как правило, представляет собой своего рода замаскированный указатель, обычно имеет тип длинного целого. В рассматриваемой реализации мы используем всего лишь нетипизированный указатель.
Реализация расширенной очереди по приоритету
С точки зрения пользователя очереди по приоритету новый интерфейс лишь немногим сложнее рассмотренного ранее. Код интерфейса класса расширенной очереди по приоритету TtdPriorityQueueEx приведен в листинге 9.9.
Листинг 9.9. Интерфейс класса TtdPriorityQueueEx
type
TtdPQHandle = pointer;
TtdPriorityQueueEx = class private
FCompare : TtdCompareFunc;
FHandles : pointer;
FList : TList;
FName : TtdNameString;
protected
function pqGetCount : integer;
procedure pqError(aErrorCode : integer;
const aMethodName : TtdNameString);
procedure pqBubbleUp(aHandle : TtdPQHandle);
procedure pqTrickleDown(aHandle : TtdPQHandle);
public
constructor Create(aCompare : TtdCompareFunc);
destructor Destroy; override;
procedure ChangePriority(aHandle : TtdPQHandle);
procedure Clear;
function Dequeue : pointer;
function Enqueue(alt em : pointer): TtdPQHandle;
function Examine : pointer;
function IsEmpty : boolean;
function Remove(aHandle : TtdPQHandle): pointer;
property Count : integer read pqGetCount;
property Name : TtdNameString read FName write FName;
end;
Как видите, единственное реальное различие между этим классом и классом TtdPriorityQueue состоит в наличии методов Remove и ChangePriority и в том, что метод Enqueue возвращает дескриптор.
Так как же реализован этот интерфейс? Внутренне очередь, как обычно, содержит сортирующее дерево, но на этот раз она должна поддерживать определенную дополнительную информацию, чтобы иметь возможность отслеживать позицию каждого элемента в сортирующем дереве. Кроме того, очередь должна идентифицировать каждый элемент дескриптором, чтобы поиск элемента по заданному дескриптору выполнялся быстро и эффективно – теоретически быстрее, чем в дереве двоичного поиска, где время поиска определяется соотношением O(log(n)).
Поэтому мы сделаем следующее: когда пользователь будет ставить элемент в очередь, мы будем добавлять элемент в связный список. Это будет сопряжено с определением и использованием узла и, по меньшей мере, двух указателей: указателя самого этого элемента и указателя следующего элемента, хотя по причинам, которые станут понятны несколько позже, мы будем использовать двухсвязный список и поэтому нам потребуется также и предыдущий указатель. Передаваемый нами обратно дескриптор элемента будет адресом узла. Теперь наступает важный момент. Узел хранит также целочисленное значение – позицию элемента в массиве, посредством которого реализовано сортирующее дерево. Сортирующее дерево не хранит сами элементы, а только их дескрипторы (т.е. узлы связного списка). Каждый раз, когда для выполнения сравнения ему нужно будет обратиться к самому элементу, оно будет разыменовывать дескриптор.
К сожалению, мы не можем использовать описанный в главе 3 класс связного списка, поскольку нам требуется доступ к узлам, а этот класс был разработан с целью сокрытия структуры узлов. Это один из случаев, когда нельзя использовать заранее стандартные классы и требуется выполнить кодирование от начала до конца. В случае применения двухсвязного списка это не так страшно, поскольку эта структура достаточно проста. Мы создадим связный список с явными начальным и конечным узлами. В результате удаление обычного узла превращается в исключительно простую задачу. Удаление узлов будет выполняться с применением обоих методов Dequeue и Remove класса расширенной очереди по приоритету.
Операции постановки в очередь и пузырькового подъема лишь немногим более сложны. Вначале мы создаем дескриптор, выделяя узел для элемента, и добавляем его в связный список узлов. Поскольку мы добавляем дескрипторы к сортирующему дереву, для доступа к элементам потребуется выполнять разыменование дескрипторов, а при перемещении элемента по сортирующему дереву индекс его новой позиции необходимо сохранять внутри узла. Код реализации методов постановки в очередь и пузырькового подъема приведен в листинге 9.10.
Листинг 9.10. Постановка в очередь и пузырьковый подъем в расширенной очереди по приоритету
procedure TtdPriorityQueueEx.pqBubbleUp(aHandle : pointer);
var
FromInx : integer;
ParentInx : integer;
ParentHandle : PpqexNode;
Handle : PpqexNode absolute aHandle;
begin
{если анализируемый дескриптор больше дескриптора родительского элемента, нужно их нужно поменять местами и продолжить процесс с новой позиции}
{Примечание: родительский узел дочернего узла, имеющего индекс n, имеет индекс (n-1)/2}
FromInx := Handle^.peInx;
if (FromInx > 0) then begin
ParentInx := (FromInx – 1) div 2;
ParentHandle := PpqexNode(FList.List^[ParentInx]);
{если элемент имеет родительский элемент и больше нее о...}
while (FromInx > 0) and
(FCompare (Handle^.peItem, ParentHandle^.peItem) > 0) do
begin
{нужно переместить родительский элемент вниз по дереву}
FList.List^[FromInx] := ParentHandle;
ParentHandle^.peInx := FromInx;
FromInx := ParentInx;
ParentInx := (FromInx – 1) div 2;
ParentHandle := PpqexNode(FList.List^[ParentInx]);
end;
end;
{сохранить элемент в правильной позиции}
FList.List^[FromInx] := Handle;
Handle^.peInx := FromInx;
end;
function TtdPriorityQueueEx.Enqueue(aItem : pointer): TtdPQHandle;
var
Handle : PpqexNode;
begin
{создать новый узел для связного списка}
Handle := AddLinkedListNode(FHandles, aItem);
{добавить дескриптор в конец очереди}
FList.Add(Handle);
Handle^.peInx := pred(FList.Count);
{теперь нужно выполнить его пузырьковый подъемна максимально возможный уровень}
if (FList.Count > 1) then
pqBubbleUp(Handle);
{вернуть дескриптор}
Result := Handle;
end;
Подобно методу Enqueue, все эти косвенные ссылки несколько усложняют метод Dequeue, но в коде все же можно распознать стандартные операции исключения из очереди и просачивания.
Листинг 9.11. Исключение из очереди и просачивание в расширенной очереди по приоритету
procedure TtdPriorityQueueEx.pqTrickleDown(aHandle : TtdPQHandle);
var
FromInx : integer;
MaxInx : integer;
ChildInx : integer;
ChildHandle : PpqexNode;
Handle : PpqexNode absolute aHandle;
begin
{если анализируемый элемент меньше одного из своих дочерних элементов, его нужно поменять местами с большим дочерним элементом и продолжить процесс из новой позиции}
FromInx := Handle^.peInx;
MaxInx := pred(FList.Count);
{вычислить индекс левого дочернего узла}
ChildInx := succ(FromInx * 2);
{если имеется по меньшей мере правый дочерний элемент, необходимо вычислить индекс большего дочернего элемента...}
while (ChildInx <= MaxInx) do
begin
{если есть хоть один правый дочерний узел, вычислить индекс наибольшего дочернего узла}
if ((ChildInx+1) <= MaxInx) and
(FCompare(PpqexNode(FList.List^[ChildInx])^.peItem, PpqexNode(FList.List^[ChildInx+ 1])^.peItem) < 0) then
inc(ChildInx);
{если элемент больше или равен большему дочернему элементу, задача выполнена}
ChildHandle := PpqexNode(FList.List^[ChildInx]);
if (FCompare (Handle^.peItem, ChildHandle^.peItem) >= 0) then
Break;
{в противном случае больший дочерний элемент нужно переместить вверх по дереву, а сам элемент – вниз}
FList.List^[FromInx] ChildHandle;
ChildHandle^.peInx := FromInx;
FromInx := ChildInx;
ChildInx := succ(FromInx * 2);
end;
{сохранить элемент в правильной позиции}
FList.List^[FromInx] := Handle;
Handle^.peInx := FromInx;
end;
function TtdPriorityQueueEx.Dequeue : pointer;
var
Handle : PpqexNode;
begin
{проверить наличие элементов, которые нужно исключить из очереди}
if (FList.Count = 0) then
pqError(tdeQueueIsEmpty, 'Dequeue');
{вернуть корневой элемент, удалить его из списка дескрипторов}
Handle := FList.List^[0];
Result := Handle^.peItem;
DeleteLinkedListNode(FHandles, Handle);
{если очередь содержала только один элемент, теперь она пуста}
if (FList.Count = 1) then
FList.Count := 0
{если она содержала два элемента, нужно просто заменить корневой элемент одним из оставшихся дочерних элементов. Очевидно, что при этом свойство пирамидальности сохраняется}
else
if (FList.Count = 2) then begin
Handle := FList.List^[1];
FList.List^[0] := Handle;
FList.Count := 1;
Handle^.peInx := 0;
end
{в противном случае свойство пирамидальности требует восстановления}
else begin
{заменить корневой узел дочерним узлом, расположенным в самой нижней, крайней справа позиции, и уменьшить размер списка; затем за счет применения метода просачивания переместить корневой узел как можно дальше вниз по дереву}
Handle := FList.Last;
FList.List^[0] := Handler-Handle^.peInx := 0;
FList.Count := FList.Count – 1;
pqTrickleDown(Handle);
end;
end;
После ознакомления с операциями постановки в очередь и исключения из нее можно рассмотреть новые операции: удаление и изменение приоритета. Метод ChangePriotity крайне прост. Прежде чем метод будет вызван, класс предполагает, что приоритет элемента был изменен. Вначале метод проверяет, имеет ли элемент родительский элемент, и если да, то больше ли элемент с новым приоритетом своего родительского элемента. Если это так, то элемент перемещается вверх за счет применения метода пузырькового подъема. Если операция пузырькового подъема невозможна или не требуется, метод проверяет возможность выполнения операции просачивания.
Листинг 9.12. Восстановление свойства пирамидальности после изменения приоритета
procedure TtdPriorityQueueEx.ChangePriority(aHandle : TtdPQHandle);
var
Handle : PpqexNode absolute aHandle;
ParentInx : integer;
ParentHandle : PpqexNode;
begin
{проверить возможность выполнения операции пузырькового подъема}
if (Handle^.peInx > 0) then begin
ParentInx := (Handle^.peInx – 1) div 2;
ParentHandle := PpqexNode(FList[ParentInx]);
if (FCompare( Handle^.peItem, Parent Handle^.peItem) > 0) then begin
pqBubbleUp(Handle);
Exit;
end;
end;
{в противном случае выполнить операцию просачивания}
pqTrickleDown(Handle);
end;
Последняя операция реализуется при помощи метода Remove. В данном случае мы возвращаем элемент, определенный дескриптором, а затем заменяем его последним элементом сортирующего дерева. Дескриптор удаляется из связного списка. Эта операция упрощается благодаря использованию двусвязного списка. Затем значение счетчика элементов в сортирующем дереве уменьшается на единицу. С этого момента процесс полностью совпадает с процессом изменения приоритета, поэтому мы просто вызываем соответствующий метод.
Листинг 9.13. Удаление элемента, заданного его дескриптором
function TtdPriorityQueueEx.Remove(aHandle : TtdPQHandle): pointer;
var
Handle : PpqexNode absolute aHandle;
NewHandle : PpqexNode;
HeapInx : integer;
begin
{вернуть элемент, а затем удалить дескриптор}
Result := Handle^.peItem;
HeapInx := Handle^.peInx;
DeleteLinkedListNode(FHandles, Handle);
{выполнить проверку того, что был удален последний элемент. Если это так, нужно просто уменьшить размер сортирующего дерева – при этом свойство пирамидальности будет сохранено}
if (HeapInx = pred(FList.Count)) then
FList.Count := FList.Count – 1
else begin
{заменить элемент сортирующего дерева дочерним элементом, расположенным в самой нижней крайней справа позиции, и уменьшить размер списка}
NewHandle := FList.Last;
FList.List^[HeapInx] := NewHandle;
NewHandle^.peInx := HeapInx;
FList.Count := FList.Count – 1;
{дальнейшие действия совпадают с выполнением операции изменения приоритета}
ChangePriority(NewHandle);
end;
end;
Полный код этого класса можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.
Резюме
В этой главе мы уделили основное внимание очередям по приоритету – очередям, которые возвращают не самый первый помещенный в них элемент, а элемент с наивысшим приоритетом. Исследовав несколько простых реализаций, мы ознакомились с реализацией, предполагающей использование сортирующего дерева. Мы рассмотрели базовые свойства и операции сортирующего дерева и научились применять их в как в качестве алгоритма пирамидальной сортировки, так и для удовлетворения первоначального требования, предъявляемого к очереди по приоритету.
И, наконец, мы расширили определение очереди по приоритету для обеспечения выполнения ряда дополнительных операций: удаления произвольного элемента и изменения приоритета данного элемента. Мы выяснили, какие изменения нужно внести в реализацию с целью поддержки этих операций.
Глава 10. Конечные автоматы и регулярные выражения.
Существует целый класс проблем, которые могут быть решены с помощью авторучки и бумаги. По-моему, это замечательный аспект программирования: иметь возможность графически представить какой-либо процесс, а затем закодировать его. Я имею в виду алгоритмы, в которых используются конечные автоматы.
Конечные автоматы
В отличие от большинства рассмотренных в этой книге алгоритмов, конечные автоматы – это технологии, призванные облегчать разработку других алгоритмов. Они служат средством достижения конечной цели – реализации алгоритма. Тем не менее, как будет показано, они обладают рядом интересных особенностей. В основном мы будем рассматривать конечные автоматы, которые реализуют алгоритмы синтаксического анализа (parsing algorithm). Синтаксический анализ означает считывание строки (или текстового файла) и разбиение последовательностей символов на отдельные лексемы. Конечный автомат, который выполняет синтаксический анализ, обычно называют синтаксическим анализатором (parser).
Использование конечного автомата: синтаксический анализ
Чтобы лучше понять весь процесс, рассмотрим пример. Предположим, что требуется разработать алгоритм, который должен извлекать отдельные слова из строки текста. Извлекаемые слова будут помещаться в список строк. Более того, желательно, чтобы внутри строки текст, заключенный в кавычки, воспринимался как одно слово. Т.е., если имеется строка:
Не said, "State machines?"
процедура должна игнорировать знаки препинания и пробелы и возвращать следующее:
Не
said
"State machines?"
Обратите внимание, что пробел и вопросительный знак внутри заключенного в кавычки текста остались без изменений.
Простейший способ реализации этого конкретного алгоритма – использование конечного автомата. Конечный автомат (state machine) – это система (обычно цифровая), которая переходит из одного состояния в другое в соответствии с принимаемыми ею входными данными (сигналами). Смена состояний называется переходом (trAnsition). Конечный автомат можно представить специальной блок-схемой. Блок схема рассматриваемого алгоритма показана на рис. 10.1.
Показанный на рисунке конечный автомат имеет три состояния: А, В и С. Работа блок-схемы начинается с состояния A. В этом состоянии выполняется считывание символа из входной строки. Если этот символ – двойная кавычка, осуществляется переход в состояние В. Если символ является пробелом или знаком препинания, выполняется переход в состояние С. Если это любой другой символ, конечный автомат остается в состоянии А (это показано петлей).
После перехода в состояние В считывание символов продолжается в нем до тех пор, пока не будет считан символ закрывающей двойной кавычки. В этот момент происходит переход обратно в состояние A.
С другой стороны, если был выполнен переход в состояние С, считывание символов продолжается в этом состоянии до тех пор, пока не произойдет одно из двух: либо не будет выполнено считывание символа двойной кавычки, в результате чего произойдет переход в состояние В, либо не будет выполнено считывание символа, который не является ни двойной кавычкой, ни пробелом, ни знаком препинания, в результате чего будет осуществлен переход в состояние A.
Рисунок 10.1. Конечный автомат извлечения слов из строки
Во время перехода может требоваться также выполнение какого-либо действия. Предположим, что мы используем строку для накапливания символов текущего слова. Первоначальный переход в состояние А очистит эту строку. Циклический переход из состояния А в состояние А допишет символ к текущему слову. Переход из состояния А в состояние В вначале добавит текущее слово (если таковое имеется) к списку строк, а затем установит в качестве текущего слова открывающую двойную кавычку. Циклический переход из состояния В в это же состояние допишет символ к текущему слову. Переход из состояния В обратно в состояние А допишет закрывающую двойную кавычку к текущему слову, добавит его в список строк, а затем очистит текущее слово. При переходе из состояния А в состояние С текущее слово добавляется в список строк, а затем очищается. Переход из состояния С в это же состояние не вызывает никаких действий (именно во время этого перехода происходит действительное отбрасывание пробелов и знаков препинания). При переходе из состояния С в состояние А значение текущего слова устанавливается равным считываемому символу. При переходе из состояния С в состояние В текущее слово устанавливается равным открывающей двойной кавычке.
Проанализировав рисунок 10.1, как это описано в предыдущем абзаце, легко убедиться, что конечный автомат прекрасно реализует рассматриваемый алгоритм.
Переход в состояние А; очистка слова
Считывание ' H1; сохранение состояния А; слово = ' H'
Считывание 'e'; сохранение состояния А; слово = ' Не'
Считывание ' '; переход в состояние С; вывод слова 'Не', очистка слова
Считывание 's'; переход в состояние А; слово = ' s'
Считывание 'a'; сохранение состояния А; слово = ' sa'
Считывание 'i'; сохранение состояния А; слово – 'sai'
Считывание 'd';сохранение состояния А; слово = 'said'
Считывание ','; переход в состояние С; вывод слова 'said', очистка слова
Считывание ' '; сохранение состояния С
Считывание '"';переход в состояние А;слово = '"'
Считывание 'S';сохранение состояния В; слово = "'S'
и. т.д.
Однако, блок-схема конечного автомата, показанная на рис. 10.1, обладает еще одной особенностью, о которой еще ничего не было сказано. Состояния А и С обозначены двойными окружностями, в то время как состояние В – одинарной. По соглашению в диаграммах конечных автоматов двойные окружности используются для обозначения конечного состояния (называемого также состоянием останова (halt state) или поглощающим состоянием (accepting state)). Когда входная строка полностью считана, конечный автомат оказывается в особом состоянии (применительно к приведенному выше примеру строки заключительное состояние конечного автомата – состояние А). Если заключительное состояние является конечным, говорят что конечный автомат поглощает входную строку. Независимо от того, какие символы (или, точнее, лексемы (tokens)) были найдены во входной строке и какие при этом были осуществлены переходы, конечный автомат «понимает» строку. С другой стороны, если бы конечный автомат прекратил работу в незавершенном состоянии, строка не была бы принята (поглощена) и конечный автомат не понял бы ее.
В данном случае состояние В не является поглощающим состоянием. Что это означает на практике? Если в момент, когда входная строка исчерпана, конечный автомат находится в состоянии В, это означает, что был считан первый символ двойной кавычки, но не второй. Т.е. конечный автомат считывает строку, содержащую текст с непарным символом двойной кавычки. В зависимости от строгости алгоритма, эта ситуация может считаться ошибкой либо просто игнорироваться. В алгоритме, изображенном на рис. 10.1, она считается ошибкой.
Если говорить об ошибках, хотя в данном конкретном примере эта ситуация не отражена, возможно состояние, когда переход к конкретному символу или лексеме невозможен. Это немедленно привело бы к ошибке. В дальнейшем будет показано, как это свойство можно встроить в сам конечный автомат.
Вычертив блок-схему, теперь ее необходимо реализовать. Для простоты понимания мы немного изменим ее, чтобы считывание входной строки управляло конечным автоматом, а не чтобы каждое состояние приводило к считыванию следующего символа из входной строки. Это облегчит понимание процесса выхода из конечного автомата.
Код реализации конечного автомата, показанного на рис. 10.1, приведен в листинге 10.1 (полный исходный код можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDStates.pas). Обратите внимание, что было решено назвать состояния не абстрактно А, В и С, как на рисунке, а с использованием описательных имен ScanNormal, ScanQuoted и ScanPunctuation (соответственно, СчитываниеОбычныхСимволов, СчитываниеКавычек и СчитываниеЗнаковПрепинания).
Листинг 10.1. Извлечение слов из строки
procedure TDExtractWords(const S : string; aList : TStrings);
type
TStates = (ScanNormal, ScanQuoted, ScanPunctuation);
const
WordDelim= ' !<>[]{}(),./?;:-+=*&';
var
State : TStates;
Inx : integer;
Ch : char;
CurWord : string;
begin
{инициализация путем очистки списка строк и начало работы в состоянии ScanNormal с пустым словом}
Assert(aList <> nil, 'TDExtractWords: list is nil');
aList.Clear;
State := ScanNormal;
CurWord := '';
{считывание всех символов строки}
for Inx := 1 to length(S) do
begin
{get the next character}
Ch := S[Inx];
{обработка в зависимости от состояния}
case State of
ScanNormal : begin
if (Ch = '"') then begin
if (CurWord <> '') then
aList.Add(CurWord);
CurWord := '';
State := ScanQuoted;
end
else
if (TDPosCh(Ch, WordDelim) <> 0) then begin
if (CurWord <> '') then begin
aList.Add(CurWord);
CurWord := '''';
end;
State := ScanPunctuation;
end else
CurWord := CurWord + Ch;
end;
ScanQuoted : begin
CurWord := CurWord + Ch;
if (Ch = '"') then begin
aList.Add(CurWord);
CurWord := '';
State := ScanNormal;
end;
end;
ScanPunctuation : begin
if (Ch = '''') then begin
CurWord := '''';
State := ScanQuoted;
end
else
if (TDPosCh(Ch, WordDelim) = 0) then begin
CurWord := Ch;
State := ScanNormal;
end end;
end;
end;
{если по достижении конца строки текущим состоянием является ScanQuoted, это означает несоответствие символа двойной кавычки}
if (State = ScanQuoted) then
raise EtdStateException.Create(FmtLoadStr (tdeStateMisMatchQuote,
[UnitName, 'TDExtractWords']));
{если текущее слово не является пустым, добавить его в список}
if (CurWord <> '') then
aList.Add(CurWord);
end;
Код извлекает символ из входной строки, а затем входит в оператор Case, который переключает текущее состояние. Для каждого состояния предусмотрены операторы If, которые реализуют соответствующие действия и переходы в зависимости от значения текущего символа. В конце кода, если завершение программы происходит в состоянии ScanQuoted, генерируется исключение.
–
Этот код работает неэффективно в 32-разрядной среде Delphi. Код строит текущее слово посимвольно, используя строковую операцию +. Для длинных строк этот метод крайне неэффективен, поскольку операция вынуждена периодически перераспределять область памяти, в которой хранится строка, для размещения дополнительных символов. Первоначально строка пуста. Затем в нее добавляется первый символ. Поскольку пустая строка является нулевым указателем, под нее выделяется определенный объем памяти (в лучшем случае 8 байт), и строка изменяется, чтобы указывать на него. Символ добавляется в строку. После того, как в нее будет добавлено еще семь символов, выделенный под строку объем памяти должен быть перераспределен, чтобы в нее можно было поместить еще один символ. Еще одна причина низкой эффективности программы связана с операцией добавления символа. Компилятор генерирует код, обеспечивающий преобразование символа во временную односимвольную строку, а затем объединяет эти строки. Понятно, что преобразование символа в длинную строку требует выделения дополнительного объема памяти.
Оба описанных фактора приводят к снижению быстродействия программы TDExtractWords. Чтобы решить указанные проблемы, можно внести в код следующие изменения, хотя они и делают конечную цель менее очевидной, по крайней мере, с точки зрения программиста, отвечающего за сопровождение.
• Вместо того чтобы установить значение переменной CurWord равным ' ', необходимо вызвать метод Set Length, чтобы заранее распределить память под строку. В зависимости от конкретных требований, следует выбрать приемлемое значение, определяющее длину слова в байтах. (Например, приемлемым значением может быть длина символа S. Длина извлекаемого слова не может превышать это значение.)
• Необходимо поддерживать переменную CurInx, определяющую позицию следующего символа. Ее начальным значением должен быть ноль.
• Для каждого добавляемого символа необходимо увеличивать значение CurInx и устанавливать значение CurWord [CurInx] равным символу.
• Когда требуется добавить текущее слово в список строк, необходимо снова вызвать метод SetLength, на этот раз передавая ему значение переменной CurInx. В результате длина строки будет устанавливаться равной количеству символов в строке. Затем значение CurInx необходимо переустановить равным нолю.
