Autor Beitrag
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mo 20.02.17 23:40 
Hallo Programmierfreunde!

Zur Zeit übersetze ich einen C++-Sortieralgorithmus nach Delphi, wozu ich dankenswerterweise in jener Diskussion die entscheidende Initialhilfe bekam. Ich komme genauso mühsam voran, wie sich das Eichhörnchen ernährt, aber es geht vorwärts. Doch nun scheitere ich an einem Konstrukt. Eine Datenstruktur, wie folgt typisiert:

ausblenden Quelltext
1:
2:
3:
4:
struct HeapShape {
std::bitset<kNumLeonardoNumbers> trees;
size_t smallestTreeSize;
};


(anscheinend so etwas wie ein Record in Delphi), wird als deklarierte Variable:

ausblenden Quelltext
1:
HeapShape shape					


an einer Stelle im Code wie folgt boole'sch aufgerufen:

ausblenden Quelltext
1:
2:
do {...}
while (shape.trees.any() && !shape.trees[0]);


Mit dem ".any ()" komme ich überhaupt nicht klar, finde das auch nicht im Internet und werde auch aus dem Laufverhalten nicht schlau, was das bezwecken soll. Wichtig scheint es aber zu sein.

Etwas ausführlicher, es ist natürlich in dem schon in der verlinkten Diskussion bekanntgewordenen Quellcode enthalten.

Weiß jemand, was mit diesem ominösen .any() abgefragt / aufgerufen wird?

Vielen Dank im voraus und freundlicher Gruß

Delphi-Laie


Zuletzt bearbeitet von Delphi-Laie am Di 21.02.17 23:35, insgesamt 2-mal bearbeitet
Frühlingsrolle
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2162
Erhaltene Danke: 399

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Di 21.02.17 02:14 
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
HeapShape = record
//struct HeapShape {
trees: set of "Bereich";
//std::bitset<kNumLeonardoNumbers> trees;
smallestTreeSize: Cardinal;
//size_t smallestTreeSize;
end;


Das std::bitset::any() geht davon aus, ob das set leer ist oder nicht. Es liefert true zurück, wenn mind. 1 Element vorhanden ist.

_________________
„Politicians are put there to give you the idea that you have freedom of choice. You don’t. You have no choice. You have owners. They own you. They own everything." (George Denis Patrick Carlin)

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 21.02.17 12:18 
user profile iconFrühlingsrolle hat folgendes geschrieben Zum zitierten Posting springen:
Das std::bitset::any() geht davon aus, ob das set leer ist oder nicht. Es liefert true zurück, wenn mind. 1 Element vorhanden ist.


Vielen Dank!

Nunja, etwas in dieser Art schwante mir schon, denn "any" bekomme ich natürlich auch übersetzt.

Nun tauchen aber doch noch (Nach-)Fragen auf: Wenn ohnehin jedes Element des Arrays geprüft wird, warum wird dann in der boole'schen Anweisung:

ausblenden Quelltext
1:
shape.trees.any() && !shape.trees[0])					


im zweiten Teil zusätzlich noch das Element Nr. 0 des Arrays auf "Befüllung" geprüft? "Bereich" ist nämlich ein boole'sches Array. Ist das redundant? Und erfaßt dieses "any" dann alle Elemente des Arrays außer dem nullten? Eigentlich müßten doch alle Elemente bei der any-Anweisung geprüft werden (jedenfalls, bis da erste gefunden wurde, das nicht leer ist), denn "any" kann vom zweiten Teil der Abfrage doch gar nichts wissen.

Ergänzung: Hier noch ein Pascal-Nagel mit Kopf:

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
function any(trees:Booleanarray):boolean;
var i:word;
begin
result:=false;
for i:=0 to high(trees) do if trees[i] then
  begin
  result:=true;
  break//oder exit
  end
end;


Ist das mit any gemeint?


Zuletzt bearbeitet von Delphi-Laie am Di 21.02.17 12:49, insgesamt 4-mal bearbeitet
Frühlingsrolle
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2162
Erhaltene Danke: 399

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Di 21.02.17 12:43 
Der zweite Ausdruck soll heissen, Nicht Erstes Element. Die Operatoren davor sind ein logisches Und.

_________________
„Politicians are put there to give you the idea that you have freedom of choice. You don’t. You have no choice. You have owners. They own you. They own everything." (George Denis Patrick Carlin)

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 21.02.17 12:48 
user profile iconFrühlingsrolle hat folgendes geschrieben Zum zitierten Posting springen:
Der zweite Ausdruck soll heissen, Nicht Erstes Element. Die Operatoren davor sind ein logisches Und.


Ja natürlich! Das not übersah ich mitnichten, interpretierte es nur falsch.

Ich habe noch eine Beispielfunktion für any im vorigen Beitrag angegeben. Ist das so richtig?
Frühlingsrolle
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 2162
Erhaltene Danke: 399

[Win NT] 5.1 x86 6.1 x64
[Delphi] 7 PE, 2006, 10.1 Starter, Lazarus - [C#] VS Exp 2012 - [Android API 15] VS Com 2015, Eclipse, AIDE - [C++] Builder 10.1
BeitragVerfasst: Di 21.02.17 13:01 
Ja, damit bin ich einverstanden. Ich wollte noch tippen, dass du statt des set ein array verwenden könntest, da es mehr Sinn macht, Da hast du sehr gut mitgedacht.

_________________
„Politicians are put there to give you the idea that you have freedom of choice. You don’t. You have no choice. You have owners. They own you. They own everything." (George Denis Patrick Carlin)

Für diesen Beitrag haben gedankt: Delphi-Laie
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1636
Erhaltene Danke: 232

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Di 21.02.17 13:35 
Hallo,

in Analogie zu der existierende Delphi Unit:
ausblenden C#-Quelltext
1:
2:
3:
4:
struct HeapShape {
std::bitset<kNumLeonardoNumbers> trees;
size_t smallestTreeSize;
};

Würde dort, statt eines Bitsets, ein Uint64 alternativ benutzt.
Bit 31 wäre 4.6x10^6 ( Weshalb das Original keine 8 Mio Elemente sortieren konnte) und 45 reicht für mehr 3.6x10^9 Elemente.
ausblenden Delphi-Quelltext
1:
2:
3:
4:
tHeapShape=record 
             BelegteLeonardoHeaps : UInt64;
             ErsterBelegterLHeap  : integer;
           end;

Das Any wäre ein (BelegteLeonardoHeaps = 0)
Es ist die Frage, ob Delphi nicht wie Freepascal auch BSR und BSL kennt, dann könnte man sich ErsterBelegterLHeapwohl sparen.

Gruß Horst

Für diesen Beitrag haben gedankt: Delphi-Laie
hydemarie
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 405
Erhaltene Danke: 50



BeitragVerfasst: Di 21.02.17 14:32 
Ja, shl und shr.

Für diesen Beitrag haben gedankt: Delphi-Laie
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 21.02.17 14:58 
Vielen Dank für die rege Beteiligung!

Vermutlich komme ich jetzt selbständig weiter.

Je mehr ich darüber nachdenke, desto entbehrlicher kommt es mir vor, das Array schon ab Index Null zu prüfen, sondern erst ab Index 1, weil das Element mit dem Index Null ohnehin explizit abgefragt wird. Ich werde das noch herausfinden.


Zuletzt bearbeitet von Delphi-Laie am Di 21.02.17 18:03, insgesamt 1-mal bearbeitet
Delphi-Laie Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1567
Erhaltene Danke: 221


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Di 21.02.17 18:03 
So, liebe Leute, der Algorithmus läuft jetzt erstmal zu meiner Zufriedenheit in Delphi, war mal wieder eine Zangengeburt mit deutlicher Tendenz zum Kaiserschnitt. Wenig überraschend: Es zeigt ein ähnliches Laufzeitverhalten wie schon mein erstes implementiertes Smoothsort (die Anzahl der Vergleiche ist etwas größer, die Anzahl der Verschiebungen etwas kleiner als beim schon implementierten Smoothsort).

Bevor ich noch mehr Anpassungen für mein Sortierkino vornehme, hier als Dankeschön für Eure Hilfe die Pascal-"Rohversion", vermutlich besonders für Horst interessant:

Vorbereitender Code:

ausblenden Delphi-Quelltext
1:
2:
3:
var leonardo:array [0..19of cardinal;
...
leonardo[0]:=1;leonardo[1]:=1;for x:=2 to high(leonardo) do leonardo[x]:=succ(leonardo[pred(x)]+leonardo[x-2]);


Aufruf (Anfangs- und Endindex der zu sortierenden Menge, Ende:=Elementeanzahl-1, wahrscheinlich funktioniert das auch mit Startindizes>0):

ausblenden Delphi-Quelltext
1:
Smoothsort(0,Ende)					


Eigentlicher Code:

ausblenden volle Höhe 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:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
procedure smoothsort(links,rechts:word);

type
 Booleanarray=array[0..45]of boolean;
 HeapShape=record
 SmallestTreeSize:word;
 trees:Booleanarray
 end;

var i:word;
shape:HeapShape;

  procedure shift_left(var a:booleanarray;shift:word);
  var i:word;
  begin
  for i:=high(a) downto shift do a[i]:=a[i-shift];
  for i:=0 to pred(shift) do a[i]:=false
  end;

  procedure shift_right(var a:booleanarray;shift:word);
  var i:word;
  begin
  for i:=0 to high(a)-succ(shift) do a[i]:=a[i+shift];
  for i:=high(a)-shift to high(a) do a[i]:=false
  end;

  function FirstChild(root,size:word):word;
  begin
  result:=pred(root)-Leonardo[size-2]//pred(root) ist SecondChild
  end;

  procedure RebalanceSingleHeap(root,size:word);
  var first,second,largerChild,ChildSize:word;
  begin
  while size>1 do
    begin
    first:=FirstChild(root,size);
    second:=pred(root);//SecondChild
    if Menge[first].schluessel<Menge[second].schluessel then
      begin
      largerChild:=second;
      ChildSize:=size-2
      end
    else
      begin
      LargerChild:=first;
      ChildSize:=pred(size)
      end;
    if Menge[root].schluessel>Menge[LargerChild].schluessel then exit;//oder break
    tausche(root,LargerChild);
    root:=LargerChild;
    size:=ChildSize
    end
  end;

  procedure LeonardoHeapRectify(l,r:word;lokalShape:HeapShape);

    function largerChild(root,size:word):word;
    var first,second:word;
    begin
    first:=FirstChild(root,size);
    second:=pred(root);//SecondChild
    if Menge[first].schluessel>Menge[second].schluessel
    then result:=first
    else result:=second
    end;

  var itr,lastheapsize,toCompare,largeChild,priorHeap:word;
  begin
  itr:=pred(r);
  lastheapsize:=0;//Compilerwarnung vermeiden
  while true do
    begin
    lastheapsize:=lokalshape.smallestTreeSize;
    if itr-l=pred(Leonardo[lastHeapSize]) then break;
    toCompare:=itr;
    if lokalshape.smallestTreeSize>1 then
      begin
      largeChild:=largerChild(itr,lokalshape.smallestTreesize);
      if Menge[toCompare].schluessel<Menge[largeChild].schluessel
      then toCompare:=largeChild
      end;
    priorHeap:=itr-Leonardo[lastHeapSize];
    if Menge[toCompare].schluessel>Menge[priorHeap].schluessel then break;
    tausche(itr,priorHeap);
    itr:=priorHeap;
      repeat
      shift_right(lokalshape.trees,1);
      inc(lokalshape.SmallestTreeSize)
      until lokalshape.trees[0];
    end;
  RebalanceSingleHeap(itr,lastHeapSize)
  end;

  procedure LeonardoHeapAdd(l,r,heapend:word);
  var islast:boolean;
  begin
  if not shape.trees[0then
    begin
    shape.trees[0]:=true;
    shape.smallesttreesize:=1
    end
  else
    if shape.trees[1and shape.trees[0then
      begin
      shift_right(shape.trees,2);
      shape.trees[0]:=true;
      inc(shape.smallestTreeSize,2)
      end
    else
      if shape.smallestTreeSize=1 then
        begin
        shift_left(shape.trees,1);
        shape.smallestTreeSize:=0;
        shape.trees[0]:=true
        end
      else
        begin
        shift_left(shape.trees,pred(shape.smallestTreeSize));
        shape.trees[0]:=true;
        shape.smallestTreeSize:=1
        end;
  islast:=false;
  case shape.smallestTreeSize of
    0:if succ(r)=heapend then islast:=true;
    1:if (succ(r)=heapEnd) or (r+2=heapEnd) and not shape.trees[1then isLast:=true;
      else if heapEnd-succ(r)<=leonardo[pred(shape.smallestTreeSize)] then isLast:=true
    end;
  if isLast
  then LeonardoHeapRectify(l,succ(r),shape)
  else RebalanceSingleHeap(r,shape.smallestTreeSize)
  end;

  procedure LeonardoHeapRemove(l,r:word);

    function any:boolean;
    var i:word;
    begin
    for i:=1 to high(shape.trees) do if shape.trees[i] then//ab 1, weil 0 irrelevant ist
      begin
      result:=true;
      exit//oder break
      end;
    result:=false
    end;

  var HeapOrder,leftHeap,RightHeap:word;
  AllButLast:HeapShape;
  begin
  if shape.smallestTreeSize<=1 then
    begin
      repeat
      shift_right(shape.trees,1);
      inc(shape.SmallestTreeSize);
      until shape.trees[0or not any;
    exit
    end;
  HeapOrder:=shape.SmallestTreeSize;
  shape.trees[0]:=false;
  shift_left(shape.trees,2);
  shape.trees[1]:=true;
  shape.trees[0]:=true;
  dec(shape.SmallestTreeSize,2);
  LeftHeap:=FirstChild(r,HeapOrder);
  RightHeap:=pred(r);//SecondChild
  allButLast:=shape;
  inc(allButLast.SmallestTreeSize);
  shift_right(allButLast.Trees,1);
  LeonardoHeapRectify(l,succ(leftHeap),allButLast);
  LeonardoHeapRectify(l,succ(rightHeap),shape)
  end;

begin
for i:=0 to high(shape.trees) do shape.trees[i]:=false;
shape.smallesttreesize:=0;
for i:=links to rechts do LeonardoHeapAdd(links,i,succ(rechts));
for i:=rechts downto links do LeonardoHeapRemove(links,i)
end;


Update: Ich war etwas zu voreilig, es gibt doch noch irgendeinen klitzekleinen Fehler, den ich jetzt suchen werde.

Update 2: Der Fehler war bald gefunden: In der Hauptprozedur muß LeonardoHeapAdd nicht mit

ausblenden Delphi-Quelltext
1:
LeonardoHeapAdd(links,i,rechts);					

, sondern mit

ausblenden Delphi-Quelltext
1:
LeonardoHeapAdd(links,i,succ(rechts));					


aufgerufen werden. Ist schon im großen Codeblock korrigiert.

Update 3: Kleine Codeoptimierungen an/in und im Kontext von "any"

Update 4: Funktion "RebalanceSingleHeap" wurde in Prozedur umgewandelt, weil kein Ergebnis benötigt wird.

Update 5: Weitere kleine Codeverbesserungen (überflüssige Variablen entfernt, lastheapsize initialisiert)

Für diesen Beitrag haben gedankt: Frühlingsrolle