warum ist das Programm so langsam?

[Noobinator]

Hy Community
Wir sollten in der Schule Heapsort Programmieren, und das Hier ist nun Mein Programm.

Delphi-Quellcode:

procedure genheap(f:ftype;Heap:integer);
var i,temp,j,k:integer;
begin
for k:=1 to Heap div 2 do
begin
  for i:=1 to Heap div 2 do
    begin
       if (f[i]<f[i*2]) then
          begin
            temp:=f[i];
            f[i]:=f[i*2];
            f[i*2]:=temp;
          end;
       if (f[i]<f[i*2+1]) and (i*2+1<Heap)then
          begin
            temp:=f[i];
            f[i]:=f[i*2+1];
            f[i*2+1]:=temp;
          end;
    end;
end;
end;

procedure heapsort(f:ftype;n:integer);
var i:integer;
begin
if n>0 then
begin
  genheap(myarray,n);
  for i:=1 to n do
    myarray[i-1]:=myarray[i];
  myarray[n]:=myarray[0];
  heapsort(myarray,n-1);
end;
end;

Nun läuft mein Programm extrem Langsam, und ich weiss nicht warum.
Bei anderen Dauert das sortieren von 4000 Werten ca 0,6 Sekunden, und bei mir ganze 35 s

Woran kann das liegen? wir arbeiten in der Schule alle an Gleichen Rechnen, sodass das wegfällt.
Was könnte ich noch optimieren? wo habe ich Fatale geschwindigkeitsbremsen eingebaut?

Danke schonmal

[Luckie]

Eine fällt mir hier auf:

Delphi-Quellcode:

setlength(myarray,i+1);

Ändert man die Größe eines dynamischen Arrays, wird für die neue Größe (Alt + Anzahl neue Elemente) neuer Speicherreserviert. dann wird der Inhalt des alten Arrays dorthin kopiert. Das ist erstmal zeitraubend und zum zweiten ein Speichrfresser, da der alte Speicher nicht wieder freigegeben wird. Damit defragemntiert auch der Speicher sehr stark.

Schätz am Anfang, wie groß das Array ungefähr sein muss und wenn es nicht mehr raicht, vergrößerst du es gleich um 30% dr ursprünglichen größe, so dass du es nicht in jedem Schleifendurchgang vergrößern musst.

Es können noch weitere Bremsen im Code, sein, aber die sind mir so auf die Schnelle nicht aufgefallen.

[Noobinator]

Zitat:

Zitat von Luckie

Eine fällt mir hier auf:

Delphi-Quellcode:

setlength(myarray,i+1);

Ändert man die Größe eines dynamischen Arrays, wird für die neue Größe (Alt + Anzahl neue Elemente) neuer Speicherreserviert. dann wird der Inhalt des alten Arrays dorthin kopiert. Das ist erstmal zeitraubend und zum zweiten ein Speichrfresser, da der alte Speicher nicht wieder freigegeben wird. Damit defragemntiert auch der Speicher sehr stark.

Schätz am Anfang, wie groß das Array ungefähr sein muss und wenn es nicht mehr raicht, vergrößerst du es gleich um 30% dr ursprünglichen größe, so dass du es nicht in jedem Schleifendurchgang vergrößern musst.

Es können noch weitere Bremsen im Code, sein, aber die sind mir so auf die Schnelle nicht aufgefallen.

Danke für den Tipp, aber diese Zeit messe ich ja garnicht mit.
Ich messe nur die Zeit des Sortierens.
habe auch nochmal Editiert oben.

Es muss innerhalb dieser zwei Proceduren sein.

[Robert Marquardt]

Das Problem ist das die Fuktion zwar heapsort heisst aber nicht heap sort macht.
Hier mal eine Unit die bei mir rumliegt:

Delphi-Quellcode:

unit heapsort;

interface

procedure HeapSort(var A: array of PChar; Len: Integer);

implementation

procedure HeapSort(var A: array of PChar; Len: Integer);
var
  I: Integer;

  procedure Swap(var X, Y: PChar);
  var
    Swp: PChar;
  begin
    Swp := X;
    X := Y;
    Y := Swp;
  end;

  function Comp(const A, B: PChar): Boolean;
  var
    I: Integer;
  begin
    for I := 0 to Len - 1 do
      if A[I] <> B[I] then
      begin
        Result := Byte(A[I]) > Byte(B[I]);
        Exit;
      end;
    Result := False;
  end;

  procedure SiftDown(Current, MaxIndex: Integer);
  var
    Left, Right, Largest: Integer;
  begin
    Left := Low(A) + (2 * (Current - Low(A))) + 1;
    Right := Low(A) + (2 * (Current - Low(A))) + 2;
    Largest := Current;
    if (Left <= MaxIndex) and Comp(A[Left], A[Largest]) then
      Largest := Left;
    if (Right <= MaxIndex) and Comp(A[Right], A[Largest]) then
      Largest := Right;
    if Largest <> Current then
    begin
      Swap(A[Current], A[Largest]);
      SiftDown(Largest, MaxIndex);
    end;
  end;

  procedure Heapify;
  var
    Middle: Integer;
    I: Integer;
  begin
    Middle := ((Low(A) + High(A) + 1) div 2) - 1;
    for I := Middle downto Low(A) do // Nur die Knoten, die Söhne haben!
      SiftDown(I, High(A));
  end;

begin
  Heapify;
  for I := High(A) downto Low(A) + 1 do
  begin
    Swap(A[I], A[Low(A)]);
    SiftDown(Low(A), I - 1);
  end;
end;

end.

[MrKnogge]

Zitat:

Zitat von Luckie

[...]Ändert man die Größe eines dynamischen Arrays, wird für die neue Größe (Alt + Anzahl neue Elemente) neuer Speicherreserviert. dann wird der Inhalt des alten Arrays dorthin kopiert. Das ist erstmal zeitraubend und zum zweiten ein Speichrfresser, da der alte Speicher nicht wieder freigegeben wird. [...]

:shock:
Kann man diesen Speicher irgendwie manuel freigeben ?

Gruß

[Noobinator]

Zitat:

Zitat von Robert Marquardt

Das Problem ist das die Fuktion zwar heapsort heisst aber nicht heap sort macht.
Hier mal eine Unit die bei mir rumliegt:

Also diese Unit macht Heapsort ;)
da bin ich mir sehr sehr sicher.
Jedenfalls habe ich das Modell von Heapsort in der Schule vorgestellt als Schülervortrag, und da hätte mein Lehrer schon was gesagt, wenn es nicht stimmen würde.

Du nimmst ja immer den Vater (i in meinem Code) und wenn der kleiner ist als die Söhne (i*2 und i*2+1) dann wird getauscht.
So hast du am Ende ein sortieren Baum (Heap) von dem Du die Wurzel rausschmeißt, und die anderen Glieder wieder zu einem Heap machst,und das so lange, bis du durch bist.