Autor |
Beitrag |
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 21.02.17 00: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:
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:
Quelltext
an einer Stelle im Code wie folgt boole'sch aufgerufen:
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 Mi 22.02.17 00:35, insgesamt 2-mal bearbeitet
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Di 21.02.17 03:14
- Nachträglich durch die Entwickler-Ecke gelöscht -
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 21.02.17 13:18
Frühlingsrolle hat folgendes geschrieben : | 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:
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:
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 13:49, insgesamt 4-mal bearbeitet
|
|
Frühlingsrolle
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Di 21.02.17 13:43
- Nachträglich durch die Entwickler-Ecke gelöscht -
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 21.02.17 13:48
Frühlingsrolle hat folgendes geschrieben : | 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
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Di 21.02.17 14:01
- Nachträglich durch die Entwickler-Ecke gelöscht -
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 21.02.17 14:35
Hallo,
in Analogie zu der existierende Delphi Unit:
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.
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
Beiträge: 481
Erhaltene Danke: 51
|
Verfasst: Di 21.02.17 15:32
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 21.02.17 15: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 19:03, insgesamt 1-mal bearbeitet
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: Di 21.02.17 19: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:
Delphi-Quelltext 1: 2: 3:
| var leonardo:array [0..19] of 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):
Delphi-Quelltext
Eigentlicher Code:
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] 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); 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; 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); 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; 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[0] then begin shape.trees[0]:=true; shape.smallesttreesize:=1 end else if shape.trees[1] and shape.trees[0] then 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[1] then 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 begin result:=true; exit 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[0] or 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); 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
Delphi-Quelltext 1:
| LeonardoHeapAdd(links,i,rechts); |
, sondern mit
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)
|
|
|