Planet-Quellcodes.de Forum -> AVLSort in Delphi

Planet-Quellcodes.de · Regeln/Impressum

Hilfe

Suche

Chat

Mitglieder

Kalender

Herzlich Willkommen. ( Einloggen | Registrieren )

erneutes Übersenden der Registrierungs-Mail

Planet-Quellcodes.de Forum -> Anwendungs- und Webentwicklung -> Delphi/Kylix

Seiten: (3) [1] 2 3 ( zum ersten ungelesenen Beitrag )

AVLSort in Delphi, Probleme bei Portierung

Thema abonnieren | Link zum Thema versenden | Thema drucken

PapaNappa

geschrieben am: 24.08.2005, 17:56

Gruppe: Mitglieder
Beiträge: 393
Mitglieds-Nr.: 33
Mitglied seit: 03.09.2004

Hallo!

Ich wollte versuchen, den Sortieralgorithmus AvlSort (Variante 3) nach Delphi zu portieren, den Quellcode gibt es auf der Applet-Seite.

Das Problem tritt bei sehr wenigen Elementen (bis 10

) nur sehr selten auf, ab 25 nur noch (in den Funktionen lRot/rRot und Balance): der zugriff die Elemente Left und Right (vom typ TAVLNode) ergibt irgendwann eine Access Violation, da diesen nichts zugewiesen wurde, also nil sind.
Mein Code (am Ende des Postes) dürfte eigentlich kaum oder garnicht vom Java-Original abweichen (welches nur in Variante 3 vorliegt, daher benutze ich diese), aber die Java-version funktioniert ja.

Den Entwickler des Algorithmus und des Applets/der Page habe ich auch schon kontaktiert, aber er hat auch im Moment keine Zeit, um sich das näher anzugucken.

hier der Code (Auszug):

CODE

interface

type
TIntegerArray= array of integer;

procedure AVLSort(var AArray: TIntegerArray); overload;

implementation

type
TAVLNode = class
public
Index, Balance: integer;
Left, Right: TAVLNode;

constructor Create(Index: integer);
end;

constructor TAVLNode.Create(Index: integer);
begin
Self.Index:=Index;
Left:=nil;
Right:=nil;
Balance:=0;
end;

procedure AVLSort(var AArray: TIntegerArray);
type
TIntegerArrayArray = array [0..1] of TIntegerArray;
var
pbal: integer;

function Resolve(A: TIntegerArray; B: TIntegerArrayArray; Index: integer; Current: TAVLNode): integer;
var
s, t: integer;
begin
if Current<>nil then
begin
Index:=Resolve(A, B, Index, Current.Left); //
s:=B[0, Current.Index];
t:=B[1, Index];
Exchange(A[s], A[Index]);
B[0, t]:=s;
B[1, s]:=t;
inc(Index);
Result:=Resolve(A, B, Index, Current.Right); //
end
else
Result:=Index;
end;

function rRot(A: TAVLNode): TAVLNode;
var
B, C: TAVLNode;
begin
B:=A.Left;
C:=B.Right;
B.Right:=A;
A.Left:=C;
pbal:=pbal+A.Balance+1;
if B.Balance<=0 then
begin
A.Balance:=A.Balance-B.Balance-1;
B.Balance:=B.Balance+A.Balance+1;
end
else
begin
A.Balance:=0;
B.Balance:=2;
end;
Result:=B;
end;

function lRot(A: TAVLNode): TAVLNode;
var
B, C: TAVLNode;
begin
B:=A.Right;
C:=B.Left;
B.Left:=A;
A.Right:=C;
pbal:=pbal-A.Balance-1;
if B.Balance>=0 then
begin
A.Balance:=A.Balance-B.Balance+1;
B.Balance:=B.Balance+A.Balance-1;
end
else
begin
A.Balance:=0;
B.Balance:=-2;
end;
Result:=B;
end;

function Balance(A: TAVLNode; bal: integer): TAVLNode;
begin
pbal:=0;
if bal<>0 then
begin
A.Balance:=A.Balance+bal;
if A.Balance=-2 then
begin
if A.Left.Balance=-1 then
begin
inc(pbal);
Result:=rRot(A);
exit;
end
else
begin
A.Left:=lRot(A.Left);
A.Balance:=A.Balance-pbal;
inc(pbal);
Result:=rRot(A);
exit;
end;
end
else if A.Balance=+2 then
begin
if A.Right.Balance=+1 then
begin
inc(pbal);
Result:=lRot(A);
exit;
end
else
begin
A.Right:=rRot(A.Right);
A.Balance:=A.Balance+pbal;
inc(pbal);
Result:=lRot(A);
exit;
end;
end
else if A.Balance<>0 then begin
inc(pbal);
Result:=A;
exit;
end;
end;
Result:=A;
end;

function Insert(A: TIntegerArray; Current, Element: TAVLNode): TAVLNode;
begin
if A[Element.Index]<A[Current.Index] then
begin
if Current.Left<>nil then
begin
Current.Left:=Insert(A, Current.Left, Element);
pbal:=-pbal;
end
else
begin
Current.Left:=Element;
pbal:=-1;
end;
end
else
begin
if Current.Right<>nil then
Current.Right:=Insert(A, Current.Right, Element)
else
begin
Current.Right:=Element;
pbal:=+1;
end;
end;
Result:=Balance(Current, pbal);
end;

procedure AVLSortInteger(var AArray: TIntegerArray; l, r: integer); inline;
var
i: integer;
Root: TAVLNode;
B: TIntegerArrayArray;
begin
Root:=TAVLNode.Create(l);
for i:=l+1 to r do
Root:=Insert(AArray, Root, TAVLNode.Create(i));
SetLength(B[0], r+1);
SetLength(B[1], r+1);
for i:=l to r do
begin
B[0, i]:=i;
B[1, i]:=i;
end;
Resolve(AArray, B, l, Root); //
end;

begin
AVLSortInteger(AArray, Low(AArray), High(AArray));
end;

--------------------

I look forward to killing you soon!

Schutsch	geschrieben am: 24.08.2005, 21:02
Gruppe: Mitglieder Beiträge: 87 Mitglieds-Nr.: 22 Mitglied seit: 03.09.2004	Ein bißchen Predebugging wäre ja schon hilfreich, ich meine es ist ja nicht sehr viel Code, aber eingrenzen sollte doch schon sein. An deiner Stelle würde ich den enstehenden Baum schritt für schritt mit einer simplen Ausgaberoutine darstellen lassen, und dann selbst rausfinden, wo exakt der Fehler ist. So nach dem Motto : procedure viewavltree(s:string;node:tavlnode); begin writeln(s,node.index); if assigned(node.left) then viewavltree(s+' ',node.left); if assigned(node.right) then viewavltree(s+' ',node.right); end; Anders würde ich es jetzt auch nicht rauskriegen, sag doch bescheid, wenn du den Fehler gefunden hast.

RainerK

geschrieben am: 25.08.2005, 16:05

Gruppe: Mitglieder
Beiträge: 53
Mitglieds-Nr.: 185
Mitglied seit: 25.09.2004

Liegt es vieleicht an der Klammersetzung?

CODE

function rRot(A: TAVLNode): TAVLNode;
var
B, C: TAVLNode;
begin
B:=A.Left;
C:=B.Right;
B.Right:=A;
A.Left:=C;
pbal:=pbal+A.Balance+1;
if B.Balance<=0 then
begin
A.Balance:=A.Balance-(B.Balance-1);
B.Balance:=B.Balance+(A.Balance+1);
end
else
begin
A.Balance:=0;
B.Balance:=2;
end;
Result:=B;
end;

function lRot(A: TAVLNode): TAVLNode;
var
B, C: TAVLNode;
begin
B:=A.Right;
C:=B.Left;
B.Left:=A;
A.Right:=C;
pbal:=pbal-A.Balance-1;
if B.Balance>=0 then
begin
A.Balance:=A.Balance-(B.Balance+1);
B.Balance:=B.Balance+(A.Balance-1);
end
else
begin
A.Balance:=0;
B.Balance:=-2;
end;
Result:=B;
end;

PapaNappa	geschrieben am: 25.08.2005, 19:15
Gruppe: Mitglieder Beiträge: 393 Mitglieds-Nr.: 33 Mitglied seit: 03.09.2004	daran kann es eigentlich nicht liegen, außer Java hat in dem Fall eine andere Rangfolge der Operatoren, was ich aber nicht glaube. Außerdem schlägt ja schon der Zugriff auf Left bzw. Right fehl, nicht erst auf .Balance @Schutsch: hab ich das nicht schon? in lRot/rRot bzw. in Balance. Mit der Ausgabe werd ich mal gucken, atm habe ich keine Zeit - morgen aber bestimmt. -------------------- I look forward to killing you soon!

Schutsch

geschrieben am: 26.08.2005, 18:27

Gruppe: Mitglieder
Beiträge: 87
Mitglieds-Nr.: 22
Mitglied seit: 03.09.2004

QUOTE (PapaNappa @ 25.08.2005, 19:15)

@Schutsch: hab ich das nicht schon? in lRot/rRot bzw. in Balance.
Mit der Ausgabe werd ich mal gucken, atm habe ich keine Zeit - morgen aber bestimmt.

Wo was ???
Die Prozedur da liefert dir nur ne Übersicht über den vorhandenen Baum.

Delphi-Laie	geschrieben am: 28.10.2009, 13:31
Gruppe: Mitglieder Beiträge: 14 Mitglieds-Nr.: 756 Mitglied seit: 24.10.2009	Hallo, ist zwar schon Jahre her, aber trotzdem: Ich beschäftige mich auch gerade mit diesem Thema, also konkret mit der Delphi-Umsetzung des AVL-Sorts. PapaNappa, hatten Sie meine PM dazu erhalten? Das Problem könnte in einem fehlerhaften Aufruf der Funktion rRot liegen. Die wird nämlich auch dann aufgerufen, wenn A.left = nil ist. Damit wird B auch nil zugewiesen, als B:=nil. Jeder Zugriff auf - logischerweise nichtexistente - "Unterelmente" auf B (also B.left, B.right und B.balance) muß damit zu einem Laufzeitfehler (konkret Exzeption) führen. Für lRot dürfte das analog gleiche gelten, die ist ja nur das "spiegelbildlich( invers)e" Pendant zu rRot. Nun kam ich auf die Idee, den Verdacht, daß lRot und rRot lediglich von der Deklaration her vertauscht sind (auch, weil zuerst rRot und dann lRot im Quelltext stehen, normalerweise fängt man ja mit links an), doch Pustekuchen, damit waren die Fehler auch nicht beseitigt. Ich werde weiterforschen und mich bei einer weiteren Einkreisung (oder gar Lösung) des Problems wieder melden.

(j)avatar

geschrieben am: 28.10.2009, 14:18

Gruppe: Mitglieder
Beiträge: 58
Mitglieds-Nr.: 753
Mitglied seit: 31.08.2009

QUOTE (PapaNappa)

Ich wollte versuchen, den Sortieralgorithmus AvlSort (Variante 3) nach Delphi zu portieren, den Quellcode gibt es auf der Applet-Seite.

Hallo PapaNappa,

leider funktionieren die beiden links (zumindest momentan) nicht. Wenn du den Java-Code posten würdest könnte ich mal den Delphi- und den Java-Code vergleichen und schauen, ob dir bei der Umsetzung Fehler unterlaufen sind.
Mir ist das auch schon mal passiert, als ich einen Sortieralgorithmus aus C in Delphi übersetzten wollte, wodurch ich meine Facharbeit verhauen habe

Meine Delphi-Zeit liegt zwar schon etwas zurück, aber das sollte kein Problem sein

mfg

--------------------

"Handle nur nach derjenigen Maxime, durch die du zugleich wollen kannst, dass sie ein allgemeines Gesetz werde."
-Immanuel Kant

NetPanther

geschrieben am: 28.10.2009, 15:11

Administrator

Gruppe: Administratoren
Beiträge: 7.696
Mitglieds-Nr.: 1
Mitglied seit: 29.08.2004

QUOTE ((j)avatar)

leider funktionieren die beiden links (zumindest momentan) nicht.

Guten Tag,

die Inhalte der verlinkten Seite stellt der einstige Gründer derzeit noch unter dieser Adresse zum Abruf bereit. Die o.g. Domain ist schon seit geraumer Zeit nicht mehr zu erreichen.

MfG

--------------------

:: NetPanther :: NetPanther@gmx.net :: Website :: IRC Channel: #NetPanther ::

Das Leben ist eine Beta. Nichts ist vollkommen.

Delphi-Laie	geschrieben am: 28.10.2009, 15:39
Gruppe: Mitglieder Beiträge: 14 Mitglieds-Nr.: 756 Mitglied seit: 24.10.2009	Oh, konnte ich diese Diskussion reanimieren? Freut mich. Peter Weigel quengelte ich schon im Sommer die Ohren (bzw. Augen) voll. Er gab vor wenigen Jahren seine Sortierseite an einen Schweizer Informatikprofessor ab, der sie nicht nur nicht weiterpflegte, sondern sogar ein wenig abbaute, zurückfuhr. Nachdem besagte Seite seit dem Frühsommer nicht mehr erreichbar ist, schwieg er auf meine und sogar Herrn Weigels diesbezügliche Anfrage. Herr Weigel entschloß sich dankenswerterweise zu dieser „Notlösung“. Ich finde es klasse, daß die beste deutschsprachige Sortierseite wenigstens auf diese Weise erhalten blieb. Zurück zum AVL-Sort: Ein (der?) Wurm steckt eindeutig auch oder allein schon „weiter vorn“ im Programmablauf, nämlich in der l-&rRot-aufrufenden Prozedur „Balance“. Beitrag bearbeitet von Delphi-Laie am 28.10.2009, 15:42

(j)avatar

geschrieben am: 28.10.2009, 16:33

Gruppe: Mitglieder
Beiträge: 58
Mitglieds-Nr.: 753
Mitglied seit: 31.08.2009

QUOTE (Delphi-Laie)

Ein (der?) Wurm steckt eindeutig auch oder allein schon „weiter vorn“ im Programmablauf, nämlich in der l-&rRot-aufrufenden Prozedur „Balance“.

Für den Fall das wirklich "nur" ein Fehler in balance steht, hab ich jetzt einfach mal "java-balance" in "delphi-balance" übersetzt.
Stecken zwar vlt. Tipp- und/oder Flüchtigkeitsfehler drin, aber Delphi wird ja schon meckern, wenn solche Fehler drin sind.
Bei Gelegenheit und falls meine Übersetzung nicht schon das Problem löst (Daumen drücken!) schau ich mir deinen Code und den Originalcode mal genauer an.

CODE

function balance(a: tavlnode; bal: integer): tavlnode;
begin
pbal:=0;
if bal<>0 then begin
a.balance:=a.balance+bal;
if a.balance=-2 then begin
if a.left.balance:=-1 then begin
inc(pbal)
result:=rrot(a);
end
else begin
a.left:=lrot(a.left);
a.balance=a.balance-pbal;
inc(pbal);
result:=rrot(a);
end;
end
else if a.balance=2 then begin
if a.right.balance=1 then begin
inc(pbal);
result:=lrot(a);
end
else begin
a.right:=rrot(a.right);
a.balance:=a.balance+pbal;
inc(pbal);
result:=lrot(a);
end;
end
else if a.balance<>0 begin
inc(pbal);
result:=a;
end;
end;
result:=a;
end;

Ps.: hat schon mal jemand den original-Code geprüft? Vlt. hat sich da ja bereits ein Fehler eingeschlichen.

mfg

--------------------

"Handle nur nach derjenigen Maxime, durch die du zugleich wollen kannst, dass sie ein allgemeines Gesetz werde."
-Immanuel Kant

Delphi-Laie	geschrieben am: 28.10.2009, 22:42
Gruppe: Mitglieder Beiträge: 14 Mitglieds-Nr.: 756 Mitglied seit: 24.10.2009	Danke für Deine Mühe! Im Originalbeitrag von PapaNappa folgt den einzelnen Result-Zuweisung der exit-Befehl, was ich für korrekt(er) halte als Deine Version, bei der das finale result:=a ja immer aufgerufen wird. Damit wären die result-Zuweisungen vorher überflüssig. Besondere Erfahrung im Übersetzen von C-Derivaten nach Pascal/Delphi habe ich allerdings nicht, ich lehne mich also nicht weit hinaus. Der Fehler in Balance äußerte sich bei mir schon dahingehend, daß auf a.left.balance zugegriffen wird, obwohl a.left=nil ist (analog a.right(.balance)). Dem Autor der Internetseite kann ich ein Hochmaß an Sorgfalt bescheinigen, jedoch kann ich mich an zwei Algorithmen erinnern, die nicht so ohne weiteres in Pascal-Übersetzung funktionierten (einmal mußte eine Variable anders gesetzt werden, im anderen Falle funktioniert es bis heute bei mir nicht hundertprozentig zufriedenstellend). Egal, ich werde jedenfalls so schnell nicht aufgeben, und weitere Ergebnisse, sofern vorliegend, hier beitragen. Beitrag bearbeitet von Delphi-Laie am 28.10.2009, 22:58

(j)avatar

geschrieben am: 28.10.2009, 23:20

Gruppe: Mitglieder
Beiträge: 58
Mitglieds-Nr.: 753
Mitglied seit: 31.08.2009

@delphi-laie

kann sein das mein code nicht ganz korrekt ist. hab bloß zeile für zeile übersetzt (also so wie google englische Seiten übersetzt

). Für eine ordentliche Übersetzung müsste ich mich mal in das Sortierverfahren einarbeiten, was Erfahrungsgemäß einige Zeit in Anspruch nimmt.
Ich schau mir das ganze aber wie gesagt bei gelegenheit mal an, was aber eventuell bis zum Wochenende dauern könnte.

Aber wenn a.left = nil ist solltest du mal gucken, wie das sein kann, das a.left nicht belegt wird. Das hört sich stark danach an, als läge das Problem schon in einer "übergeordneten" Funktion. Du solltest auf jeden Fall mal nachgucken wo a.left und a.right gesetzt werden sollten, oder du baust folgendes ein an Stellen, an denen a.left/right gelesen werden und schaust was passirt:

CODE

if a.left<>nil;

sonst bleibt nur debuggen.

Tip: lass dir mit writeln() an so vielen Stellen wie möglich die wichtigsten Variablen ausgeben und geh dann Schritt für Schritt durch, was wann, wieso passiert. Ist sehr aufwändig, aber so findest du bestimmt den Fehler.

mfg

--------------------

"Handle nur nach derjenigen Maxime, durch die du zugleich wollen kannst, dass sie ein allgemeines Gesetz werde."
-Immanuel Kant

Delphi-Laie	geschrieben am: 28.10.2009, 23:39
Gruppe: Mitglieder Beiträge: 14 Mitglieds-Nr.: 756 Mitglied seit: 24.10.2009	Yo, danke erneut! Natürlich gehe ich so (ähnlich) vor, der Debugger läßt ja kaum etwas unentdeckt. Einen Fehler habe ich schon entdeckt: Bei einer inversen Permutation (also absteigend, jedes Element einmal) muß nur der Stack entsprechend erhöht werden (ich maximiert ihn auf den Maximalwert über 16 Millionen). Dann sortiert mir das Programm auch 1.200 Elemente/Wert fehlerfrei. Bei einer Zufallspermutation kommen Abbruchfehler (der in lRoot) leider teilweise schon bei <10 Elementen. Beitrag bearbeitet von Delphi-Laie am 28.10.2009, 23:41

(j)avatar	geschrieben am: 29.10.2009, 00:07
Gruppe: Mitglieder Beiträge: 58 Mitglieds-Nr.: 753 Mitglied seit: 31.08.2009	Sicher, dass die Vergrößerung des Stacks etwas damit zu tun hat? Wenn der zu klein ist bekommt man soweit ich weiß eine Fehlermeldung "Stackoverflow". Und 1.200 Elemente ist eigentlich noch recht wenig. Normalerweise sollten auch Listen mit mehreren millionen Elementen kein Problem sein. Bei Listen mit 1200 Elementen macht es nicht einmal Sinn viel Zeit in komplizierte Sortieralgorithmen zu stecken. Da tun es auch schon einfache Sortierverfahren, wie Bubblesort, die wesentlich einfacher zu implementieren sind, da sie kurz und nicht rekursiv sind. Beitrag bearbeitet von (j)avatar am 29.10.2009, 00:08 -------------------- "Handle nur nach derjenigen Maxime, durch die du zugleich wollen kannst, dass sie ein allgemeines Gesetz werde." -Immanuel Kant

Delphi-Laie

geschrieben am: 29.10.2009, 11:30

Gruppe: Mitglieder
Beiträge: 14
Mitglieds-Nr.: 756
Mitglied seit: 24.10.2009

QUOTE

Sicher, dass die Vergrößerung des Stacks etwas damit zu tun hat?

Ja!

QUOTE

Wenn der zu klein ist bekommt man soweit ich weiß eine Fehlermeldung "Stackoverflow".

Genau die bekam ich ja, und zwar in der Zeile "begin" gleich nach der Funktionseröffnungszeile: function Insert..... Eigentlich verblüffend, weil ich die Stacknutzung nur von der Rekursion (her) kenne, und die finde ich in diesem Algorithmus nicht.

Edit: Doch, schon welche gefunden, und zwar bei der Ergebniszuweisung der Funktion resolve und in der Funktion Insert.

QUOTE

Normalerweise sollten auch Listen mit mehreren millionen Elementen kein Problem sein. Bei Listen mit 1200 Elementen macht es nicht einmal Sinn viel Zeit in komplizierte Sortieralgorithmen zu stecken. Da tun es auch schon einfache Sortierverfahren, wie Bubblesort, die wesentlich einfacher zu implementieren sind, da sie kurz und nicht rekursiv sind.

Mir geht es um die Herausforderung. In anderen Delphiforen veröffentlichte ich ein Sortiervisualisierungsprogramm. Wenn ich es mit solch immensen Algorithmen noch erweitern könnte.... Ich verbeiße mich aber nicht darin. Die Entscheidung, ob ich mich als Nichtinformatiker damit zu weit aus dem Fenser lehnte, habe ich noch nicht getroffen.

Beitrag bearbeitet von Delphi-Laie am 29.10.2009, 19:18

0 Besucher zu diesem Thema (0 Gäste und 0 'versteckte' Mitglieder)

0 Mitglied(er):

« älteres Thema | Delphi/Kylix | neueres Thema »

Seiten: (3) [1] 2 3

[ DB Queries: 11 ] [ Execution Time: 0.1140 ] [ GZIP aktiviert ]