| Autor |
Beitrag |
fiore
Hält's aus hier
Beiträge: 10
|
Verfasst: 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
      
Beiträge: 735
Erhaltene Danke: 6
Windows 7
Delphi7 - Delphi XE
|
Verfasst: 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 :
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; begin New(pData); pData.String1 := 'Hallo'; pData^.String1 := 'Hallo'; 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
      
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mi 09.09.09 14:26
Ich glaube bei Pointern auf records geht es auch ohne ^ da Delphi das intern dereferenziert, oder?
|
|
fiore 
Hält's aus hier
Beiträge: 10
|
Verfasst: Mi 09.09.09 14:34
Also bei mir handelt es sich um Pointer auf records.
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, kind, links, rechts: TZeiger; grad: integer; marke: boolean; d: real; nr: integer; pred: integer; 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
      
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mi 09.09.09 14:36
Flamefire hat folgendes geschrieben : | | 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 
Hält's aus hier
Beiträge: 10
|
Verfasst: Mi 09.09.09 14:40
Also aufräumen mache ich bisher wie folgt:
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:
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
      
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: 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 
Hält's aus hier
Beiträge: 10
|
Verfasst: 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
      
Beiträge: 735
Erhaltene Danke: 6
Windows 7
Delphi7 - Delphi XE
|
Verfasst: 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
OK, zum Problem.
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 
Hält's aus hier
Beiträge: 10
|
Verfasst: 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
      
Beiträge: 4106
Erhaltene Danke: 13
Delphi 2010 Pro; Delphi.Prism 2011 pro
|
Verfasst: 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.
|
|