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

После того, как мы убедились в простоте разработки создания этой очереди по приоритету, рассмотрим ее эффективность. Во-первых, добавление элемента в очередь по приоритету будет требовать постоянного времени. Иначе говоря, эта операция является операцией типа O(1). Независимо от того, содержит ли очередь ноль или тысячи элементов, добавление нового элемента будет занимать приблизительно одно и то же время: мы всего лишь дописываем его в конец списка.

Теперь рассмотрим противоположную операцию: удаление элемента. В этом случае для отыскания элемента с наивысшим приоритетом потребуется выполнить считывание всех элементов в структуре TList. Этот поиск является последовательным и, как было показано в главе 4, эта операция является операцией типа O(n). Требуемое для этого время пропорционально количеству элементов в очереди.

Таким образом, мы разработали и создали структуру данных, реализующую очередь по приоритету, в которой добавление элемента является операцией типа O(1), а удаление - операцией типа O(n). При наличии небольшого количества элементов эта структура оказывается вполне приемлемой и достаточно эффективной.

Вторая простая реализация

Однако при наличии большого количества элементов или при добавлении и удалении из очереди большого количества элементов она оказывается не столь эффективной, как хотелось бы. Уверен, что читатели сразу подумали об одном возможном способе повышения эффективности: поддержании структуры TList в порядке приоритетов. Иначе говоря, о поддержании ее в отсортированном виде в ходе всех добавлений. По существу, это усовершенствование означает перенос реальной задачи поддержания очереди из операции удаления элемента в операцию вставки элемента. При добавлении элемента необходимо найти для него правильную позицию внутри структуры TList после всех элементов с более низким приоритетом и перед всеми элементами с более высоким приоритетом. В случае выполнения этой дополнительной задачи на этапе добавления все элементы структуры TList будут размещены в порядке своих приоритетов и, следовательно, при удалении элемента потребуется всего лишь удалить последний элемент структуры. Фактически, при этом удаление превращается в операцию типа O(1) (нам точно известно, где расположен элемент с наивысшим приоритетом - он находится в конце очереди, поэтому удаление не зависит от количества элементов).

Вычисление времени, которое требуется для вставки в этот отсортированный список TList, несколько сложнее. Этот процесс проще всего представить сортировкой простыми вставками (которая была описана в главе 5). Мы увеличиваем размер TList на один элемент, а затем, подобно четкам, по одному перемещаем элементы на свободное место, начиная с конца структуры TList. Процесс прекращается по достижении элемента, приоритет которого ниже приоритета элемента, который мы пытаемся вставить. В результате в структуре TList образуется "пробел", в который можно поместить новый элемент. В структуре TList, содержащей n элементов, в среднем придется переместить nil элементов. Следовательно, вставка является операцией типа O(n) (т.е. требуемое для ее выполнения время снова пропорционально количеству элементов в очереди), хотя это усовершенствование позволяет несколько уменьшить время выполнения операции по сравнению с предыдущей реализацией. Пример кода выполнения этих двух операций в описанной структуре данных приведен в листинге 9.2.

Листинг 9.2. Очередь по приоритету, в которой используется отсортированная структура данных TList

type

TtdSimplePriQueue2 = class private

FCompare : TtdCompareFunc;

FList : TList;

protected

function pqGetCount : integer;

public

constructor Create(aCompare : TtdCompareFunc);

destructor Destroy; override;

function Dequeue : pointer;

procedure Enqueue(aItem : pointer);

property Count : integer read pqGetCount;

end;

constructor TtdSimplePriQueue2.Create(aCompare : TtdCompareFunc);

begin

inherited Create;

FCompare := aCompare;

FList := TList.Create;

end;

destructor TtdSimplePriQueue2.Destroy;

begin

FList.Free;

inherited Destroy;

end;

function TtdSimplePriQueue2.Dequeue : pointer;

begin

Result := FList.Last;

FList.Count := FList.Count - 1;

end;

procedure TtdSimplePriQueue2.Enqueue(aItem : pointer);

var

Inx : integer;

begin

{увеличить количество элементов в списке}

FList.Count := FList.Count + 1;

{определить место помещения нового элемента}

Inx := FList.Count -2;

while (Inx>= 0) and (FCompare(FList.List^ [Inx], aItem) > 0) do

begin

FList.List^[Inx+ 1] := FList.List^[Inx];

dec(Inx);

end;

{поместить элемент в эту позицию}

FList.List^[Inx+1] := aItem

end;

function TtdSimplePriQueue2.pqGetCount : integer;

begin

Result := FList.Count;

end;

Исходный код класса TtdSimplePriQueue2 можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDPriQue.pas.

В ходе разработки и создания этой усовершенствованной очереди по приоритету мы перешли от быстрой вставки/медленного удаления к медленной вставке/быстрому удалению. Нельзя ли воспользоваться более эффективным алгоритмом?