Eine Java-Klasse in ihr Delphi-Pendant übersetzen

Delphi-Laie · Verfasst: Mo 06.03.17 23:44

Hallo Programmierfreunde, darf ich bitte noch mal etwas fragen?

Es geht um die Java-Klasse jener Diskussion, die ich dank der entscheidend-punktuellen Hilfen dort zum Laufen brachte. Das ist dort dermaßen objektorientiert, daß ich mich entschloß, diesen Algorithmus in Pascal/Delphi auch objektorientiert umzusetzen - eigentlich "nur" zu übersetzen - sonst müßte ich zu oft zwischen "objektorientiert" und "nicht objektorientiert" quelltextbezogen und gedanklich hin- und herschalten.

Lange Rede, die erste Java-Klasse, die es zu übersetzen galt, ist diese:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:

/** Class Leonardo implements basic manipulation of Leonardo numbers */
private static class Leonardo
{
  /* data members */
  private int m_iSize;
  private int m_iPrevious;
  /* access */
  public int getSize() { return m_iSize; }
  private void setSize(int iSize) { m_iSize = iSize; }
  private int getPrevious() { return m_iPrevious; }
  private void setPrevious(int iPrevious) { m_iPrevious = iPrevious; }
  /* default constructor */
  public Leonardo()
  {
    setSize(1);
    setPrevious(1);
  }
  /* copy constructor */
  public Leonardo(Leonardo lSize)
  {
    setSize(lSize.getSize());
    setPrevious(lSize.getPrevious());
  } /* copy constructor */
  /* recursion */
  public void up()
  {
    int iTemp = m_iSize;
    setSize(m_iPrevious + m_iSize + 1);
    setPrevious(iTemp);
  }
  public void down()
  {
    int iTemp = m_iPrevious;
    setPrevious(m_iSize - m_iPrevious - 1);
    setSize(iTemp);
  }
} /* class Leonardo */

Für geübte OOP-Programmierer und geschulte Augen sicher simpel, ja geradezu trivial, ist ja auch nur eine kleine Klasse.

Dennoch taucht schon hier die erste Frage auf:

1. Wo ist der Destruktor?

Meine Delphi-Übersetzung dazu:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:

type Leonardo=class
  private
    m_iSize,m_iPrevious:integer;
    procedure setSize(iSize:integer);
    function getPrevious:integer;
    procedure setPrevious(iPrevious:integer);
  public
    constructor create;overload;
    constructor create(lSize:Leonardo);overload;
    destructor destroy;override;
    function getSize:integer;
    procedure up;
    procedure down;
  end;

constructor Leonardo.create;
begin
inherited;
setSize(1);
setPrevious(1)
end;

constructor Leonardo.create(lSize:Leonardo);
begin
inherited create;//ohne "create" kommt Compilerfehler: "Inkompatible Typen", Grund unbekannt
setSize(lSize.getSize{()});
setPrevious(lSize.getPrevious{()})
end;

destructor Leonardo.destroy;
begin
inherited
end;

procedure Leonardo.setSize(iSize:integer);
begin
m_iSize:=iSize
end;

function Leonardo.getSize;
begin
result:=m_iSize
end;

function Leonardo.getPrevious;
begin
result:=m_iPrevious
end;

procedure Leonardo.setPrevious(iPrevious:integer);
begin
m_iPrevious:=iPrevious
end;

procedure Leonardo.up;
var iTemp:integer;
begin
iTemp:=m_iSize;
setSize(m_iPrevious+m_iSize+1);
setPrevious(iTemp)
end;

procedure Leonardo.down;
var iTemp:integer;
begin
iTemp:=m_iPrevious;
setPrevious(m_iSize-m_iPrevious-1);
setSize(iTemp)
end;

an der der Compiler auch nichts auszusetzen hat, beim Destruktor weiß ich aber gar nichts, außer den vererbten aufzurufen. Da es zwei Konstruktoren gibt, ist "overload" wohl die richtige Wahl. Fragen:

2. Ist das soweit richtig?
3. Warum darf im zweiten überladenen Konstruktor nicht nur "inherited" stehen, sondern der Compiler akzeptiert nur die Langform "inherited create"?
4. Welchen höheren Sinn hat es, den Kon- und den Destruktor public zu deklarieren? Nach meinen Experimenten mit anderen Klassen können diese auch mit privatem Kon-/Destruktor oder ohne explizite Sichtbarkeitsattribute funktionieren. Die Delphi-Hilfe sagt nicht, und die Foren erschöpfen sich auch sehr schnell zu solchen Fragen, die mir gar nicht sehr speziell vorkommen.

Bitte entschuldigt, daß es gleich 4 Fragen "am Stück" sind, aber die sind ja thematisch alle zusammenhängend.

Danke und Gruß

Delphi-Laie

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Di 07.03.17 14:57

Vielen herzlichen Dank, liebe Frühlingsrolle! Du gibst Dir ja eine Mühe (nochmalige Übersetzung, mit der ich Unroutinierter mehr als eine geschlagene Stunde verbrachte), die ich nicht einmal zu träumen wagte, geschweige denn, damit rechnete. Bist ja fast so etwas wie ein persönlicher Mentor für mich geworden.

Ja, die Properties mit ihren Lese- und/oder Schreibvariablen kenne sogar ich, doch diese hier einzusetzen und einen solch beeindruckend komprimierten Code damit hervorzuzaubern, ist mir nicht einmal in den Sinn gekommen, und ich wäre dazu allein wohl außerstande gewesen. Ich war schon froh, daß diese - weitgehende - 1:1-Übersetzung vom Compiler akzeptiert wurde.

So ganz klar ist mir immer noch nicht, warum ein Destruktor entbehrlich sein soll(te) und was dieser außer "inherited" oder "inheritec destroy" noch aufzunehmen hätte. Immerhin lernte ich, alles "manuell" (also explizit) angeforderte auch - irgendwann - "manuell" wieder freizugeben. Warum sollte das bei der TLeonardo-Klasse anders sein?!

Auch ist mir weiterhin unklar, warum "inherited" und "inherited create" im zweiten Konstruktor nicht synonym sind. Auch das war neu für mich. Kann ja nur am zusätzlichen Parameter liegen (und tut es auch, wie ich soeben prüfte). Nunja, Delphi ist in bezug auf Objektpascal der Experte, nicht ich.

Frühlingsrolle hat folgendes geschrieben :

Nachtrag:

Wenn du den SmoothSort nachbauen möchtest, hier gibt es schon eine in Delphi geschriebene Version. Ich schätze mal, sie wurde von dieser Version hier übersetzt.

Das kenne ich doch schon, aber dennoch danke! Du bist der zweite nach Horst_H, der mir das anbietet. Doch das implementierte ich schon vor Jahren. Mir geht es um einen weiteren Alternativalgorithmus (zum Smoothsort), weil dieser signifikante Änderungen zu Dijkstras Original haben muß und höchstwahrscheinlich auch - mehr oder weniger anders als der erstgenannte zu sein scheint (zusätzliche Routinen).

Und nun geht es mit (der Übersetzung) der nächsten Klasse weiter, hoffentlich noch etwas selbständiger.

Horst_H · Verfasst: Di 07.03.17 18:07

Hallo,

[offtopic]
auf der Suche nach dem heiligen Gral des smoothsort ;-)

Die neue Version im Sortierkino ( www.keithschwarz.com/smoothsort/ ), habe ich mal getestet.
Bei 1MIo double-Daten unsortiert dauert es bei mir 1200 ms, die oben verlinkte etwa 800 ms ( auf Trab gebracht mittlerweile 280 ms x64 mit BitScanForward von Freepascal,ohne 305 ms ( QuickSort braucht 120 ms fürs selbe) )
Was aber viel wichtiger erscheint:
1MioDaten sortiert, das, wo smoothsort auftrumpfen sollte, braucht 820 ms ala keithschwarz und 15 ms mit der obigen aufgepimpten Version.
Die Verwaltung des Heaps muss also kriminell schlecht sein.
Weiterhin viel Vergnügen beim umstricken der Java-Version,

Gruß Horst

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Di 07.03.17 22:05

Danke! Puh, das muß ich erstmal verdauen.

Unabhängig davon war ich heute nachmittag schon fleißig, und angeregt von Deiner vorigen Übersetzung, wagte ich es, die nächste Klasse gleich mit properties zu versuchen. Damit tat ich mir insofern keinen Gefallen, daß es kam, wie es kommen mußte, ich blieb an mehreren Stellen stecken.

Hier zunächst der Java-Quellcode:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:

/** Class Sequence implements basic manipulation of concatenation sequence sizes.
The current size is not stored in the bitmap but is assumed to be occupied.
if current size = L(n) and bit i is set in bitmap then L(n+i) is in
concatenation sequence. Thus having bit 0 set means, that current size
appears twice (can only occur for size 1).
*/
private static class Sequence
{
  /* data members */
  private Leonardo m_lSize;
  private int m_iStretches;
  /* access */
  public Leonardo getSize() { return m_lSize; }
  private void setSize(Leonardo lSize ) { m_lSize = lSize; }
  private int getStretches() { return m_iStretches; }
  private void setStretches(int iStretches) { m_iStretches = iStretches; }
  /** default constructor */
  public Sequence()
  {
    setSize(new Leonardo());
    setStretches(0);
  }
  /** copy constructor */
  public Sequence(Sequence sSize)
  {
    setSize(new Leonardo(sSize.getSize()));
    setStretches(sSize.getStretches());
  }
  /** returns underlying current size of binary heap */
  public int size()
  {
    return m_lSize.getSize();
  } /* size */
  /** empty returns true, if there are no stretches to the left */
  private boolean empty()
  {
    return m_iStretches == 0;
  } /* empty */
  /** length returns total size of ternary heap */
  public int length()
  {
    int iLength = size();
    Sequence s = new Sequence(this);
    while (!s.empty())
    {
      s.upToPrevious();
      iLength = iLength + s.size();
    }
    return iLength;
  } /* length */
  /** mergeable is given, if bit 1 is set */
  public boolean mergeable()
  {
    return (m_iStretches & 2) != 0;
  } /* mergeable */
  /** permanent returns true, if ternary tree at root is permanent */
  public boolean permanent(int iRoot, int iTotalSize)
  {
    boolean bPermanent = true;
    int iSize = m_lSize.getPrevious();
    if (iSize < 0)
      iSize = 0;
    if ((iRoot + 1) + iSize + 1 <= iTotalSize)
      bPermanent = false;
    return bPermanent;
  } /* permanent */
  /** up goes to next size */
  public void up()
  {
    m_lSize.up(); /* size of left stretch */
    setStretches(m_iStretches >> 1);
  } /* up */
  /** down goes to previous size */
  public void down()
  {
    m_lSize.down();
    setStretches(m_iStretches << 1);
  } /* down */
  /** upToPrevious finds next stretch size in sequence */
  public void upToPrevious()
  {
    /* find next occupied stretch */
    while (!empty() && !mergeable())
      up();
    up();
    clear();
  } /* upToPrevious */
  /** downToOne reduces current size to one */
  public void downToOne()
  {
    set();
    /* go down to one */
    down();
    while (size() > 1)
      down();
  } /* downToOne */
  /** set adds current size to left sequence */
  public void set()
  {
    m_iStretches = m_iStretches | 1;
  } /* set */
  /** clear removes current size from left sequence */
  public void clear()
  {
    m_iStretches = m_iStretches & ~1;
  } /* clear */
} /* class Sequence */

Ist "eigentlich" kaum komplizierter als die vorige, und ich konnte sogar etwas von jener schöpfen. Doch nicht genug. An meiner Pascal-Übersetzung:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:

type TSequence=class
  private
    FSize: TLeonardo;//m_lSize
    FStretches: Integer;//m_iStretches
    property Size: TLeonardo read FSize write FSize;
    property Stretches: Integer read FStretches write FStretches;
    function empty: boolean;
    function mergeable:boolean;
  public
    constructor Create; overload;
    constructor Create(sSize: TSequence); overload;
    function length: integer;
    function permanent(iRoot, iTotalSize: integer): boolean;
    procedure up;
    procedure down;
    procedure upToPrevious;
    procedure downToOne;
    procedure myset;
    procedure clear;
  end;

constructor TSequence.Create;
begin
inherited;
Size := TLeonardo.create;
Stretches:=0
end;

constructor TSequence.Create(sSize: TSequence);
begin
inherited create;
Size := TLeonardo.create(Size);
FStretches:=FStretches//? Stretches := Stretches?
end;

function TSequence.empty: boolean;
begin
result := Stretches=0
end;

function TSequence.length: integer;
var s: TSequence;
begin
//result := Size;//Compilerfehler: "Inkompatible Typen: 'Integer' und 'TLeonardo'
s := TSequence.Create(self);//?
while not s.empty do
  begin
  s.upToPrevious;
  length := length + s.Size.FSize//oder s.Size.Size?
  end
//s.destroy hier angebracht?
end;

function TSequence.mergeable:boolean;
begin
result := (Stretches and 2) <> 0//? unsicher, wird ggf. später überprüft
end;

function TSequence.permanent(iRoot,iTotalSize: integer): boolean;
var iSize: integer;
begin
result := true;
iSize := FSize.Previous;//? nur "Previous" ist unbekannt
if iSize < 0 then iSize:=0;
if iRoot + iSize +2 <= iTotalSize then result := false
end;

procedure TSequence.up;
begin
Size.Up;
Stretches := Stretches shr 1
end;

procedure TSequence.down;
begin
Size.Down;
Stretches := Stretches shl 1
end;

procedure TSequence.upToPrevious;
begin
while not empty and not mergeable //oder: not (empty or mergeable)
do up;
up;
clear
end;

procedure TSequence.downToOne;
begin
myset;
down;
//while size > 1 do//Compilerfehler: "Inkompatible Typen"
down
end;

procedure TSequence.myset;
begin
Stretches := Stretches or 1//später überprüfen
end;

procedure TSequence.clear;
begin
Stretches := Stretches and not 1//später überprüfen: Das Zeichen "~" invertiert in Java alle Bits, tut das nicht auch ein einfaches "not"?
end;

hat Delphi so einiges herumzumosern, was ich in die Kommentare schrieb. Ich kann Delphi verstehen, denn ich wüßte sogar noch an manch anderer Stelle mehr nicht, was der Quelltext einem sagen will. Weitere Unsicherheiten habe ich ebenfalls als Kommentare hinterlassen.

Besonders die Java-Zeile

markieren

Quelltext

1:	setStretches(sSize.getStretches())

läuft in der Property-behafteten Pascal-Übersetzung, weil die Werteauslesung und die -zuweisung in eine Variable gepackt wurde, aus meiner jetzigen Sicht auf eine Wertzuweisung einer Variablen an sich selbst hinaus, was unsinnig ist.

Ich weiß, ich strapziere Deine / Eure Aufmerksamkeit schon weit über Gebühr, aber vielleicht kann doch noch mal jemand soviel Zeit opfern und mir die Fehler nennen, bitte?

Alternativ könnte ich es natürlich auf die einfachere Art ohne Properties versuchen.

Vielen Dank nochmal im voraus und viele Grüße

Delphi-Laie

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Di 07.03.17 22:26

Hallo Horst, danke!

Kannst Du bitte mal diesen Deinen Satz:

Horst_H hat folgendes geschrieben :

1MioDaten sortiert, das, wo smoothsort auftrumpfen sollte, braucht 820 ms ala keithschwarz und 15 ms mit der obigen aufgepimpten Version.

etwas verständlicher (um)formulieren? Ich verstehe ihn nämlich auch nach wiederholtem Lesen nicht.

Horst_H hat folgendes geschrieben :

Die Verwaltung des Heaps muss also kriminell schlecht sein.

Verstehe ich ebenfalls nicht. Soll das am Compiler oder am Algorithmus liegen?

Bei unsortierten Mengen hat Quicksort immer die Nase vorn, und zwar deutlich. Auch bei n*log(n) gibt es eben Unterschiede.

Smoothsort ist eine akademische Angelegenheit. Zum einen war es die Herausforderung für Dijkstra, Heapsort zu "adaptivieren". Das ist ihm gelungen. Zum anderen ist dieser Algorithmus auch heute noch eine Herausforderung für Mathematiker und Informatiker, ihn zu verstehen, ihn nachzuvollziehen und ggf. auch zu verbessern. So kamen die Versionen zustande.

Er ist jedoch für den praktischen Einsatz wegen dieser Komplizierthei völlig ungeeignet.

Und wenn die Originale nicht fehlerfrei liefen (Konjunktiv II, also laufen würden) - das taten sie bis heute zum Glück immer - dann habe ich kaum eine Chance, das zu korrigieren (obwohl auch mir Ausnahmen gelangen).

Horst_H hat folgendes geschrieben :

Weiterhin viel Vergnügen beim umstricken der Java-Version,

Ist das ironisch oder wortwörtlich? Mich-In-Etwas-Verbeißen ist eine meiner Disziplinen, anders als mit Hartnäckigkeit kommt man im Reiche der Bits und Bytes auch kaum voran.

Delphi-Laie · Verfasst: Di 07.03.17 22:28

Frühlingsrolle hat folgendes geschrieben :

Probier es mal damit:

Das ist ein Verstoß gegen Einstein und konrekt gegen seine spezielle Relativitätstheorie, weil überlichtgeschwind! ;-)

Danke! Da bin ich jetzt aber mal gespannt, wo ich wieder gepatzt habe...

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Horst_H · Verfasst: Mi 08.03.17 08:35

Hallo,

Zitat:

für 1 MioDaten sortiert, das, wo smoothsort auftrumpfen sollte, braucht 820 ms ala keithschwarz und 15 ms mit der obigen aufgepimpten Version

Das heisst, dass bei sortiert vorliegenden Daten smoothsort ja extrem schnell sein sollte und es bei Deiner Implementation nach Keith Schwarz mit 820 ms nicht ist.Die andere Delphi Version saust in 15 ms darüber.
Ich habe jetzt diese Version auf Bit-Operationen, statt array of boolean umgestellt.
Dann ist es unter Freepascal 3 immer noch 30% langsamer, unter Delphi aber 20% schneller.Da habe ich wohl falsch optimiert....
Jetzt mal exemplarisch die Daten für 1 Mio double Werte.
Smo2 ist die Version aus Deinem Sortierkino nach Keith Schwarz
smo ist die Version, die als Delphi Unit vorlag( up und down durch Leonardo[h] ersetzt)

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Freepascal 3.0.2 x32 ohne Bitscanbefehle 
*  Komplett gemischt  |  Laufzeit    |Vergleiche   Bewegungen
Smo2           100.0%       429 ms     55225496            0
Smo            100.0%       325 ms     53796838     27884299
Qik            100.0%       110 ms     16040231     10739763
sortiert vorgegeben:
Smo2             0.0%        35 ms      3999874            0
Smo              0.0%        16 ms      1999963      1000010
Qik              0.0%        32 ms     17951445      1572861

jetzt Delphi 7 ( ohne Zählerei, sind identisch zu oben, kostet nur wenige ms)
    Komplett gemischt  |  Laufzeit    |Vergleiche   Bewegungen
Smo2           100.0%       471 ms            0            0
Smo            100.0%       594 ms            0            0
Qik            100.0%       125 ms            0            0
sortiert vorgegeben:
Smo2             0.0%        44 ms            0            0
Smo              0.0%        33 ms            0            0
Qik              0.0%        21 ms            0            0

Ich finde es gut, bei weiteren Versionen nach Verbesserungen zu suchen, denn irgendwann platzt ein Knoten und man hat eine neue Idee.
Anbei eine Version des Testprogrammes mit Konsolenausgabe.

Gruß Horst

Einloggen, um Attachments anzusehen!

Delphi-Laie · Verfasst: Mi 08.03.17 13:31

Horst_H hat folgendes geschrieben :

Das heisst, dass bei sortiert vorliegenden Daten smoothsort ja extrem schnell sein sollte und es bei Deiner Implementation nach Keith Schwarz mit 820 ms nicht ist.Die andere Delphi Version saust in 15 ms darüber.
Ich habe jetzt diese Version auf Bit-Operationen, statt array of boolean umgestellt.

Hallo Horst, nach meinem Kenntnisstand kann man keine Shift-Operationen auf Delphi-Arrays anwenden (ich bewundere die größere Flexibilität der C-Programmiersprachen). Mithin habe ich sie "nachgebildet". Daß das nicht sonderlich performant ist, war mir von vornherein klar, sollte aber bei den maximal wenigen tausend zu sortierenden Elementen in meinem Sortierprogramm keine entscheidende Rolle spielen. Ich bin schon heilfroh, etwas - offensichtlich - fehlerfrei hinbekommen zu haben, optimiert wird nur nebenbei und nur "im Rahmen meiner Kenntnisse".

Ich werde mir Deinen Quelltext genauer anschauen. Solltest Du diese Shifts wesentlich besser als meine Wenigkeit hinbekommen haben (so kündigst Du es ja an), erlaube ich mir, unter Nennung Deines Pseudonyms und mit Danksagung mein Programm in dieser Hinsicht ebenfalls zu optimeren.

Gruß

Delphi-Laie

Ergänzung: Horst, was bist Du für ein Zaubermeister, daß Dein

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

procedure shift_left(var a: booleanarray; shift: longint);
begin
  a := a shl shift;
end;

procedure shift_right(var a: booleanarray; shift: longint);
begin
  a := a shr shift;
end;

in meinem Delphi 4 funktioniert, währendhingegen in meinem Sortierkino derlei Befehle natürlich nicht ausführbar sind ("Operator ist auf diesen Operandentyp nicht anwendbar.")? Wie erreichst Du das? :?:

Edit2: Du verpackst das Booleanarray in einen Integer...

Horst_H · Verfasst: Mi 08.03.17 15:23

Hallo,

etwas offtopic....
Dein shape ist einfach nur die Darstellung der Anzahl der Elemente insgesamt auf dem Haufen in "Leonardo"-Form, analog Zeckendorf www.ijon.de/mathe/fibonacci/node5.html
Also einem merkwürdigem Stellenwertsystem mit den Leonardo-Zahlen: oeis.org/A001595

smallestTreeSize ist bei meiner Umsetzung der Delphi Unit h geworden und benennt den kleinsten Leonardo-Heap.Und trees ist dann der darüberliegende Teil.Die nierderwertigsten '0' sind dabei entfernt.
Der geniale Kunstgriff dabei ist, das die Leonardo 0 und 1, welche beide 1 sind, getauscht werden.
Normal wäre:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

         Leonardo-Zahl-Nummer
                    76543210 

         1          00000001  0<= h 
         2          00000011  0
         3          00000100  2
         4          00000101  0
         5          00001000  3
         6          00001001  0
         7          00001011  0
         8          00001100  2
         9          00010000  4
        10          00010001  0
        11          00010011  0
        12          00010100  2
        13          00010101  0
        14          00011000  3
        15          00100000  5

aber in dem Programm ist es:

markieren

Delphi-Quelltext

1:
2:

    with Shape do
      writeln(IntToBin(trees shl smallestTreeSize,16,16));

bzw. writeln(IntToBin(BitFldLeoHeaps shl h,16,16));

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Leonardo-Zahl-Nummer
1111111100000000
5432109876543201              

0000000000000010 == 1 also wird nur ein neuer Heap Größe 1 aka Wurzel bei 0 eingefügt  
0000000000000011 == 2 also wird nur ein neuer Heap Größe 1 aka Wurzel bei 1 eingefügt  
0000000000000100 == 3 also 1 und 0 werden zusammgefast und neues Element eingefügt
0000000000000110 == 4 also wird nur ein neuer Heap Größe 1 aka Wurzel eingefügt 
0000000000001000 == 5 also 3 und 1 werden zusammgefast und neues Element eingefügt
0000000000001010 == 6 also wird nur ein neuer Heap Größe 1 aka Wurzel bei 0 eingefügt 
0000000000001011 == 7 also wird nur ein neuer Heap Größe 1 aka Wurzel bei 1 eingefügt 
0000000000001100
0000000000010000
0000000000010010
0000000000010011
0000000000010100
0000000000010110
0000000000011000
0000000000100000

Dabei ist nämlich sofort ersichtich, wenn zwei aufeinanderfolgende Leonardozahlen genutzt werden ( also'11' ), bewirkt eine Erhöhung um eins das diese beiden nicht mehr genutzt werden sondern die folgende Leonardozahl. (das ergibt shr 2 und h := h+2).
Auf den LeonardoHeap bezogen, werden zwei Heaps zu einem zusammen gefasst.
Der Übergang von 4 auf 5 Elemente ist damit elegant gelöst, der tanzt nämlich sonst aus der Reihe.

Was noch schön ist, diese zwei auf einanderfolgenden 1 kann es nur "ganz unten" geben.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

3184  1010101010101010  1
3185  1010101010101011  0
3186  1010101010101100  2
3187  1010101010110000  4
3188  1010101011000000  6
3189  1010101100000000  8
3190  1010110000000000 10
3191  1011000000000000 12
3192  1100000000000000 14
3193 10000000000000000 16 == Leonardozahl 17, wenn Zählung bei 1 beginnt

Sodele, genug verwirrt ;-)

Gruß Horst

Delphi-Laie · Verfasst: Fr 10.03.17 00:02

So nett das von Dir auch war, Frühlingsrolle, ich muß leider doch - wenigstens erstmal - meine Übersetzungen nach Delphi verwenden, um ein möglichst 1:1-Abbild des Java-Quelltextes zu erzeugen. Die eigentliche Schwerarbeit geht nämlich jetzt erst los, nein, sie ist schon im vollen Gange, nämlich das parallele Debuggen, um den Algorithmus zum Laufen zu bringen, und das geht nur dahingehend, die Fehler in meiner Übersetzung zu finden. Sollte dieser Algorithmus jemals in Pascal laufen, kann ich immer noch die Veränderungen / Vereinfachungen / Codekomprimierungen versuchen, dann werden die Properties ihre zweite Chance bekommen.

Doch nun sieht es ganz trüb aus, so trüb wie noch nie.

Im Smoothsort-Quelltext wird eine lokal erzeugte Instanz von TSequence "s":

markieren

Delphi-Quelltext

1:
2:

s:=TSequence.Create(sSize);
s.upToPrevious();

im Konstruktor mit den korrekten Daten bestückt und im nächsten Befehl an die parameterlose Klassenmethode

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

procedure TSequence.upToPrevious();
begin
while not empty and not mergeable
do up;
up;
clear
end;

geschickt ("empty", "mergeable", "up" und "clear" sind natürlich auch deklarierte, parameterlose Methoden derselben Klasse). Phänomenale Folge: Ich kann die Datenstruktur "s" nicht mehr verfolgen. In dieser Klassenmethode scheint es überhaupt keine überwachbaren Variablen zu geben.

In Java, also konkret in der Eclipse, wird mir wenigstens die lokal angelegte Kopie(r)variable "this" mit all' ihren Einzeldaten/-werten angezeigt.

Das Verfolgen, was in TSequence.upToPrevious mit dem dorthin geschickten Wert, konkret der dorthin geschickten Datenstruktur passiert, ist für mich jedoch essentiell, weil genau dort der Programmverlauf als nächstes bzw. derzeit als erstes auseinanderdriftet (vorher konnte ich ihn "auf Linie bringen").

Gibt es eine Möglichkeit, auch in dieser - überhaupt in Klassenmethoden - zu debuggen?

Vielen Dank für Eure Aufmerksamkeit!

Schöne Grüße

Delphi-Laie

Edit: Ich definierte behelfsweise und experimentell eine globale TSequence-Instanz, damit scheint es erstmal zu funktionieren, also die Datenstruktur auch in den Klassenmethoden vom Debugger abrufbar zu sein. Was für ein Gefrickel...

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Fr 10.03.17 12:48

Hallo Frühlingsrolle, vielen Dank, aber es ist nicht nötig, mir mehr zu helfen, als ich frage. Sowohl habe ich eine 1:1-Übersetzung beider Klassen (jedenfalls nach jetzigem Stand), als auch ist mir das Debuggen wohlbekannt. Ich wollte eigentlich wissen, ob jemand weiß, ob bzw. wie man an die lokale Variable gelangt, die an eine Methode übergeben wird, die keinen expliziten Parameter hat. Wie gesagt, die Eclipse zeigt mir "this" an. Daß es in / mit Delphi nicht möglich zu sein scheint, jedenfalls mit meinem derzeit verwendeten Delphi 4, ist eine der schwersten Enttäuschungen, die es mir je bereitete, wenn die größte überhaupt. Zum Glück habe ich bisher objektorientierte Programmierung immer vermieden, ich wußte wohl intuitiv, warum, denn so etwas ist indiskutabel. Wie wollte jemand unter diesen Voraussetzungen Software ernsthaft entwickeln und prüfen?

Frühlingsrolle hat folgendes geschrieben :

Meinst du mit Klassenmethoden:

Das war eine falsche Titulierung meinerseits, ich meinte natürlich nur die einfachen Methoden ohne vorangestelltes "class".

Gruß Delphi-Laie

Edit: Daß in setSize die übergebene Variable per Debugger beobachtet werden kann, ist klar. Nochmals: Es geht um die ohne übergebenen Parameter - jedenfalls nicht explizit übergebenen - wie z.B. "upToPrevious".

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Fr 10.03.17 13:52

Wie gesagt, Breakpoints setzen und dorthin die Programmausführung springen lassen kann ich auch.

Mit "self" kommt man auch an die in der Methode verarbeiteten Daten bzw. an die dort verarbeitete Klassenstruktur. Damit ist Delphi wieder mein bester Freund.

Lange Rede, leicht geschafft von der Debustrapaze kopierte ich nochmal Deine komplette Übersetzung, und nun sortiert es bestens. Tausend Dank!! Mein Sortierprogramm hat demnächst, müßte diese Woche noch bequem zu schaffen sein, einen weiteren Eintrag, und meine Dankesliste mehr als einen neuen.

Mal schauen, ob ich den Fehler noch finde, den ich beging.

Freundliche Grüße

Delphi-Laie

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

- Nachträglich durch die Entwickler-Ecke gelöscht -

Delphi-Laie · Verfasst: Fr 10.03.17 14:17

Frühlingsrolle hat folgendes geschrieben :

Du hattest den Löwenanteil zu übersetzen. Das bisschen an Unterstützung schadet nicht.

Kommen ja noch all' die eigentlichen Sortier-Unterprogramme hinzu. Wird in Kürze veröffentlicht werden. Auch heute bin ich fleißig.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme