Autor Beitrag
fiore
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Mi 09.09.09 14:00 
Hallo!

Ich habe gerade in Delphi einen Fibonacci-Heap implementiert um mit dem Dijkstra-Algorithmus kürzeste Wege in Graphen schnell finden zu können. Allerdings habe ich das Problem, dass bei mehrmaligem Aufruf des Dijkstra-Algorithmus, und damit dem mehrfachen Auf- und Abbbau eines Fib-Heaps, mein Speicher extrem zugemüllt wird. Meine Versuche das Problem mit Dispose in den Griff zu kriegen haben bisher noch zu keinem Ergebnis geführt. Deshalb habe ich mich ein bisschen gelesen und bin auf folgendes Problem gestoßen:

Wofür ist der ^-Operator eigentlich genau da? Naiv wie ich war, habe ich meinen gesamten Fib-Heap nämlich ohne den ^-Operator aufgebaut und das funktioniert auch alles ohne Probleme. Allerdings habe ich die Vermutung, dass deshalb mein Dispose nicht ordentlich funktioniert. Liege ich mit der Vermutung richtig und wenn ja, an welchen Stellen muss ich den ^-Operator nehmen und an welchen nicht?

Vielen Dank!
fiore

PS: Bei Bedarf kann ich auch Quellcode-Schnipsel anhängen.
HelgeLange
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 735
Erhaltene Danke: 6

Windows 7
Delphi7 - Delphi XE
BeitragVerfasst: Mi 09.09.09 14:22 
Stell es Dir mit Pointer so vor : Ein Pointer zeigt auf die Hausadresse während Du noch am Bahnhof bist. Der ^-Operator ist das Taxi, das Dich vor dem Haus absetzt :)

Bsp in Delphi :

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
type RMeinRecord = packed record
       String1 : String;
       String2 : String;
       Integer1 : Integer;
     end;
     PMeinRecord = ^RMeinRecord;

procedure XYZ;
var pData : PMeinRecord;   // hoffe, es fällt auf, dass ich die P-variante nehme
begin
  New(pData);
  pData.String1 := 'Hallo';   // das ist FALSCH. pData ist nur der Zeiger zur Adresse, wo die Daten sind
  pData^.String1 := 'Hallo';  // das ist RICHTIG, Du hast das taxi genommen, um zur Adresse zu fahren und kannst das haus betreten :)
  Dispose(pData);
end;

_________________
"Ich bin bekannt für meine Ironie. Aber auf den Gedanken, im Hafen von New York eine Freiheitsstatue zu errichten, wäre selbst ich nicht gekommen." - George Bernhard Shaw
Flamefire
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1207
Erhaltene Danke: 31

Win 10
Delphi 2009 Pro, C++ (Visual Studio)
BeitragVerfasst: Mi 09.09.09 14:26 
Ich glaube bei Pointern auf records geht es auch ohne ^ da Delphi das intern dereferenziert, oder?
fiore Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Mi 09.09.09 14:34 
Also bei mir handelt es sich um Pointer auf records.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
type TZeiger = ^TKnotenh;
     TFibHeap = record
                  min: TZeiger;
                  n: integer;
                end;
     TKnotenh = record
                 p, // Vater
                 kind, // Zeiger auf ein beliebiges Kind
                 links, // zeiger auf linken Bruder
                 rechts: TZeiger; // Zeiger auf rechten Bruder
                 grad: integer; // Anzahl der Kinder
                 marke: boolean; // gibt an, ob der Knoten ein Kind verloren hat
                 d: real; // enthält den Abstand zum Startknoten s => Sortierschlüssel!
                 nr: integer; // Knotennummer des Knotens v
                 pred: integer; // Vorgänger auf dem kürzesten s-v Pfad
               end;


Heißt das dann also, dass es hier keine Probleme machen dürfte, dass ich das ^ überall weggelassen habe?

@ Helge: Dein Beispiel läuft mit beiden Zeilen. Was also genau ist an der ersten Zeile falsch bzw. was passiert in der ersten Zeile ohne ^ was in der anderen Zeile nicht passiert bzw. umgekehrt?


Zuletzt bearbeitet von fiore am Mi 09.09.09 14:37, insgesamt 1-mal bearbeitet
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Mi 09.09.09 14:36 
user profile iconFlamefire hat folgendes geschrieben Zum zitierten Posting springen:
Ich glaube bei Pointern auf records geht es auch ohne ^ da Delphi das intern dereferenziert, oder?

Ja. Der .-Operator dereferenziert selber. Ist der gleiche Mechanismus, der auch auf Objekte angewendet wird, wenn man foo.bar:= '123' schreibt.

Dispose hat damit erstmal genau nix zu tun... Das würde bestenfalls mit GC ne Rolle spielen.

Wie räumst du denn auf? Eventuell fehlt ja eine Ebene oder sowas...

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
fiore Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Mi 09.09.09 14:40 
Also aufräumen mache ich bisher wie folgt:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
var Q: TFibHeap;
begin
  Q := make_fib_heap;
  [...]
  dispose(Q.min);
end


Dabei war TFibHeap wie folgt definiert:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
     TFibHeap = record
                  min: TZeiger;
                  n: integer;
                end;


Was meinst du mit "vielleicht fehlt eine Ebene?"

Es kann natürlich auch sein, dass die Speicherplatzprobleme an einer anderen Stelle auftreten. Z.b. wenn ich das Minimum aus dem Fibonacci-Heap entferne.
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: Mi 09.09.09 14:42 
Dann ist das schon klar. Du gibts einen Datenblock frei... was passiert mit den anderen? Nichts, genau. Die stehen immer noch irgendwo rum, nur, dass du nicht mehr weißt wo. Die Referenz hast du ja grade weg geworfen ;)

Du musst dich also den gesamten Baum durchhangeln und alle TZeiger in der richtigen Reihenfolge freigeben.
Darauf war auch das mit der fehlenden Ebene bezogen.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
fiore Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Mi 09.09.09 14:50 
Ah alles klar. Ja das erklärt einiges :-)

Zum Glück habe ich schon eine Ausgabe-Prozedur, die sich durch den gesamten Heap schlängelt. Da brauch ich dir nur noch so umprogrammieren, dass alles gelöscht wird. Vielen Dank! Ich hoffe es klappt!
HelgeLange
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 735
Erhaltene Danke: 6

Windows 7
Delphi7 - Delphi XE
BeitragVerfasst: Mi 09.09.09 14:57 
Der Unterschied zwischen dem Record und dem Zeiger auf ein record is ja schon da. Auch wenn es Delphi mittlerweile vielleicht selbst dereferenziert, behalte ich ich die Schreibweise bei, da ich immer genau weis, ob ich mit einem Record oder dem Zeiger darauf arbeite.. bin halt old-school :)

Und die Frage, was ein ^-Operator macht, war ja da und ich habe sie beantwortet :P

OK, zum Problem.

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
var Q: TFibHeap;
begin
  Q := make_fib_heap;
  [...]
  dispose(Q.min);
end


make_fib_heap erzeugt ja nicht nur ein TZeiger, sondern einen TFibHeap. Dein Dispose muss also auf Q sein und nicht nur auf ein Mitglied von Q. Dieses Q.Min musst Du natürlich auch freigeben mit Dispose.

_________________
"Ich bin bekannt für meine Ironie. Aber auf den Gedanken, im Hafen von New York eine Freiheitsstatue zu errichten, wäre selbst ich nicht gekommen." - George Bernhard Shaw
fiore Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Do 10.09.09 13:39 
Vielen Dank euch nochmal!

Ich habe das Problem jetzt gelöst, in dem ich mich durch den gesamten Heap hangel und jeden Knoten einzeln lösche. Der ^-Operator scheint in der Tat wegen des records nicht nötig zu sein. Allerdings gab es noch eine kleine Gemeinheit. Wenn ich in meinem Turbo-Delphi eine Zeigervariable überwache, die ich mit dispose zerstöre, wird weiterhin deren alter Wert und Verknüpfungen angezeigt. Deshalb dachte ich die ganze Zeit, dass mein dispose nicht funktionieren würde :-)

Vielen Dank für eure Hilfe und Tips!

fiore
mkinzler
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 4106
Erhaltene Danke: 13


Delphi 2010 Pro; Delphi.Prism 2011 pro
BeitragVerfasst: Do 10.09.09 14:51 
Aber ich würde trotzdem dereferenzieren auch wenn der Compiler so nett ist und den falschen Code gnädig richtig interpretiert

_________________
Markus Kinzler.