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.

[mkinzler]

Was machst du alles in .Delete()?

[peschai]

@mkinzler: Zeile52 in seinem Beispiel ? ...

[Noobinator]

wenn ich da jetzt richtig durchgeblickt habe:

beim pop gibst du den ersten Knoten zurück,

  Result:=FNodes[0]; wirfst wenn vorhanden den ersten Knoten weg

Delphi-Quellcode:

  if not IsEmpty then
    Delete(0);

und stellst dann in der Delete Methode wieder Heap Eigenschaften herstellen, indem du neu sortierst.

--> du benutzt ein Dynamisches Array.
und das ist dein Zeitfresser.

--> bei jeder Änderung wird die SAF (Speicherabbildungsfunktion) des Arrays aufgerufen, was ja bei einem
1000000 Array ne ganz schöne Menge ist.

so würde ich mir das jetzt mal erklären.

Mach das ganze doch Listenbasiert

[3_of_8]

Speicherabbildungsfunktion? Was meinst du damit? Den Array-Zugriff?

mov esi, [edx+eax*4] So realisiert das der Compiler, also wohl kaum der Flaschenhals bei dem Code. Listen sind schlecht geeignet, erstens weil sie keinen Random-Access haben, den ich für diesen Heap brauche, um effizient arbeiten zu können und zweitens weil sie doppelt so viel Speicher benötigen.

Außerdem steigt die Anzahl der Array-Zugriffe nur logarithmisch.

[Noobinator]

Zugriff auf ein Element:

wie du richtig geschrieben hast ist

a[i] = A0 + i * Sizeof(element)

und genau das bricht dir das Genick.
Diese Berechnung wird bei jedem Zugriff ausgeführt.
Wobei er sich über den Pointer erst den Anfangsblock des Arrays hohlen muss,
und dann noch den Speicherplatz je Element.

Jedenfalls haben wir das so in der Schule gelernt.

Belehrt mich eines Besseren wenn ich Falsch liege.

[3_of_8]

Ist das dein Ernst? Eine Addition, ein Linksshift, zwei Moves. Das schafft ein halbwegs aktueller Prozessor in 4 Takten (solange kein Cache-Miss auftritt).

Aber selbst wenn, genau das wird beim Pushen auch ausgeführt, und da dauert es nur 1/20 mal so lange.

[JasonDX]

Das Verschieben des Knotens nach oben - das was du dir beim Pop ersparst - dauert nicht lange. Aber nachdem beim Pop immer der letzte Knoten, was va. Anfangs einer der Größeren ist, nach oben gelegt wird, muss dieser auch meist ganz nach unten geschoben werden. Das heißt, dass vor allem der zweite Teil von Heapify Zeit kosten wird, und bei einem Pop die While-Schleife relativ oft ausgeführt wird. Ich denke, dass da das Problem liegt. Genauer auf dem Grund gehn kannst du dem, indem du prüfst, wieviel Zeit bei welchem Teil (Nach oben, nach unten verschieben) von Heapify bei welcher Operation (Push, Delete) verbraucht wird.

greetz
Mike

[3_of_8]

So genau kann ich aber nie und nimmer messen, das ist das Problem...

[JasonDX]

Zitat von 3_of_8:

So genau kann ich aber nie und nimmer messen, das ist das Problem...

Dann kannst du anstelle einer Zeitmessung einfach mitzählen, wie oft nach unten (evt. auch zwischen links und rechts auch unterscheiden), und wie oft nach oben verschoben wird. Das gibt dir auch einen Anhaltspunkt.

greetz
Mike