Merkwürdiges Konstrukt in C++-Quelltext: .any()

Delphi-Laie · 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:

markieren

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:

markieren

Quelltext

1:	HeapShape shape

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

markieren

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

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

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

Delphi-Laie · 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:

markieren

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:

markieren

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?

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

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

Delphi-Laie · 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?

Delphi-Laie · Ehemaliges Mitglied Erhaltene Danke: 1

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

Horst_H · Verfasst: Di 21.02.17 14:35

Hallo,

in Analogie zu der existierende Delphi Unit:

markieren

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.

markieren

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

hydemarie · Beiträge: 475 Erhaltene Danke: 51

Ja, shl und shr.

Delphi-Laie · 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.

Delphi-Laie · 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:

markieren

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):

markieren

Delphi-Quelltext

1:	Smoothsort(0,Ende)

Eigentlicher Code:

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:
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[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//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[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);//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

markieren

Delphi-Quelltext

1:	LeonardoHeapAdd(links,i,rechts);

, sondern mit

markieren

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)

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme