Programmieren - alles kontrollieren 4.941 Themen, 20.708 Beiträge

DOS-Programm: Sortier-Ergebnisse weichen von einander ab

dromedar / 14 Antworten / Baumansicht Nickles

Immer noch arbeite ich an und mit einem DOS-Programm, erstellt mit Turbo-Pascal 7.0. (Leider kenne ich nichts, was eine Umstellung auf Windows (Delphi) halbwegs automatisch ermöglicht.)
Auf meinem neuen Computer (Windows XP Prof.) stelle ich nun fest, dass Sortier-Ergebnisse, Ablauf mit denselben Daten auf demselben Weg, von einander abweichen: Mal sind sie in Ordnung, mal ist die Sortierung fehlerhaft. Kann die Ursache dafür sein, dass der Computer wegen seiner höheren Geschwindigkeit die Ursache dafür ist? Wenn ja: Wie kann ich diese für DOS-Programme drosseln? Oder wo kann die Ursache sonst liegen?
Für Hilfe wäre ich sehr dankbar.

bei Antwort benachrichtigen
Max Payne dromedar „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Was genau sortierst Du denn?

The trouble with computers is that they do what you told them – not necessarily what you wanted them to do.
bei Antwort benachrichtigen
PaoloP dromedar „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Warum ist denn er Umstieg auf Delphi nicht möglich?
Tausende IT-Unterricht Schüler in deutschen Grundschulen mussten mit Delphi programmieren
weil umfunktionierte Mathelehrer früher mal Pascal gelernt haben. Scheint zu gehen.
Anonsten musst du schon sagen was du da sortierst und welchen Sortieralgorithmus du verwendest.

Jedes mal wenn jemand "Cloud" sagt, verliert ein Engel seine Flügel.
bei Antwort benachrichtigen
Andreas42 dromedar „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Hi!

Ich kann mir nicht vorstellen, dass die CPU-Geschwindigkeit die Bearbeitungsreihenfolge von compilierten Turbo-Pascal anwendungen beeinflusst. Turbo-pascal erzeugt einen auf 286er CPUs optimierten Binärcode (soweit ich wiess). Der Code steht fix im Programm und die CPU führt ihn aus. Da kann es aus meiner Sicht keine Abweichungen in Sortierergebnissen geben, sofern die Sortierung im Programmcode erfolgt.
Einziges Problem ist die Zeitmessung bei Programmstart in der Standardbibliothek. Die musstest du ja vermutlich schon patchen.

Ich denke eher an die üblichen Fehler: man will alphabetisch sortieren, erwartet das Umlaute korrekt einsortiert werden, vergisst aber, dass die von ihrem CHR-Wert, ausserhalb des normalen Alphabets liegen.
Evtl. hat man die Umlaute auch berücksichtigt, aber dann nur für DOS-ASCII-Kodierung, nicht aber für die unter Windows verwendete ANSI-Kodierung.

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
PaoloP Andreas42 „Hi! Ich kann mir nicht vorstellen, dass die CPU-Geschwindigkeit die...“
Optionen

Der Gedanke kam mir auch aber das Verhalten ist wohl bei gleichen Daten nicht generisch.

Jedes mal wenn jemand "Cloud" sagt, verliert ein Engel seine Flügel.
bei Antwort benachrichtigen
Andreas42 PaoloP „Der Gedanke kam mir auch aber das Verhalten ist wohl bei gleichen Daten nicht...“
Optionen

Hi!

Wenn wir es auf diese allgemeine theoretische Betrachtungsweise angehen, dann müssen wir logisch schlussfolgern, dass die Programmierung bewirkt, dass die Sortierung auf schnelleren CPUs kein eindeutiges Ergebnis liefert. Die Ursache liegt daher der programmiertechnischen Umsetzung.

Dann lautet die Lösung natürlich: das Programm muss so geändert werden, dass das nicht passiert.

;-)

Ich hätte aber lieber konkrete Beispiele, was sortiert wird und dann wie rauskommt. Zudem natürlich den TurboPascal-Quelltext der Sortierung. Wer weiss schon, was wirklich passiert?

Ausgehend von meiner Person (und meiner ureigenen Schusseligkeit), wäre die naheliegende Ursache, dass die Ausgangsdaten beim groben Überfliegen gleich aussehen und auf den ersten Blick gleich verarbeitet werden, sich dann aber nach kräftigem Fluchen ("Himmel, Arsch und Zwirn!" - universeller hessischer Fluch) und Verwünschen ("Mist!", Zitat Bernd das Brot) herausstellt, dass sich die Ausgangsdaten doch unterscheiden und sie zusätzlich doch nicht gleich verarbeitet werden (weil irgendein Zusatzprogramm aufgerufen wird, dass unter XP etwas anders arbeitet als unter DOS). ;-)

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
PaoloP dromedar „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

ich glaub der thread starter is längst weg ...

Jedes mal wenn jemand "Cloud" sagt, verliert ein Engel seine Flügel.
bei Antwort benachrichtigen
dromedar Nachtrag zu: „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Hallo Helfer,

vielen Dank für Eure Antworten. Hier die zu meiner Frage gewünschten Ergänzungen.

Max Payne: Was genau sortierst Du denn?

"records", nämlich Datensätze mit Ergebnissen von sportlichen Wettbewerben. Zweck: Erstellung von Ranglisten nach den Erfolgen in den vorangegangenen drei Jahren - jeden Monat neu mit den Ergebnissen des letzten Monats.
Alle Ergebnisse eines Monats sind in einer Datei "file of record" gespeichert. Jeder "record" besteht aus mehreren String- und Zahlen-Datenfeldern mit Angaben zur Person des Teilnehmers und zu seinem Erfolg.
Der Teilnehmerkreis ist begrenzt, in der Regel im Bereich von 30 bis 200. Jeder Teilnehmer ist eindeutig gekennzeichnet durch ein Kürzel aus maximal fünf Großbuchstaben. Die Zahl der Wettbewerbe liegt monatlich meist im Bereich von 4 bis 25, deren jeweilige Teilnehmerzahl 12 bis 80.

PaoloP:
Warum ist denn er Umstieg auf Delphi nicht möglich?
Tausende IT-Unterricht Schüler in deutschen Grundschulen mussten mit Delphi programmieren
weil umfunktionierte Mathelehrer früher mal Pascal gelernt haben. Scheint zu gehen.
Anonsten musst du schon sagen was du da sortierst und welchen Sortieralgorithmus du verwendest.

Die exe-Datei des Programms passt gerade noch auf eine 1,4-MByte-Diskette, die Programmzeilen habe ich nicht gezählt. Begonnen habe ich damit vor 20 Jahren im Alter von >60. Sollte ich dann später für Windows in einer doch recht anderen Programmiersprache sozusagen ein neues Programm in Angriff nehmen?
Die Sortierung erfolgt auf der Basis der Chip-Spezial-Toolbox-Unit TREELIB, die wohl aus den Neunziger-Jahren stammt, in einer dynamischen Baumstruktur: Die Datensätze werden an die Unit übergeben und entsprechend dem maßgebenden Datenfeld in den Baum eingefügt.

Andreas42:
Der Code steht fix im Programm und die CPU führt ihn aus. Da kann es aus meiner Sicht keine Abweichungen in Sortierergebnissen geben, sofern die Sortierung im Programmcode erfolgt.
Einziges Problem ist die Zeitmessung bei Programmstart in der Standardbibliothek. Die musstest du ja vermutlich schon patchen.
Ich denke eher an die üblichen Fehler: man will alphabetisch sortieren, erwartet das Umlaute korrekt einsortiert werden, vergisst aber, dass die von ihrem CHR-Wert, ausserhalb des normalen Alphabets liegen.
Evtl. hat man die Umlaute auch berücksichtigt, aber dann nur für DOS-ASCII-Kodierung, nicht aber für die unter Windows verwendete ANSI-Kodierung.

Code: Das dachte ich auch. Aber muss das immer so sein?
Zeitmessung: Davon weiß ich nichts. Was muss ich dafür eventuell tun?
Alphabetisch: Das ist mir klar. Es stand aber beispielsweise bei der Sortierung nach den Namenskürzeln der Datensatz mit ZIP zwischen den mit N beginnenden Datensätzen.

Andreas42:
Wenn wir es auf diese allgemeine theoretische Betrachtungsweise angehen, dann müssen wir logisch schlussfolgern, dass die Programmierung bewirkt, dass die Sortierung auf schnelleren CPUs kein eindeutiges Ergebnis liefert. Die Ursache liegt daher der programmiertechnischen Umsetzung.
Dann lautet die Lösung natürlich: das Programm muss so geändert werden, dass das nicht passiert.
Ich hätte aber lieber konkrete Beispiele, was sortiert wird und dann wie rauskommt. Zudem natürlich den TurboPascal-Quelltext der Sortierung. Wer weiss schon, was wirklich passiert?
Ausgehend von meiner Person (und meiner ureigenen Schusseligkeit), wäre die naheliegende Ursache, dass die Ausgangsdaten beim groben Überfliegen gleich aussehen und auf den ersten Blick gleich verarbeitet werden, sich dann aber nach kräftigem Fluchen ("Himmel, Arsch und Zwirn!" - universeller hessischer Fluch) und Verwünschen ("Mist!", Zitat Bernd das Brot) herausstellt, dass sich die Ausgangsdaten doch unterscheiden und sie zusätzlich doch nicht gleich verarbeitet werden (weil irgendein Zusatzprogramm aufgerufen wird, dass unter XP etwas anders arbeitet als unter DOS). ;-)

Programm ändern: aber wie?
Quelltext: Als Beispiel von mehreren eingesetzten Funktionen hier die Entscheidungsfunktion für eine Sortierung nach Namenskürzeln:
function VglRS (p10, p20: pointer): boolean;
var kl : shortint;
v1, v2 : v_ispieler_m;
begin
VglRS := t;
Move (p10^, v1, SizeOf (v_ispieler_m));
Move (p20^, v2, SizeOf (v_ispieler_m));
kl := KzlKleiner (v1.ikzl, v2.ikzl);
if kl = -1 then Exit;
if kl = 0 then if KzlKleiner (v1.iclub, v2.iclub) = -1 then Exit;
VglRS := f;
end; {VglRS}
Es sind v1 und v2 die zu vergleichenden Datensätze und ikzl die Namenskürzel darin sowie iclub sekundäre Namenskürzel, die gegenwärtig noch nicht verwendet werden, also immer leer sind. Die Funktion KzlKleiner gibt zurück 1 für v1 > v2, 0 für v1 = v2 und -1 für v1 Die Baum-Unit umfasst 272 Zeilen mit den Prozeduren und Funktionen
FindNode, FirstNode, LastNode, NextNode, PrevNode, DelNode, PutBack, Swap, NewTree, InsVar, NewNode, FirstVar, LastVar, NextVar, PrevVar, FindVar, DelVar und DisposeTree.
Sind davon welche für die Beurteilung von Bedeutung?
Ausgangsdaten: Die sind hundertprozentig gleich, weil sie vor meinen Operationen jedes Mal vom Original- in den Verwendungs-Ordner kopiert habe. Und auch der Ablauf war jedes Mal gleich.

Gibt es eine Erklärung?
Schönes Wochenende!
(Morgen werde ich nicht an den Computer kommen.)

bei Antwort benachrichtigen
Andreas42 dromedar „Hallo Helfer, vielen Dank für Eure Antworten. Hier die zu meiner Frage...“
Optionen

Hi!

Ich gehe mal auf meine Rückmeldungen ein.

Der Punkt Patch der Zeitmessung in der Runtime-Libray von TurboPascal ist z.B. hier beschrieben:
http://www.webplain.de/turbopascal/error200.php

Die ursprüngliche Version der CRT-Bibliothek brach mit einem Error 200 auf CPUs mit mehr als 200MHz ab.

Ich setze einen Patch aus der c't ein:
http://www.heise.de/ct/hotline/Nicht-schon-wieder-Runtime-Error-200-307662.html
Bzw. ich nutze Borland Pascal 7.0 da war der Quelltext der CRT-Bibliothek im Lieferumfang und man konnte die Stelle entsprechend ändern und neu kompilieren.

Meinen zweiten Beitrag mit der theoretischen Betrachtung kannst du igrnorieren. In solchen Fällen kommt man mit der Theorie nicht weiter, da muss man die reale Implementierung betrachten.
Oder um es noch etwas überspitzter zu formulieren: es gibt keinen Programmfehler, der sich für Theorien oder Verträge interessiert und diese in seinem Verhalten berücksichtigt. ;-)

Danke für den Quelltext. Das erleichtert die Betrachtung.

function VglRS (p10, p20: pointer): boolean;
var kl : shortint;
v1, v2 : v_ispieler_m;
begin
VglRS := t;
Move (p10^, v1, SizeOf (v_ispieler_m));
Move (p20^, v2, SizeOf (v_ispieler_m));
kl := KzlKleiner (v1.ikzl, v2.ikzl);
if kl = -1 then Exit;
if kl = 0 then if KzlKleiner (v1.iclub, v2.iclub) = -1 then Exit;
VglRS := f;
end; {VglRS}

Auf den ersten Blick ist allerdings nichts zu erkennen, was da zu Unschärfen führen sollte. Eine Anmerkung habe ich allerdings: ich finde es ungünstig, das die Parameter von VglRS untypisierte Zeiger sind und dann der zugewiesene Speicher mehr oder weniger "blind" in echte Objekte (oder Records) kopiert wird.

Ich hätte p10 und p20 als Zeiger vom Typ v_ispieler_m deklariert, da hätte man sich die Kopieroperation mit move(..) sparen können. Damit umgeht man jede Typprüfung von TurboPascal. Da könnte ich jetzt nicht garantieren, dass das wirklich CPU- und plattformunabhängig klappt. Es sollte, aber wer weiss das schon wirklich?

VglRS := t(rue) ist die Vorbelegung bzw. initialisierung des Rückgabeergebnisses.
Das wird zurück gegeben, wenn der Vergleich ein Kleiner zurückliefert (-1) oder wenn das Ergebnis Gleich ist. Für die restlichen Ergebnisse (also +1) wird f(alse) zurückgegeben.

OK, das würde passen. Bei kleiner oder gleich muss nicht getauscht werden. (Ich vermute du nutzt ein Bubblesort das darauf basiert zwei Objektinstanzen zu vergleichen und bei Bedarf zu vertauschen.)


Was genau meinst du mit dem "Datensatz mit ZIP"? (ZIP-Postalcode?) Sortierst du da Adressen und Namen? Ist das reproduzierbar?


Deine Funktion VglRS(..) scheint mir bisher einfach nur die Funktion KzlKleiner(..) zu kapseln. (Sie ist eine Funktion, die einen Grösser/Kleiner-Vergleich durchführt udn dazu eine Funktion aufruft, die einen Grölsser/Kleiner-Vergleicht durchführt aufruft.)

Falls das Problem im Grösser/Kleiner-Vergleich liegt, dann müsste man sich die Funktion KzlKleiner(..) ansehen.

Die Funktion Swap(..) dürfte zwei Elemente tauschen, vermutlich nach dem Vergleich. Ein Bubblesort erfordert ja bei n zu sortierenden Elementen, n Durchläufe durch den Array. Zu Beschleunigungszwecken geht man dann davon aus, dass nach jedem Durchlauf (i) die ersten i-1 Elemente bereits korrekt sortiert sind und fängt daher mit dem i-ten Element in der Liste an (vergleicht es mit dem Element i-1) und arbeitet sich zum Ende der Liste durch.
Wenn da das Startelement des jeweiligen Durchlaufs falsch bestimmt wird, dann kann es "vergessene" Element in der resultierenden Liste geben.

Wie genau arbeitet deine Sortierung?

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
dromedar Nachtrag zu: „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

> Der Punkt Patch der Zeitmessung in der Runtime-Libray von TurboPascal ist z.B. hier beschrieben:
> http://www.webplain.de/turbopascal/error200.php

Früher verwendete ich gelegentlich Zeitmessungen, jetzt aber nicht mehr. Deswegen brauche ich dafür wohl nichts zu tun.

> Die ursprüngliche Version der CRT-Bibliothek brach mit einem Error 200 auf CPUs mit mehr als 200MHz ab.

> Ich setze einen Patch aus der c't ein:
> http://www.heise.de/ct/hotline/Nicht-schon-wieder-Runtime-Error-200-307662.html
> Bzw. ich nutze Borland Pascal 7.0 da war der Quelltext der CRT-Bibliothek im Lieferumfang und man konnte die Stelle entsprechend ändern und neu kompilieren.

Einen solchen Abbruch habe ich noch nie erlebt. Laut Aida32 hat die CPU meines Computers eine vorgesehene Taktung von 2333 MHz (2,5 x 933). Allerdings setze ich in meinem Programm nicht die Borland-Unit crt ein, sondern stattdessen die Unit OPcrt von Enz EDV-Beratung Gmbh (laut c't-Archiv 4/1995 Seite 28 bankrott)von 1990: "Bei OPcrt handelt es sich um einen vollständigen Ersatz der Standard Turbo Pascal Unit CRT. Obwohl ... vollständige Kompatibilität mit dieser Unit besteht, bietet OPcrt ... Erweiterungen und Steigerungen. ... " Wahrscheinlich verarbeitet sie deswegen die höhere Geschwindigkeit ohne dieses Problem.

> function VglRS (p10, p20: pointer): boolean;
> var kl : shortint;
> v1, v2 : v_ispieler_m;
> begin
> VglRS := t;
> Move (p10^, v1, SizeOf (v_ispieler_m));
> Move (p20^, v2, SizeOf (v_ispieler_m));
> kl := KzlKleiner (v1.ikzl, v2.ikzl);
> if kl = -1 then Exit;
> if kl = 0 then if KzlKleiner (v1.iclub, v2.iclub) = -1 then Exit;
> VglRS := f;
> end; {VglRS}

> Auf den ersten Blick ist allerdings nichts zu erkennen, was da zu Unschärfen führen sollte. Eine Anmerkung habe ich allerdings: ich finde es ungünstig, das die Parameter von VglRS untypisierte Zeiger sind und dann der zugewiesene Speicher mehr oder weniger "blind" in echte Objekte (oder Records) kopiert wird.

Diese Funktion ist eine von elf ähnlichen Vergleichs-Funktionen, die unterschiedliche Records bearbeiten, aber alle aus der Baum-Unit aufgerufen werden. Vorher bekommt die Baum-Unit (im Beispiel unten rsBptr) vom Hauptprogramm als Parameter den zu bearbeitenden Datensatz zugewiesen (ispieler) sowie die far-Adresse der Vergleichs-Funktion (VglRS), die zu verwenden ist, und falls erforderlich die Datensatzlänge (SizeOf). Die globale Variable lby ist hier der zurückgegebene Code. Beispiel:
Aufruf: InsVar (rsBptr, ispieler, SizeOf (v_ispieler_m), VglRS, lby);
procedure InsVar (var baum5: p_baum_u; var v0; siz0: integer;
KleinF: FuncKlein; var okay9: byte);
{fügt die Variable v0 mit der Größe siz0 Bytes in den Baum ein -
bei Gleichheit wird der bestehende Eintrag überschrieben
okay9 = 0, wenn Variable v0 eingefügt
1, wenn bestehender Eintrag überschrieben
2, wenn Speicherplatz nicht ausreicht}
var pk1, pk2 : pKnoten;
dir : (l, r);
pv : ^t_objekt;
procedure NewNode (var B_neu: pKnoten; last: p_baum_u);
var pk1 : pKnoten;
begin
if MaxAvail 1 then Exit;
New (pk1);
with pk1^ do begin
size := siz0; left := nil; right := nil; back := last;
GetMem (inhalt, size); Move (v0, inhalt^, size); end {with};
B_neu := pk1;
end; {NewNode}
begin {InsVar}
pk1 := pKnoten (baum5); pk2 := pk1; pv := @v0; okay9 := 0;
while pk1 nil do with pk1^ do begin
pk2 := pk1;
if KleinF (pv, inhalt) then begin dir := l; pk1 := left; end
else if KleinF (inhalt, pv) then begin dir := r; pk1 := right; end
else begin
if pk1^.size siz0 then Writeln ('TYPE MISMATCH ERROR!')
else Move (v0, inhalt^, size);
okay9 := 1; Exit; end {else};
end {while};
NewNode (pk1, pk2); if okay9 > 1 then Exit;
if pk2 nil then if dir = l then pk2^.left := pk1
else pk2^.right := pk1
else baum5 := pk1;
end; {InsVar}

> Ich hätte p10 und p20 als Zeiger vom Typ v_ispieler_m deklariert, da hätte man sich die Kopieroperation mit move(..) sparen können. Damit umgeht man jede Typprüfung von TurboPascal. Da könnte ich jetzt nicht garantieren, dass das wirklich CPU- und plattformunabhängig klappt. Es sollte, aber wer weiss das schon wirklich?

Das wäre nicht so zweckmäßig, weil die Baum-Unit nicht nur Datensätze vom Typ v_ispieler_m bearbeitet, sondern auch eine ganze Anzahl mehr.

> VglRS := t(rue) ist die Vorbelegung bzw. initialisierung des Rückgabeergebnisses.
> Das wird zurück gegeben, wenn der Vergleich ein Kleiner zurückliefert (-1) oder wenn das Ergebnis Gleich ist. Für die restlichen Ergebnisse (also +1) wird f(alse) zurückgegeben.

> OK, das würde passen. Bei kleiner oder gleich muss nicht getauscht werden. (Ich vermute du nutzt ein Bubblesort das darauf basiert zwei Objektinstanzen zu vergleichen und bei Bedarf zu vertauschen.)

Anderswo schon, aber hier nicht. Hier werden Datensätze als "Knoten" gespeichert zusammen mit den Adressen des vorangehenden und des nachfolgenden Knotens (links und rechts).

> Was genau meinst du mit dem "Datensatz mit ZIP"? (ZIP-Postalcode?) Sortierst du da Adressen und Namen? Ist das reproduzierbar?

ZIP ist das Namenskürzel des Teilnehmers Zipp Heinrich. Im aktuellen Fall wurden die Datensätze nach den Namenskürzeln sortiert. Die fehlerhafte Sortierung ist nicht reproduzierbar.

> Deine Funktion VglRS(..) scheint mir bisher einfach nur die Funktion KzlKleiner(..) zu kapseln. (Sie ist eine Funktion, die einen Grösser/Kleiner-Vergleich durchführt udn dazu eine Funktion aufruft, die einen Grölsser/Kleiner-Vergleicht durchführt aufruft.)

> Falls das Problem im Grösser/Kleiner-Vergleich liegt, dann müsste man sich die Funktion KzlKleiner(..) ansehen.

function KzlKleiner (kzl10, kzl20: a_kzl_g): shortint;
{Rückgabe 1 / 0 / -1 für kzl10 > / = / var i : byte;
begin
for i := 1 to cLKzl_gz do begin
if kzl10[i] = #0 then kzl10[i] := ' ';
if kzl20[i] = #0 then kzl20[i] := ' ';
if kzl10[i] > kzl20[i] then begin KzlKleiner := 1; Exit; end;
if kzl10[i] KzlKleiner := 0;
end; {KzlKleiner}
Es ist a_kzl_g ein array [1 .. cLKzl_gz] of char, cLKzl_gz die Konstante 5.

> Die Funktion Swap(..) dürfte zwei Elemente tauschen, vermutlich nach dem Vergleich. Ein Bubblesort erfordert ja bei n zu sortierenden Elementen, n Durchläufe durch den Array. Zu Beschleunigungszwecken geht man dann davon aus, dass nach jedem Durchlauf (i) die ersten i-1 Elemente bereits korrekt sortiert sind und fängt daher mit dem i-ten Element in der Liste an (vergleicht es mit dem Element i-1) und arbeitet sich zum Ende der Liste durch.
> Wenn da das Startelement des jeweiligen Durchlaufs falsch bestimmt wird, dann kann es "vergessene" Element in der resultierenden Liste geben.

Die Prozedur Swap wird nur bei der Löschung eines Knotens aus dem Baum eingesetzt, um die Pointer in den Nachbarknoten (links und rechts) anzupassen.
procedure Swap(var X,Y);
var XPtr : pointer absolute X;
YPtr : pointer absolute Y;
TPtr : pointer;
begin
TPtr:=XPtr; XPtr:=YPtr; YPtr:=TPtr;
end {Swap};

> Wie genau arbeitet deine Sortierung?

Diese Frage verstehe ich leider nicht. Ihre Aufgabe ist es, die Datensätze genau in die Reihenfolge zu bringen, die durch das aktuelle Datenfeld bestimmt wird.

Trotzdem hoffe ich, dass ich helfen konnte mein Problem zu lösen.

Schönes Wochenende!

bei Antwort benachrichtigen
Andreas42 dromedar „ Der Punkt Patch der Zeitmessung in der Runtime-Libray von TurboPascal ist z.B....“
Optionen

Hi!

Diese Funktion ist eine von elf ähnlichen Vergleichs-Funktionen, die unterschiedliche Records bearbeiten, aber alle aus der Baum-Unit aufgerufen werden. Vorher bekommt die Baum-Unit (im Beispiel unten rsBptr) vom Hauptprogramm als Parameter den zu bearbeitenden Datensatz zugewiesen (ispieler) sowie die far-Adresse der Vergleichs-Funktion (VglRS), die zu verwenden ist, und falls erforderlich die Datensatzlänge (SizeOf).

Das ist C-Programmierstil. ;-)

Ich hätte dazu eine Objektstruktur erstellt, welche eine Basisklasse verwendet und dann für die 11 Records 11 abgeleitete Objektklassen verwendet. Die Funktionen oder Methoden, die mit all den 11 Typen arbeiten müssen, erwarten dann als Parameter einen Zeiger der Basisklasse.
Die Vergleichsmethode wird dann virtuell deklariert und in der jeweiligen Klasse implementiert.

Ich vermeide einfach Typkonvertierungen und untypisierte Pointer, soweit ich das kann. Diese IMHO C-typischen Operationen waren mir nie ganz geheuer. Ich finde, da verliert man zu schnell bei Änderungen die interne Datenintegrität.

> Wie genau arbeitet deine Sortierung?

Diese Frage verstehe ich leider nicht. Ihre Aufgabe ist es, die Datensätze genau in die Reihenfolge zu bringen, die durch das aktuelle Datenfeld bestimmt wird.


Ich wollte, dass du beschreibst, wie du deine Knoten-Elemente sortierst, also wie der programmierte Algorithmus abläuft. (Geklärt; siehe Unten)

Die Funktion musste ich mir etwas anders Formatieren, damit ich den Ablauf verstehe. Vermutlich fehlen Ungleichs im Quelltext, weil Nickles.de die gefiltert hat. (Kommentare sind von mir.)


procedure InsVar (var baum5: p_baum_u; var v0; siz0: integer;KleinF: FuncKlein; var okay9: byte);
{fügt die Variable v0 mit der Größe siz0 Bytes in den Baum ein -
bei Gleichheit wird der bestehende Eintrag überschrieben
okay9 = 0, wenn Variable v0 eingefügt
1, wenn bestehender Eintrag überschrieben
2, wenn Speicherplatz nicht ausreicht}

var pk1, pk2 : pKnoten;
dir : (l, r); {Suchrichtung für Einfügestelle}
pv : ^t_objekt; {das ist jetzt ein Objekt und nicht pointer? inhalt ist auch so deklariert?}

procedure NewNode (var B_neu: pKnoten; last: p_baum_u); {wieso ist last nicht vom Typ pKnoten? Unten wird da pk2 zugewiesen.}
var pk1 : pKnoten;
begin
if MaxAvail 1 then Exit;
New (pk1);
with pk1^ do
begin
size := siz0; left := nil; right := nil; back := last;
GetMem (inhalt, size); Move (v0, inhalt^, size);
end {with};
B_neu := pk1;
end; {NewNode}

begin {InsVar}
pk1 := pKnoten (baum5); pk2 := pk1; pv := @v0; okay9 := 0;
while pk1 nil do {schluckt Nickles.de hier das ungleich?}
with pk1^ do
begin
pk2 := pk1; {aktueller Node in pk2 speichern}
{im aktuellen Element bestimmen, ob der neue Node Links oder Rechts eingefügt werden muss.}
if KleinF (pv, inhalt) then {ich vermute pk1.inhalt wäre korrekt, oder?}
begin
{pv ist kleiner als der aktuelle Node, also linkes Element als nächstes nehmen}
dir := l; pk1 := left;
end
else
begin {ich wars}
{pv war nicht kleiner}
if KleinF (inhalt, pv) then
begin
{pk1.inhalt ist kleiner als pv (Prüfung erfolgt eigentlich um Gleichheit festzustellen)
also rechten Node nehmen}
dir := r; pk1 := right;
end
else
begin
{pk1.inhalt und pv sind gleich, also überschreiben}
if pk1^.size siz0 then Writeln ('TYPE MISMATCH ERROR!')
else Move (v0, inhalt^, size);
okay9 := 1;
Exit; {Funktion verlassen}
end {else};
end; {ich wars}
end {while/eigentlich with};
{while endet hier}
NewNode (pk1, pk2);
if okay9 > 1 then Exit;
if pk2 nil then
{Abhängig vom letzten Suchschritt neuen Node in zuletzt beim Suchlauf gefundenen Node eintragen
Bei Gleichheit wurde Funktion bereits beendet.}
if dir = l then pk2^.left := pk1
else pk2^.right := pk1
else
{Sonderfall: erster Node in Baum}
baum5 := pk1;
end; {InsVar}


Baum5 scheint ein Zeiger auf den ersten Node der Baumstruktur zu sein, wird mit einem Wert vom Typ pknoten belegt, ist aber vom Typ p_baum_u.

Durch die Analyse der Funktion habe ich verstanden, wie dein Sortieren funktioniert. Du baust einen sortierten Baum auf. OK. Grundsätzlich funktioniert das und obwohl ich die ganze Typenbehandlung in deinen Sourcen nicht mag ;-) , kann ich keinen Grund finden, warum die Routine falsch arbeiten sollte.

Der Baum muss aber noch ausgegeben werden. Vielleicht liegt das Problem an der Stelle. Wie wird die Liste der gespeicherten daten aus dem Baum ausgelesen?

Bis dann
Andreas

Hier steht was ueber mein altes Hard- und Softwaregedoens.
bei Antwort benachrichtigen
ChrE Andreas42 „Hi! Das ist C-Programmierstil. - Ich hätte dazu eine Objektstruktur erstellt,...“
Optionen

Hallo,

kopier doch den Quelltext nach:

http://gist.github.com/

Da wird er ordentlich formatiert und alle Zeichen werden
richtig abgebildet. Du musst dann nur noch den Link posten.

Gruss

ChrE


bei Antwort benachrichtigen
dromedar Nachtrag zu: „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Hallo Andreas42 und Andere,

das Problem scheint erledigt: Wie so oft, saß es vor dem Bildschirm, zumindest zum Teil. Einiges ist aber dazu noch zu sagen und zu fragen.

Eine Frage zuerst:
Wie kann ich bewirken, dass Zitate wie bei Dir farbig unterlegt auf den Bildschirm kommen? Ich kenne für Übernommenes nur aus meinem E-Mail-Programm Pegasus Mail die Häkchen > vor der Zeile.

>> Diese Funktion ist eine von elf ähnlichen .....

> Das ist C-Programmierstil. ;-)
> Ich hätte dazu eine Objektstruktur erstellt .....

Als Turbo Pascal in irgend einer früheren Version die objektorientierte Programmierung ermöglichte, habe ich diese zunächst in einem Fall angewandt. Dabei ist herausgekommen, dass die TPU der Unit danach wesentlich größer war als vorher. Da mein Programm auf eine 1,4-MByte-Diskette passen sollte, bin ich dann bei der prozeduralen Programmierung geblieben. Objekte finden sich nur in Programmteilen, die ich wie die Baum-Sortierung aus anderen Quellen übernommen habe.

> Ich vermeide einfach Typkonvertierungen und untypisierte Pointer, soweit ich das kann. Diese IMHO C-typischen Operationen waren mir nie ganz geheuer. Ich finde, da verliert man zu schnell bei Änderungen die interne Datenintegrität.

Bisher bin ich eigentlich mit meinem "ohne" gut zurecht gekommen.

> Die Funktion musste ich mir etwas anders Formatieren, damit ich den Ablauf verstehe. Vermutlich fehlen Ungleichs im Quelltext, weil Nickles.de die gefiltert hat. (Kommentare sind von mir.)
.....
> pv : ^t_objekt; {das ist jetzt ein Objekt und nicht pointer? inhalt ist auch so deklariert?}

interface
type p_baum_u = pointer; {die Baumstruktur}
FuncKlein = function (p1, p2: pointer): boolean;

implementation
type t_objekt = array [0 .. maxint] of byte; {Sortier-Objekt}
pKnoten = ^vKnoten;
vKnoten = record
left, right, back : pKnoten;
size : integer;
inhalt : ^t_objekt;
end;

> procedure NewNode (var B_neu: pKnoten; last: p_baum_u); {wieso ist last nicht vom Typ pKnoten? Unten wird da pk2 zugewiesen.}

Wohl weil p_baum_u global verwendet wird, pKnoten aber nur lokal.

> var pk1 : pKnoten;
> begin
> if MaxAvail 1 then Exit;

Die letzte dieser Zeilen muss lauten:
if MaxAvail 1 then Exit;

> .....
> begin {InsVar}
> pk1 := pKnoten (baum5); pk2 := pk1; pv := @v0; okay9 := 0;
> while pk1 nil do {schluckt Nickles.de hier das ungleich?}

Jedenfalls gehört's hinein.

> with pk1^ do begin
> pk2 := pk1; {aktueller Node in pk2 speichern}
> {im aktuellen Element bestimmen, ob der neue Node Links oder Rechts eingefügt werden muss.}
> .....

Ja, so ist's.

> NewNode (pk1, pk2);
> if okay9 > 1 then Exit;
> if pk2 nil then

Auch hier fehlte das Ungleich.

> Baum5 scheint ein Zeiger auf den ersten Node der Baumstruktur zu sein, wird mit einem Wert vom Typ pknoten belegt, ist aber vom Typ p_baum_u.

Siehe oben type.

> Durch die Analyse der Funktion habe ich verstanden, wie dein Sortieren funktioniert. Du baust einen sortierten Baum auf. OK. Grundsätzlich funktioniert das und obwohl ich die ganze Typenbehandlung in deinen Sourcen nicht mag ;-) , kann ich keinen Grund finden, warum die Routine falsch arbeiten sollte.

> Der Baum muss aber noch ausgegeben werden. Vielleicht liegt das Problem an der Stelle. Wie wird die Liste der gespeicherten daten aus dem Baum ausgelesen?

Die hoffentlich nicht nur vorläufige und eingangs erwähnte Lösung:

Das Problem trat auf beim Arbeiten in der Turbo-Pascal-Entwicklungsumgebung. Beim weiteren Untersuchen für diese heutige Antwort stieß ich darauf, dass bei jedem neuen Programmstart nur beim ersten Durchlauf falsch sortiert wurde - jedes Mal gleich falsch -, beim nächsten aber nicht. Damit war die Rekonstruktion möglich und das Finden der Ursache: Die "Urdatei" wurde als ordnungsgemäß alfabetisch nach den Teilnehmerkürzeln geordnet angesehen und behandelt. Ein Teilnehmer war aber anstatt in der Mitte erst am Ende gespeichert. Mit seinem Platzindex 82 wurde dann aus der umsortierten Teilnehmerliste der richtig alfabetisch letzte Teilnehmer in die Mitte eingefügt.

Leider habe ich das erst im Zuge des oben Geschilderten gefunden. Jedenfalls danke ich Dir und allen anderen Ratgebern für die Unterstützung.

Beste Grüße

bei Antwort benachrichtigen
BastetFurry dromedar „DOS-Programm: Sortier-Ergebnisse weichen von einander ab“
Optionen

Ohne das ich jetzt Pascal genau kenne (C und Assembler-Mensch hier ;) ), versuch das ganze doch mal mit DosBOX auszuführen.
Und was die Nutzung von Pascal unter Windows angeht, mal FreePASCAL ausprobiert?

bei Antwort benachrichtigen
Borlander BastetFurry „Ohne das ich jetzt Pascal genau kenne C und Assembler-Mensch hier , versuch das...“
Optionen

Das Problem war nicht die Umgebung, sondern nicht zutreffende Annahmen (und eine fehlende Prüfung selbiger) zu den Eingabedaten...

bei Antwort benachrichtigen