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

Вычисление времени, которое требуется для вставки в этот отсортированный список TList, несколько сложнее. Этот процесс проще всего представить сортировкой простыми вставками (которая была описана в главе 5). Мы увеличиваем размер TList на один элемент, а затем, подобно четкам, по одному перемещаем элементы на свободное место, начиная с конца структуры TList. Процесс прекращается по достижении элемента, приоритет которого ниже приоритета элемента, который мы пытаемся вставить. В результате в структуре TList образуется "пробел", в который можно поместить новый элемент. В структуре TList, содержащей п элементов, в среднем придется переместить nil элементов. Следовательно, вставка является операцией типа О(я) (т.е. требуемое для ее выполнения время снова пропорционально количеству элементов в очереди), хотя это усовершенствование позволяет несколько уменьшить время выполнения операции по сравнению с предыдущей реализацией. Пример кода выполнения этих двух операций в описанной структуре данных приведен в листинге 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 (altem : 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 : pointers-begin
Result := FList.Last;
FList.Count := FList.Count - 1;
end;
procedure TtdSimplePriQueue2.Enqueue(altem : pointer); var
Inx : integer;
begin
{увеличить количество элементов в списке} FList.Count : = FList.Count + 1; {определить место помещения нового элемента} Inx := FList.Count -2;
while (Inx>= 0) and (FCompare(FList .ListA [Inx], altem) > 0) do begin
FList.ListA[Inx+l] := FList.ListA[Inx];
dec(Inx);
end;
{поместить элемент в эту позицию} FList.ListА[Inx+1] : = al teilend;
function TtdSimplePriQueue2 .pqGetCount : integers-begin
Result : = FList.Count;
end;

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

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

Еще одна возможность предполагает полный отказ от использования структуры TList и переход к другой структуре данных: дереву двоичного поиска, описанному в главе 8, или списку с пропусками, описанному в главе 6. При использовании обеих этих структур данных и вставка и удаление являются операциями типа 0(log(«)). Иначе говоря, время, требуемое как для вставки, так и для удаления элемента, пропорционально логарифму числа элементов в структуре. Однако применение обеих этих структур данных сопряжено с некоторыми сложностями. В отношении списка с пропусками это связано с его вероятностной структурой, а в отношении дерева двоичного поиска - потому, что в ходе вставки и удаления необходимо заботиться о балансировке результирующего дерева. Существует ли какая-то более простая структура данных?

Первая простая реализация || Оглавление || Сортирующее дерево


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



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс