Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

• Название: Фундаментальные алгоритмы и структуры данных в Delphi
• Автор: Джулиан Бакнелл
• Издательство: ДиаСофтЮП
• Жанр: Программирование
• Год: 2003
• ISBN: ISBN 5-93772-087-3

Книга "Фундаментальные алгоритмы и структуры данных в Delphi" представляет собой уникальное учебное и справочное пособие по наиболее распространенным алгоритмам манипулирования данными, которые зарекомендовали себя как надежные и проверенные многими поколениями программистов. По данным журнала "Delphi Informant" за 2002 год, эта книга была признана сообществом разработчиков прикладных приложений на Delphi как «самая лучшая книга по практическому применению всех версий Delphi».

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

Несмотря на то что книга рассчитана в первую очередь на профессиональных разработчиков приложений на Delphi, она окажет несомненную пользу и начинающим программистам, демонстрируя им приемы и трюки, которые столь популярны у истинных «профи». Все коды примеров, упомянутые в книге, доступны для выгрузки на Web-сайте издательства.

---

FSyncObj.StopProducing;

until (Tail^.bCount ? 0);

end;

type

TConsumer = class(TThread) private

FBuffers : TQueuedBuffers;

FStream : TStream;

FSyncObj : TtdProduceConsumeSync;

protected

procedure Execute; override;

public

constructor Create(aStream : TStream;

aSyncObj : TtdProduceConsumeSync;

aBuffers : TQueuedBuffers);

end;

constructor TConsumer.Create(aStream : TStream;

aSyncObj : TtdProduceConsumeSync;

aBuffers : TQueuedBuffers);

begin

inherited Create (true);

FStream := aStream;

FSyncObj := aSyncObj;

FBuffers := aBuffers;

end;

procedure TConsumer.Execute;

var

Head : PBuffer;

begin

{сигнализировать о готовности к началу потребления данных}

FSyncObj.StartConsuming;

{извлечь начальный буфер}

Head := FBuffers.Head;

{до тех пор, пока начальный буфер не опустошен...}

while (Head^.bCount <> 0) do

begin

{выполнить запись блока из начального буфера в поток}

FStream.Write(Head^.bBlock, Head^.bCount);

{переместить указатель начала очереди}

FBuffers.AdvanceHead;

{поскольку было выполнено считывание и обработка буфера, необходимо сообщить о том, что данные были использованы}

FSyncObj.StopConsuming;

{сигнализировать о готовности снова приступить к потреблению данных}

FSyncObj.StartConsuming;

{извлечь начальный буфер}

Head := FBuffers.Head;

end;

end;

И, наконец, мы можем рассмотреть подпрограмму копирования потока, приведенную в листинге 12.14. Она принимает два параметра: входной поток и выходной поток. Подпрограмма создает специальный объект типа TQueuedBuffers. Этот объект содержит все ресурсы и методы, необходимые для реализации организованного в виде очереди набора буферов. Он создает также экземпляр класса TtdProducerConsumerSync, который будет действовать в качестве объекта синхронизации, обеспечивающего согласованную работу производителя и потребителя.

Листинг 12.14. Многопоточное копирование

procedure ThreadedCopyStream(aSrcStream, aDestStream : TStream);

var

SyncObj : TtdProduceConsumeSync;

Buffers : TQueuedBuffers;

Producer : TProducer;

Consumer : TConsumer;

WaitArray : array [ 0..1] of THandle;

begin

SyncObj := nil;

Buffers := nil;

Producer :=nil;

Consumer :=nil;

try

{создать объект синхронизации, объект организованных в виде очереди буферов (с 20 буферами) и два потока}

SyncObj := TtdProduceConsumeSync.Create(20);

Buffers := TQueuedBuffers.Create(20);

Producer := TProducer.Create(aSrcStream, SyncObj, Buffers);

Consumer := TConsumer.Create(aDestStream, SyncObj, Buffers);

{сохранить дескрипторы потоков, что обеспечивает возможность ожидания их передачи}

WaitArray[0] := Producer.Handle;

WaitArray[1] := Consumer.Handle;

{запустить потоки}

Consumer.Resume;

Producer.Resume;

{ожидать окончания потоков}

WaitForMultipleObjects(2, @WaitArray, true, INFINITE);

finally

Producer.Free;

Consumer.Free;

Buffers.Free;

SyncObj.Free;

end;

end;

Затем подпрограмма копирования создает два потока, между которыми будет выполняться копирование, и возобновляет их выполнение (потоки создаются в приостановленном состоянии). Далее подпрограмма дожидается завершения обоих потоков и выполняет очистку. Полный код подпрограммы можно найти в файлах TstCopy.dpr и TstCopyu.pas на web-сайте издательства, в разделе материалов.

Модель с одним производителем и несколькими потребителями

Реализовать рассмотренное приложение, в котором используется модель "производитель-потребитель", было достаточно просто. Теперь рассмотрим модель с одним производителем и несколькими потребителями. В этом случае имеется поток, который создает данные. Предположим, что существует несколько потоков, которым требуется считывать созданные данные. В упомянутом ранее примере использовались два потребителя, которые сжимали данные с применением разных алгоритмов. Еще одним примером мог бы служить браузер. Будем считать, что производитель выгружает web-страницу из удаленного сайта, а один потребитель считывает HTML-код, чтобы выполнить его сохранение на диске, второй считывает код для его отображения на экране, а третий - с целью отображения индикатора выполнения. Создание этих процессов как отдельных потребителей упрощает написание кода, поскольку каждый процесс должен выполнять только одну задачу.

Итак, что же требуется, чтобы объект синхронизации поддерживал согласованную работу производителя и потребителей? Во-первых, производитель должен сообщать всем потребителям о наличии данных для считывания. Предположительно скорости работы потребителей будут различными, и поэтому они будут обрабатывать данные с различной частотой. Это предполагает существование по одному семафору "имеются данные" на каждый потребитель. Будем считать, что существует список буферов, которые производитель должен пополнять данными. И более того, этот список организован в виде циклической очереди. Следовательно, нам нужен единственный указатель конца очереди (управляемый исключительно производителем) и по одному указателю начала очереди для каждого потребителя, поскольку, по всей вероятности, каждый потребитель будет считывать буфера с различной частотой.

Так как же быть с производителем? Каким образом он узнает, что можно снова заполнять буфер данных? Понятно, что он может это делать только после того, как последний (предположительно самый медленный) потребитель прочитал достаточный объем данных, чтобы появилось место для его заполнения новыми данными (иначе говоря, как только буфер снова освободится). Это, в свою очередь, предполагает, что должен существовать счетчик потребителей для каждого буфера данных. Каждый раз, когда потребитель считывает данные из буфера, он уменьшает значение этого счетчика (число потребителей, которым еще только предстоит выполнить считывание данных из этого буфера). Таким образом, когда последний потребитель приступает к использованию каких-либо данных, известно, что он является последним, поскольку после уменьшения значение счетчика должно быть равно нулю. Обратите внимание, что потребители являются потоками и, следовательно, уменьшение значения счетчика следует выполнять безопасным для потоков образом.

Код этого расширенного класса TtdProduceManyConsumeSync, который позволяет нескольким потребителям потреблять данные, сгенерированные единственным производителем, приведен в листинге 12.15. Предполагается, что каждый поток потребителя имеет уникальный, начинающийся с нуля, идентификатор (на практике этого легко добиться, но при необходимости класс можно было бы расширить, чтобы потребители могли регистрироваться и отменять свою регистрацию, и чтобы идентификаторы присваивались им "на лету"). Затем потребитель использует этот идентификатор (числовое значение) при обращении к методам StartConsumer и StopConsumer.

Листинг 12.15. Класс синхронизации одного производителя и нескольких потребителей

В этом классе предполагается, что производитель заполняет буфера, которые затем используются потребителями. Буфера не имеют никакой реальной реализации в самом классе. Их предоставление - задача пользователя класса.

Метод StartProducing, показанный в листинге 12.16, работает во многом аналогично описанному в предыдущем случае: он просто дожидается передачи ему семафора "требуются данные". (Этот семафор содержит значение, равное количеству буферов, что позволяет производителю заполнить все буфера.)

type

TtdProduceManyConsumeSync = class private

FBufferCount : integer;

{счетчик буферов данных}

FBufferInfo : TList;

{циклическая очередь информации о буферах}

FBufferTail : integer;

{конец циклической очереди буферов}

FConsumerCount : integer;

{счетчик потребителей}

FConsumerInfo : TList;

{информация для каждого потребителя}

FNeedsData : THandle;

{семафор}

protected

public

constructor Create(aBufferCount : integer;

aConsumerCount : integer);

destructor Destroy; override;

procedure StartConsuming(aid : integer);

procedure StartProducing;

procedure StopConsuming(aid : integer);

procedure StopProducing;

end;

Метод StopProducing, также показанный в листинге 12.16, на этот раз должен выполнить несколько больший объем работы. Во-первых, счетчик использования потребителей только что заполненного им буфера должен быть установлен равным количеству потребителей. Обратите внимание, что поток производителя должен передавать все семафоры "имеются данные" (по одному для каждого потребителя), тем самым сообщая о наличии еще одного буфера, готового к использованию.

Листинг 12.16. Методы StartProducing и StopProducing

type

PBufferInfo = ^TBufferInfo;

TBufferInfo = packed record

biToUseCount : integer;

{счетчик потребителей, которым еще предстоит использовать буфер}

end;

type

PConsumerInfo = ^TConsumerInfo;

TConsumerInfo = packed record ciHasData : THandle;

{семафор}

ciHead : integer;

{указатель на начало очереди}

end;

procedure TtdProduceManyConsumeSync.StartProducing;

begin

{чтобы можно было начать генерацию данных, необходимо передать семафор "требуются данные"}

WaitForSingleObject(FNeedsData, INFINITE);

end;

procedure TtdProduceManyConsumeSync.StopProducing;

var

i : integer;

BufInfo : PBufferInfo;

ConsumerInfo : PConsumerInfo;

begin

{в случае генерации каких-либо дополнительных данных необходимо установить счетчик потребителей буфера в конце очереди, чтобы тем самым обеспечить правильную обработку всех буферов}

BufInfo := PBufferInfo(FBufferInfo[FBufferTail]);

BufInfo^.biToUseCount := FConsumerCount;

inc(FBufferTail);

if (FBufferTail >= FBufferCount) then