Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 36 (всего у книги 36 страниц)
type
TtdLCSDir = (ldNorth, ldNorthWest, ldWest);
PtdLCSData = ^TtdLCSData;
TtdLCSData = packed record
ldLen : integer;
ldPrev : TtdLCSDir;
end;
type
TtdLCSMatrix = class private
FCols : integer;
FMatrix : TList;
FRows : integer;
protected
function mxGetItem(aRow, aCol : integer): PtdLCSData;
procedure mxSetItem(aRow, aCol : integer;
aValue : PtdLCSData);
public
constructor Create(aRowCount, aColCount : integer);
destructor Destroy; override;
procedure Clear;
property Items [aRow, aCol : integer] : PtdLCSData
read mxGetItem write mxSetItem;
default;
property RowCount : integer read FRows;
property ColCount : integer read FCols;
end;
constructor TtdLCSMatrix.Create(aRowCount, aColCount : integer);
var
Row : integer;
ColList : TList;
begin
{создать производный объект}
inherited Create;
{выполнить простую проверку}
Assert ((aRowCount > 0) and (aColCount > 0),
' TtdLCSMatrix.Create: Invalid Row or column count');
FRows := aRowCount;
FCols := aColCount;
{создать матрицу: она будет матрицей TList матриц TLists, упорядоченных по строкам}
FMatrix := TList.Create;
FMatrix.Count := aRowCount;
for Row := 0 to pred(aRowCount) do
begin
ColList := TList.Create;
ColList.Count := aColCount;
TList(FMatrix.List^[Row]) := ColList;
end;
end;
destructor TtdLCSMatrix.Destroy;
var
Row : integer;
begin
{уничтожить матрицу}
if (matrix <> nil) then begin
Clear;
for Row := 0 to pred(FRows) do
TList(FMatrix.List^[Row]).Free;
FMatrix.Free;
end;
{уничтожить производный объект}
inherited Destroy;
end;
procedure TtdLCSMatrix.Clear;
var
Row, Col : integer;
ColList : TList;
begin
for Row := 0 to pred(FRows) do
begin
ColList := TList(FMatrix.List^[Row]);
if (ColList <> nil) then
for Col := 0 to pred(FCols) do
begin
if (ColList.List^[Col] <> nil) then
Dispose(PtdLCSData(ColList.List^[Col]));
ColList.List^[Col] :=nil;
end;
end;
end;
function TtdLCSMatrix.mxGetItem(aRow, aCol : integer): PtdLCSData;
begin
if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then
raise Exception.Create(
'TtdLCSMatrix.mxGetItem: Row or column index out of bounds');
Result := PtdLCSData(TList(FMatrix.List^[aRow]).List^[aCol]);
end;
procedure TtdLCSMatrix.mxSetItem(aRow, aCol : integer;
aValue : PtdLCSData);
begin
if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then
raise Exception.Create(
'TtdLCSMatrix.mxSetItem: Row or column index out of bounds');
TList(Matrix.List^[aRow]).List^[aCol] := aValue;
end;
Следующий шаг заключается в создании класса, который реализует алгоритм вычисления LCS для строк. Код интерфейса и выполнения служебных функций класса TtdStringLCS приведен в листинге 12.23.
Листинг 12.23. Класс TtdStringLCS
type
TtdStringLCS = class private
FFromStr : string;
FMatrix : TtdLCSMatrix;
FToStr : string;
protected
procedure slFillMatrix;
function slGetCell(aFromInx, aToInx : integer): integer;
procedure slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
public
constructor Create(const aFromStr, aToStr : string);
destructor Destroy; override;
procedure WriteChanges(const aFileName : string;
end;
constructor TtdStringLCS.Create(const aFromStr, aToStr : string);
begin
{создать производный объект}
inherited Create;
{сохранить строки}
FFromStr := aFromStr;
FToStr :=aToStr;
{создать матрицу}
FMatrix := TtdLCSMatrix.Create(succ(length(aFromStr)), succ(length(aToStr)));
{заполнить матрицу}
slFillMatrix;
end;
destructor TtdStringLCS.Destroy;
begin
{уничтожить матрицу}
FMatrix.Free;
{уничтожить производный объект}
inherited Destroy;
end;
При первой реализации алгоритма вычисления LCS я столкнулся с дилеммой: придерживаться ли ранее описанного рекурсивного алгоритма или же только что описанного процесса вычисления LCS вручную? Чтобы получить ответ на ряд вопросов (какой из методов проще, какой требует использования меньшего объема памяти, какой работает быстрее), я реализовал оба подхода, причем начал с реализации итеративного метода. Это итеративное решение приведено в листинге 12.24.
Листинг 12.24. Итеративное вычисление LCS
procedure TtdStringLCS.slFillMatrix;
var
FromInx : integer;
ToInx : integer;
NorthLen: integer;
WestLen : integer;
LCSData : PtdLCSData;
begin
{создать пустые элементы, располагающиеся вдоль верхней и левой сторон матрицы}
for ToInx := 0 to length (FToStr) do
begin
New(LCSData);
LCSData^.ldLen := 0;
LCSData^.ldPrev := ldWest;
FMatrix[0, ToInx] := LCSData;
end;
for FromInx := 1 to length (FFromStr) do
begin
New(LCSData);
LCSData^.ldLen := 0;
LCSData^.ldPrev := ldNorth;
FMatrix [FromInx, 0] := LCSData;
end;
{построчное, слева направо, заполнение матрицы}
for FromInx := 1 to length (FFromStr) do
begin
for ToInx := 1 to length (FToStr) do
begin {создать новый элемент}
New(LCSData);
{если два текущих символа совпадают, необходимо увеличить значение счетчика элемента, расположенного к северо-западу, т.е. предыдущего элемента}
if (FFromStr[FromInx] = FToStr[ToInx]) then begin
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := succ(FMatrix[FromInx-1, ToInx-1]^.ldLen);
end
{в противном случае текущие символы различны: необходимо использовать максимальный из элементов, расположенных к северу или к западу от текущего (к западу предпочтительнее)}
else begin
NorthLen := FMatrix[FromInx-1, ToInx]^.ldLen;
WestLen := FMatrix[FromInx, ToInx-1]^.ldLen;
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev :=ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить элемент в матрице}
FMatrix[FromInx, ToInx] := LCSData;
end;
end;
{на этом этапе длина элемента, расположенного в нижнем правом углу, равна LCS, и вычисление завершено}
end;
Мы начинаем с заполнения верхней строки и левого столбца матрицы нулевыми ячейками. Длина LCS в этих ячейках равна нулю (вспомните, что они описывают LCS пустой и какой-либо другой строки), и мы всего лишь устанавливаем флаг направления, дабы он указывал на предшествующую ячейку, ближайшую к ячейке (0,0). Затем следует вложенный цикл (цикл по столбцам внутри цикла по строкам). Для каждой строки мы вычисляем LCS для каждой из ячеек,.просматривая их слева направо. Эти вычисления выполняются для всех строк сверху вниз. Вначале мы проверяем, совпадают ли два символа, на которые ссылается ячейка. (Ячейка матрицы представляет собой переход от символа строки From (Из) к символу строки То (В).) Если они совпадают, длина LCS в этой ячейке равна длине LCS ячейки, расположенной к северо-западу от данной, плюс единица. Обратите внимание, что способ вычисления ячеек предполагает, что ячейка, на которую осуществляется ссылка, уже вычислена (именно поэтому мы заранее вычислили значения ячеек, расположенных вдоль верхней и левой сторон матрицы). Если два символа не совпадают, необходимо просмотреть ячейки, расположенные к северу и к западу от текущей. Мы выбираем ту, которая содержит наиболее длинную LCS, и используем это значение в качестве значения данной ячейки. Если две длины равны, можно выбрать любую из них. Однако мы будем придерживаться правила, что предпочтительнее выбирать LCS, соответствующую ячейке, которая расположена слева. Этот выбор обусловлен тем, что как только путь через матрицу, обеспечивающий определение LCS обеих строк, вычислен, удаления из первой строки выполняются раньше вставок во вторую строку.
Обратите внимание, что приведенный в листинге 12.24 метод требует постоянного времени для обработки двух строк, независимо от степени их совпадения или несовпадения. Если длина строк равна, соответственно, n и т, то время, требуемое для выполнения основного цикла, будет пропорционально произведению n * m, поскольку таковым является количество ячеек, значения которых нужно вычислить. (помните, что ячейка, для которой действительно нужно получить ответ – последняя, значение которой должно вычисляться;
она расположена в нижнем правом углу матрицы).
Алгоритм, реализованный с применением рекурсивного метода, приведен в листинге 12.25. Рекурсивная подпрограмма кодируется в виде функции, которая возвращает длину LCS для конкретной ячейки, заданной индексом строки и столбца (которые, в конечном счете, представляют собой индексы, указывающие на строки From и То).
Листинг 12.25. Рекурсивное вычисление LCS
function TtdStringLCS.slGetCell(aFromInx, aToInx : integer): integer;
var
LCSData : PtdLCSData;
NorthLen: integer;
WestLen : integer;
begin
if (aFromInx = 0) or (aToInx = 0) then
Result := 0
else begin
LCSData := FMatrix[ aFromInx, aToInx];
if (LCSData <> nil) then
Result := LCSData^.ldLen else begin
{создать новый элемент}
New(LCSData);
{если два символа совпадают, необходимо увеличить значение счетчика относительно элемента, расположенного к северо-западу от данного, т.е. предшествующего элемента}
if (FFromStr[aFromInx] = FToStr [aToInx]) then begin
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;
end
{в противном случае текущие символы различаются: необходимо использовать максимальный из элементов, расположенных к северу и западу (выбор элемента расположенного к западу предпочтительнее)}
else begin
NorthLen := slGetCell(aFromInx-1, aToInx);
WestLen := slGetCell(aFromInx, aToInx-1);
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev := ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить значение элемента матрицы}
FMatrix[aFromInx, aToInx] := LCSData;
{вернуть длину данной LCS}
Result := LCSData^.ldLen;
end;
end;
end;
Первое существенное различие состоит в том, что не нужно генерировать нулевые значения для ячеек, расположенных вдоль верхней и правой сторон матрицы. Теперь эту задачу выполняет простой оператор If. (Честно говоря, в итеративном варианте вычисления LCS можно было бы обойтись без вычисления этих значений, но в этом случае внутренний код цикла оказался бы значительно сложнее для понимания и поддержки. Поэтому для простоты мы заранее вычисляем значения этих ячеек.) Если значение ячейки уже вычислено, мы просто возвращаем ее длину LCS. Если нет, необходимо выполнить ту же проверку, что и в предыдущем случае: совпадают ли два символа? Если да, то необходимо добавить единицу к значению LCS ячейки, расположенной к северо-западу от данной. Если нет, необходимо использовать большее из значений длины LCS ячеек, расположенных к северу и к западу от текущей. Естественно, эти значения LCS вычисляются в результате рекурсивных вызовов этой подпрограммы.
Применив обе версии (итеративную и рекурсивную), я сгенерировал матрицу для вычисления LCS слов "illiteracy" и "innumeracy". (Длина LCS этих слов равна 6 и выглядит как "ieracy".) Результаты этих немалых трудов приведены в таблицах 12.2 и 12.3. При использовании рекурсивной версии многие ячейки вообще не вычисляются (они помечены знаком вопроса). Эти ячейки образуют часть заключительной LCS.
Таблица 12.2. Итеративная матрица LCS слов "illiteracy" и "innumeracy".
Таблица 12.3. Рекурсивная матрица LCS слов «illiteracy» и «innumeracy».
Итак, мы получили матрицу, которая определяет наиболее длинную общую подпоследовательность. Как ее можно использовать? Одна возможность связана с реализацией подпрограммы, которая создает текстовый файл, описывающий изменения, называемые последовательностью редактирования (edit sequence). Это может упростить создание аналогичной подпрограммы для текстового файла – что, собственно, является конечной целью данного раздела.
Код реализации простой технологии обхода, которая может быть приведена в соответствие с нашими потребностями, показан в листинге 12.26. Подпрограмма содержит два метода: первый вызывается пользователем с указанием имени файла, а второй представляет собой рекурсивную подпрограмму, которая записывает данные в файл. Весь основной объем работы выполняется во второй подпрограмме. Поскольку в матрице путь LCS кодируется в обратном направлении (т.е. для определения пути необходимо начать с конца и продвигаться к началу матрицы), мы создаем метод, который вначале вызывает сам себя, а затем записывает данные, соответствующие текущей позиции. Необходимо обеспечить прерывание выполнения рекурсивной подпрограммы. Это соответствует случаю, когда подпрограмма вызывается для ячейки (0,0). В этом случае никакие данные не записываются в файл. Если индекс строки То равен нулю, мы выполняем рекурсивный вызов, перемещаясь вверх по матрице (индекс строки From уменьшается), и предпринимаемым действием должно быть удаление символа из строки From. Если индекс строки From равен нулю, мы выполняем рекурсивный вызов, перемещаясь по матрице влево, и тогда действием является ставка текущего символа в строку То. И, наконец, если оба индекса не равны нулю, мы находим соответствующую ячейку в матрице, выполняем рекурсивный вызов и записываем действие в файл. Перемещению вниз соответствует удаление, перемещению вправо – вставка, перемещению по диагонали – ни одно из упомянутых действий (символ "переносится" из одной строки в другую). Для обозначения удаления мы будем использовать стрелку, указывающую вправо (-> ), а для обозначения вставки – стрелку, указывающую влево (<-). Перенос символа не обозначается.
Листинг 12.26. Вывод последовательности редактирования
procedure TtdStringLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса равны нулю, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = 0) and (aToInx = 0) then
Exit;
{если индекс строки From равен нулю, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = 0) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToStr[aToInx]);
end
{если индекс строки To равен нулю, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = 0) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '< – FFromStr[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth : begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, ' <– ', FFromStr[aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, ' ', FFromStr[aFromInx]);
end;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '-> FToStr[aToInx]);
end;
end;
end;
end;
procedure TtdStringLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange(F, length(FFromStr), length(FToStr));
finally
System.Close(F);
end;
end;
Ниже показан текстовый файл, который был сгенерирован для преобразования слова «illiteracy» в слово «innumeracy».
< – i
<– l
<– l
i
<– t
–> n
–> n
–> u
–> m
e
r
a
с
y
Это представление действий по редактированию легко доступно для понимания, но при необходимости его можно развернуть. Как видите, наиболее длинная общая подпоследовательностью является (i, e, r, a, c, y), а определение удалений и вставок не представляет сложности.
Памятуя о том, что примененный метод является рекурсивным, следует подумать о требуемой для его реализации глубине стека. Если бы строки вообще не имели общих символов, последовательность редактирования сводилась бы к удалению всех символов первой строки и вставке всех символов второй строки. Если первая строка содержит n символов, а вторая m, глубина стека должна быть пропорциональной сумме n + m.
Вычисление LCS двух файлов
После того, как мы ознакомились с решением для двух строк, его можно модифицировать для вычисления LCS и генерации команд редактирования для двух текстовых файлов. Дабы упростить себе задачу, выполним считывание обоих файлов в объект TStringsLists. Понятно, что теперь одновременно выполняется сравнение целых текстовых строк, а не символов, тем не менее, в основном, реализация остается практически той же самой. Код интерфейса и вспомогательных методов приведен в листинге 12.27.
Листинг 12.27. Класс TtdFileLCS
type
TtdFileLCS = class private
FFromFile : TStringList;
FMatrix : TtdLCSMatrix;
FToFile : TStringList;
protected
function slGetCell(aFromInx, aToInx : integer): integer;
procedure slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
public
constructor Create(const aFromFile, aToFile : string);
destructor Destroy; override;
procedure WriteChanges(const aFileName : string);
end;
constructor TtdFileLCS.Create(const aFromFile, aToFile : string);
begin
{создать производный объект}
inherited Create;
{выполнить считывание файлов}
FFromFile := TStringList.Create;
FFromFile.LoadFromFile(aFromFile);
FToFile := TStringList.Create;
FToFile.LoadFromFile(aToFile);
{создать матрицу}
FMatrix := TtdLCSMatrix.Create(FFromFile.Count, FToFile.Count);
{заполнить матрицу}
slGetCell(pred(FFromFile.Count), pred(FToFile.Count));
end;
destructor TtdFileLCS.Destroy;
begin
{уничтожить матрицу}
FMatrix.Free;
{освободить списки строк}
FFromFile.Free;
FToFile.Free;
{уничтожить производный объект}
inherited Destroy;
end;
Однако нужно решить одну проблему: при работе со строками отсчет символов начинается с 1, а при работе со списком строк отсчет строк (строк в исходном файле) начинается с 0. Поэтому необходимо внести ряд изменений.
Первое изменение заключается в простом кодировании рекурсивного метода. Если помните, итеративный метод требовал предварительного выделения ячеек, расположенных вдоль верхней и левой сторон матрицы, и установки их значений равными 0, в то время как в рекурсивном методе для выполнения этой задачи использовался оператор If. Потенциально это позволяет сэкономить достаточно большой объем памяти (в общем случае текстовые файлы могут содержать несколько сотен или даже тысяч строк).
Второе изменение, как уже отмечалось, – отсчет строк с 0. Рекурсивная подпрограмма автоматически решает эту задачу.
Код реализации рекурсивного метода генерирования LCS для двух файлов приведен в листинге 12.28.
Листинг 12.28. Генерация LCS для пары файлов
function TtdFileLCS.slGetCell(aFromInx, aToInx : integer): integer;
var
LCSData : PtdLCSData;
NorthLen: integer;
WestLen : integer;
begin
if (aFromInx = -1) or (aToInx = -1) then
Result := 0
else begin
LCSData := FMatrix[aFromInx, aToInx];
if (LCSData <> nil) then
Result := LCSData^.ldLen
else begin
{создать новый элемент}
New(LCSData);
{если две текущие строки совпадают, необходимо увеличить значение счетчика относительно элемента, расположенное о к северо-западу от текущего, т.е. предшествующего элемента}
if (FFromFile[aFromInx] = FToFile [aToInx]) then begin
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;
end
{в противном случае текущие строки различны: необходимо использовать максимальный из элементов, расположенных к северу или западу (использование элемента, расположенного к западу, предпочтительнее)} else begin
NorthLen := slGetCell(aFromInx-1, aToInx);
WestLen := slGetCell(aFromInx, aToInx-1);
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev := ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить элемент в матрице}
FMatrix [ aFromInx, aToInx ] := LCSData;
{вернуть длину данного LCS}
Result := LCSData^.ldLen;
end;
end;
end;
Метод записи последовательности редактирования, которая обеспечивает преобразование первого файла во второй, не особенно изменился по сравнению с рассмотренным ранее, за исключением того, что выполняется запись строк, а не символов. Эта подпрограмма приведена в листинге 12.29.
Листинг 12.29. Запись последовательности редактирования для пары файлов
procedure TtdFileLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса меньше нуля, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = -1) and (aToInx = -1) then
Exit;
{если индекс строки From меньше нуля, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = -1) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToFile[aToInx]);
end
{если индекс строки To меньше нуля, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = -1) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth :
begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile [aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, 1 ', FFromFile[aFromInx]);
end;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(Ff FToFile[aToInx]);
end;
end;
end;
end;
procedure TtdFileLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange (F, pred(FFromFile.Count), pred(FToFile.Count)) finally
System.Close(F);
end;
end;
Резюме
В этой главе были рассмотрены три дополнительных алгоритма. Первые два предназначены для работы с многопоточными приложениями. Третий представляет собой весьма значимый, однако малоизвестный алгоритм поиска различий между двумя версиями файла.
Применительно к многопоточным приложениям, мы рассмотрели решение проблемы синхронизации потоков считывания-записи – алгоритма, который играет большую роль во множестве программ подобного рода. Применительно к проблеме использования потоков производителей-потребителей, мы рассмотрели алгоритм, который может применяться во многих ситуациях, когда большие объемы данных должны одновременно обрабатываться, причем различным образом.
Алгоритм определения наиболее длинной общей подпоследовательности (LCS) является более специализированным, но находит применение в системах управления исходным кодом, а также в качестве программ наподобие diff.
Эпилог
Если быть кратким, написание этой книги явилось интересным опытом (а также работой, попортившей немало кровушки).
В течение долгих лет я считал, что Delphi, Visual Basic, а теперь и Kylix, порождали, порождают и будут порождать программистов, которые не имеют ни малейшего представления об этом занятии. Да, они могут создавать приложения простым перетаскиванием, с использованием небольшого объема связующего кода и нескольких обработчиков событий. Тем не менее, любое приложение, достойное того, чтобы его создавать, требует определенного мастерства, опыта и теоретической подготовки, которые могут быть предоставлены традиционными компьютерными науками и программированием. Конечно, при создании программы можно немало напутать, и, тем не менее, программа таки будет работать. Однако различие будет столь же разительным, как и различие между яйцом, сваренным вкрутую, и яйцом Фаберже.
Должен признать, что вся моя теоретическая подготовка в компьютерной области была получена в результате самообразования. Я получил ученую степень по математике в Королевском колледже при Лондонском университете. Во время учебы мне довелось прослушать единственный курс по программированию – программированию на языке FORTRAN, программы которого, хранящиеся в виде колод перфокарт, были предвестниками сегодняшнего расцвета компьютерных технологий – но насколько я помню, не предпринималось никаких реальных попыток обучения студентов строгим компьютерным наукам. (В те времена не приходилось говорить и о немедленном получении результатов, столь привычном для современного программирования на ПК). Мне пришлось полюбить просматривать длинные листинги программ на языке, который не поддерживал ни локальных переменных, ни указателей. Тем не менее, это меня не остановило. Я начал исследовать и изучать все эти премудрости. Долгими часами я мучился, пытаясь усвоить язык MIX, разработанный Кнутом (Knuth), С и иже с ними. Я пытался извлечь практическую пользу из учебников, которые оставляли реализацию операции Delete в качестве упражнения 4.25. Смею заверить, что все это – совершенно чудесный способ изучения языка.
Готов поспорить, что если вам стали известны доступные возможности языка, с которым вы более всего знакомы, то вы будете знать, следует ли при решении следующей задачи использовать хеш-таблицу или отложить клавиатуру и вычертить блок-схему конечного автомата, или, быть может, создать еще один экземпляр объекта списка TList. Именно в этом и состоит главная цель данной книги -показать читателям, чего можно добиться, если известны доступные возможности. Основное назначение кода, приведенного в книге – его непосредственное использование. (Вам требуется вычислитель регулярных выражений? Тогда воспользуйтесь кодом, разработанным нами в главе 10. Добавьте модуль в список uses и -"лэтс гоу", то бишь, за дело.)
Предупреждаю, что эта книга далеко не исчерпывающая. Когда я планировал ее написание, мне пришлось опустить больше материала, чем я смог осветить ("А чего ж ты не рассмотрел B-деревья, Юлиан?"). Угу... Так уж получилось... Прочтите книгу, а затем двигайтесь дальше, и постарайтесь выяснить, что еще написано по той или иной теме.
Список литературы
Ниже приведен список литературы, которая использовалась при написании этой книги. Некоторые из указанных работ имеют исключительно большое значение – без них я не смог бы разобраться в некоторых алгоритмах и пояснить их читателям применительно к Delphi. Другие содержат лишь материалы по менее серьезным темам, освещенным в других книгах. Тем не менее, это сделано так, что, на мой взгляд, вопрос становится более понятным.
1. Abramowitz, Milton, and Irene A. Stegun. Handbook of Mathematical Functions. Dover Publications, Inc., 1964.
2. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and
Tools. Addison-Wesley, 1986.
3. Beck, Kent. Extreme Programming Explained. Addison-Wesley, 2000.
4. Binstock, Andrew, and John Rex. Practical Algorithms for Programmers. Addison-Wesley, 1995.
5. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, 1990.
6. Folk, Michael J., and Bill Zoellick. File Structures. 2nd Ed. Addison-Wesley, 1992.
7. Guibas L.J., and R. Sedgewick. "A dichromatic framework for balanced trees." Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978.
8. Jones, Douglas W. "Application of Splay Trees to Data Compression." Communications of the ACM, Vol. 31 (1988), pp. 996-1007.
9. Kane, Thomas S. The New Oxford Guide to Writing. Oxford University Press, 1988.
10. King, Stephen. On Writing. Scribner, 2000.
11. Knuth, Donald E. The Art of Computer Programming: Fundamental Algorithms. 3rd Ed. Addison-Wesley, 1997.
12. Knuth, Donald E. The Art of Computer Programming: Seminumerical Algorithms. 3rd Ed. Addison-Wesley, 1998.
13. Knuth, Donald E. The Art of Computer Programming: Sorting and Searching. 2nd Ed. Addison-Wesley, 1998.
14. L"Ecuyer, Pierre. "Efficient and Portable Combined Random Number Generators." Communications of the ACM, Vol. 31 (1988), pp. 742-749, 774.
15. Nelson, Mark. The Data Compression Book. M& T Publishing, 1991.
16. Park, S.K., and K.W. Miller. "Random Number Generators: Good Ones are Hard to Find." Communications of the ACM, vol. 31 (1988), pp. 1192-1201.
17. Pham, Thuan Q. and Pankaj K. Garg. Multithreaded Programming with Win32. Prentice Hall, 1999.
18. Pugh, William. "Skip Lists: A Probabilistic AItemative to Balanced Trees." Communications of the ACM, Vol. 33 (1990), pp. 668-676.
19. Robbins, John. Debugging Applications. Microsoft Press, 2000.
20. Sedgewick, Robert. Algorithms. 2nd Ed. Addison-Wesley, 1988.
21. Sedgewick, Robert. Algorithms in C. 3rd Ed. Addison-Wesley, 1998.
22. Sleator, D.D., and R.E. Tarjan. "Self-adjusting binary search trees." Journal of the ACM (1985).
23. Thorpe, Danny. Delphi Component Design. Addison-Wesley Developers Press, 1996.
24. Wood, Derick. Data Structures, Algorithms, and Performance. Addison-Wesley, 1993.
25. Sedgewick, Robert. Algorithms in С++. Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. 3rd Ed. Addison-Wesley, 1999.
26. Sedgewick, Robert. Algorithms in С++. Parts 5: Graph Algorithms. 3rd Ed. Addison-Wesley, 2002.
27. Роберт Седжвик. Фундаментальные алгоритмы на С++. Части 1-4: Анализ/Структуры данных/Сортировка/Поиск. – К.: Издательство ДиаСофт?, 2001.
28. Роберт Седжвик. Фундаментальные алгоритмы на С++. Часть 5: Алгоритмы на графах. – К.: Издательство ДиаСофт?, 2002.
29. Роберт Седжвик. Фундаментальные алгоритмы на С. Части 1-4: Анализ/Структуры данных/Сортировка/Поиск. – К.: Издательство ДиаСофт?, 2003.
30. Роберт Седжвик. Фундаментальные алгоритмы на С Часть 5: Алгоритмы на графах. – К.: Издательство ДиаСофт?, 2003.
31. Джон Макгрегор, Девид Сайке. Тестирование объектно-ориентированного программного обеспечения. Практическое пособие. – К.: Издательство ДиаСофт?, 2002.
