Seltsame Geschwindigkeitsverteilung

[3_of_8]

Morgen. Ich habe gerade einen array-basierten Min-Heap implementiert.

Um die Geschwindigkeit festzustellen habe ich dann per Code 1000000 Zufallswerte berechnen lassen, jeweils in eine Klasse gewrappt in einem Array gespeichert und dann in den Heap gepusht und anschließend gepoppt. Beim Pushen und Poppen habe ich jeweils mit QPC die Zeit gemessen.

Das Pushen dauert etwa 200ms, das Poppen 4400ms.

Jetzt frage ich mich, warum? Beim Poppen wird ja eigentlich sogar weniger getan als beim Pushen. Es wird kein Speicher reserviert und in Heapify muss der Knoten auch nicht erst nach oben wandern, weil er ja sowieso die Wurzel ist.

Woher also kommt dieser enorme Unterschied?

Delphi-Quellcode:

unit TOEHeap;

interface

const
  INITIALHEAPSIZE = 255;

type
  TTOEComparable = class
  public
    function IsLowerThan(const Obj: TTOEComparable): Boolean; virtual; abstract;
  end;

  TTOEHeap = class
  private
    FNodes: array of TTOEComparable;
    FNext: Integer;

    function GetFather(const Node: Integer): Integer; inline;
    function GetLChild(const Node: Integer): Integer; inline;
    function GetRChild(const Node: Integer): Integer; inline;
    function NodeExists(const Node: Integer): Boolean; inline;
    
    procedure ExtendArray; inline;
    procedure Heapify(Node: Integer);
    procedure SwapNodes(const Node1, Node2: Integer); inline;

  public
    shifts: integer;

    constructor Create(const Size: Integer = INITIALHEAPSIZE); reintroduce;
    destructor Destroy; override;

    procedure Push(const Obj: TTOEComparable);
    function Peek: TTOEComparable;
    function Pop: TTOEComparable;
    procedure Delete(const Node: Integer);

    procedure Reorder;

    function IsEmpty: Boolean;
    procedure Clear;
  end;

implementation

{ TTOEHeap }

constructor TTOEHeap.Create(const Size: Integer=INITIALHEAPSIZE);
begin
  setlength(FNodes, Size);
end;

procedure TTOEHeap.Delete(const Node: Integer);
begin
  dec(FNext);
  if Node<FNext then
    FNodes[Node]:=FNodes[FNext];
  FNodes[FNext]:=nil;
  Heapify(Node);
end;

destructor TTOEHeap.Destroy;
begin
  Clear;
  inherited Destroy;
end;

procedure TTOEHeap.ExtendArray;
begin
  setlength(FNodes, 2*(length(FNodes)+1)-1);
end;

function TTOEHeap.GetFather(const Node: Integer): Integer;
begin
  Result:=(Node - 1) shr 1;
end;

function TTOEHeap.GetLChild(const Node: Integer): Integer;
begin
  Result:=(Node shl 1) + 1;
end;

function TTOEHeap.GetRChild(const Node: Integer): Integer;
begin
  Result:=(Node shl 1) + 2;
end;

procedure TTOEHeap.SwapNodes(const Node1, Node2: Integer);
var tmpobj: TTOEComparable;
begin
  tmpobj:=FNodes[Node1];
  FNodes[Node1]:=FNodes[Node2];
  FNodes[Node2]:=tmpobj;
end;

procedure TTOEHeap.Heapify(Node: Integer);
var father, lchild, rchild: Integer;
    nodenode, lchildnode, rchildnode: TTOEComparable;
begin

  if not NodeExists(Node) then exit;

  father:=GetFather(Node);

  while (Node>0) and (FNodes[Node].IsLowerThan(FNodes[father])) do
  begin
    SwapNodes(Node, father);
    Node:=father;
    father:=GetFather(Node);
    inc(shifts);
  end;

  lchild:=GetLChild(Node);
  rchild:=GetRChild(Node);

  if not (NodeExists(lchild) or NodeExists(rchild)) then exit;

  repeat

    lchildnode:=FNodes[lchild];
    rchildnode:=FNodes[rchild];
    nodenode:=FNodes[Node];

    if NodeExists(lchild) and lchildnode.IsLowerThan(nodenode) and
      (not NodeExists(rchild) or lchildnode.IsLowerThan(rchildnode)) then
    begin
      SwapNodes(Node, lchild);
      Node:=lchild;
      inc(shifts);
    end
    else if NodeExists(rchild) and rchildnode.IsLowerThan(nodenode) then
    begin
      SwapNodes(Node, rchild);
      Node:=rchild;
      inc(shifts);
    end
    else exit;

    lchild:=GetLChild(Node);
    rchild:=GetRChild(Node);

  until not (NodeExists(lchild) or NodeExists(rchild));

end;

function TTOEHeap.Peek: TTOEComparable;
begin
  Result:=FNodes[0];
end;

function TTOEHeap.Pop: TTOEComparable;
begin
  Result:=FNodes[0];
  if not IsEmpty then
    Delete(0);
end;

procedure TTOEHeap.Push(const Obj: TTOEComparable);
begin

  if FNext>=length(FNodes) then
    ExtendArray;

  FNodes[FNext]:=Obj;
  Heapify(FNext);

  inc(FNext);
end;

procedure TTOEHeap.Reorder;
var
  I: Integer;
begin
  for I:=0 to high(FNodes) do
    Heapify(I);
end;

function TTOEHeap.IsEmpty: Boolean;
begin
  Result:=FNext=0;
end;

function TTOEHeap.NodeExists(const Node: Integer): Boolean;
begin
  Result:=(Node<length(FNodes)) and assigned(FNodes[Node])
end;

procedure TTOEHeap.Clear;
begin
  FNodes[0]:=nil;
  FNext:=0;
end;

end.