C++: Bitset Addition / Performance Optimieren
FMFlash 17.01.2004 - 14:23 1853 10
FMFlash
tranceCoder
|
Da in den Bitsets die Grundrechnungs-Operatoren wie +, - usw nicht implementiert sind aber doch benötigt werden hab ich mich mal daran gemacht einen einfachen Additionsalgorithmus nach den allgemeinen Regeln der Addition in das Template zu basteln: bitset<_N>& operator+=(const bitset<_N>& _R){
bitset<_N> _S;
unsigned long _pp;
for (unsigned long _p = _Nw; _p < _N; _p++){
if ((test(_p) == 1 && _R[_p] == 1)){
do{
_pp = _p + 1;
(test(_p) == 1 && _R[_p] == 1) ? true : _S[_p] = 0;
((_pp) < _N) ? (_S[_pp] = 1) : false; _p++;
}while(_S[_p] == 1 && (_R[_p] == 1 || test(_p) == 1));
}else{(test(_p) == 1 || _R[_p] == 1) ? _S[_p] = 1 : false;}}
(*this) = _S;
return (*this);
}
Er funktioniert zwar, ist aber klarerweise extrem langsam. Als ersten Ansatz für die Überlegung war es aber recht hilfreich. Für mehr Geschwindigkeit mussten alle "manuellen" Tätigkeiten weg (schon allein die Zähler bedeuten Additionen innerhalb einer Addition), also Arbeiten nur mit Binären Operatoren. Dabei herausgekommen ist folgendes: bitset<_N>& operator+=(const bitset<_N>& _B){
bitset<_N> _C, _D, _E;
_C = (*this); _D = (*this);
_C &= _B; _C <<= 1; _D ^= _B;
while (_C.none()==false){
_E = _C; _C &= _D;
_C <<= 1; _D ^= _E;}
(*this) = _D;
return (*this);
}
Das läuft schon sehr schnell, ist einer Addition auf zb einen normalen int aber immernoch etwas unterlegen. Jetzt suche ich noch Anregungen und Verbesserungsvorschläge von den Experten zwecks Optimierung (oder einem anderen Konzept?). tia!
|
Ringding
Pilot
|
Ich hab keine Ahnung, was du da tun willst. Möglicherweise |= nachimplementieren?
EDIT: Oder das:?
to_ulong() + rhs.to_ulong()
Bearbeitet von Ringding am 17.01.2004, 22:55
|
FMFlash
tranceCoder
|
Ich hab keine Ahnung, was du da tun willst. Möglicherweise |= nachimplementieren?
EDIT: Oder das:?
to_ulong() + rhs.to_ulong() Das erste: Nein Das zweite: Jein - siehe unten Ich möchte ganz einfach addieren (wie schon gesagt). | ist ja bereits implementiert, aber damit sind keine arithmetischen Additionen möglich. Bsp: bitset<4> a; a = 10; (1010) a |= 9; (1001) Ergibt 1011 = 11 - nicht 19 to_ulong + to_ulong funktioniert auch nur solange man sich in einem Zahlenbereich bewegt in dem man die Rechnung genausogut mit herkömmlichen Variablen rechnen könnte. Versuch mal auf ein bitset<1024> das Hausnummer bereits 500 Bit nutzt um eine Zahl abzubilden to_ulong() anzuwenden. 
|
mat
AdministratorLegends never die
|
schwierig etwas über deinen code zu sagen, weil ohne genauen definition von bitset kann man sich ja nur denken was deine überladenen operatoren so machen.
vielleicht ein konzeptvorschlag, der (zB) schon implementiert sein könnte: nicht bitweise arbeiten sondern die bitoperationen auf 32bit level durchführen.
|
Ringding
Pilot
|
In ulong-Blöcken zu arbeiten wird wohl am besten sein - beide Operanden in ein ulong-Array konvertieren (müsste mit & und >> recht schnell gehen), in einer simplen Schleife die beiden addieren, nachher wieder zurück ins Bitset mit << und |.
|
FMFlash
tranceCoder
|
schwierig etwas über deinen code zu sagen, weil ohne genauen definition von bitset kann man sich ja nur denken was deine überladenen operatoren so machen. Das Bitset ist ein in der C++ STL definiertes Template mit dem sich beliebig lange "Ketten" von Bits verwalten lassen. Damit ist man also nicht auf den Rahmen den die herkömmlichen Datentypen bieten beschränkt. Der Operator += ist in dem Fall nicht überladen da er per Standard nicht implementiert ist. Wenn ich so ein Bitset allerdings zur Darstellung einer Zahl verwende statt für zb eine lange liste von Flags fehlen mir die Grundrechenarten -> hier kommt mein Code ins Spiel. In ulong-Blöcken zu arbeiten wird wohl am besten sein - beide Operanden in ein ulong-Array konvertieren (müsste mit & und >> recht schnell gehen), in einer simplen Schleife die beiden addieren, nachher wieder zurück ins Bitset mit << und |. Hm, worin liegt da der Geschwindigkeitsvorteil? Der gleiche Additionsalgorithmus den ich jetzt verwende müsste da (neben der Verwaltung des ulong-arrays) mehrmals durchgeführt werden.
|
Ringding
Pilot
|
Hm, worin liegt da der Geschwindigkeitsvorteil? Dass deine Schleife 32 (oder 64) mal so oft durchlaufen werden muss.
|
FMFlash
tranceCoder
|
Dass deine Schleife 32 (oder 64) mal so oft durchlaufen werden muss. "Meine Schleife" ist Teil der Addition und arbeitet nur solange der sog. Carry nicht 0 ist. Das wird ohne einen komplett anderen Ansatz (ich kenne keinen schnelleren) nicht wegzurationalisieren sein. Addiere ich zb 1 zu einem 1024 Bit langen Bitset mit dem Inhalt 1100 wird diese Schleife kein einziges mal durchlaufen. Bei 1001 + 1 wäre es 1 mal usw, sprich die länge des Bitsets bestimmt lediglich die maximale Anzahl von durchläufen dieser Schleife, nicht die Mindestanzahl!
|
Ringding
Pilot
|
Gut, aber diese Optimierung (abbrechen, wenn nur mehr 0 kommt), kann man mit größeren Worten ja genauso machen.
|
FMFlash
tranceCoder
|
Gut, aber diese Optimierung (abbrechen, wenn nur mehr 0 kommt), kann man mit größeren Worten ja genauso machen. Optimierung ist es in dem Sinn ja noch keine, nur eine Regel der Addition. Ich rechne mal eine einfache Addition nach dem Algorithmus durch, vielleicht wird es dann deutlich: (Alle Variablen sind vom Typ bitset mit der Länge _N die der Länge des this-bitsets entspricht) a: 11011 b:+ 00001 c1: 00010 - a&b << 1 d1: 11010 - a^b - hier beginnt die schleife. wäre c1 jetzt 0, also gibt es keinen "rest", ist die rechnung beendet (bsp 01^10 = 11) c2: 00100 - c1&d1 << 1 d2: 11000 - c2^d1 c3: 00000 - c2&d2 << 1 d3: 11100 - c3^d2 - schleife bricht ab ergebnis = 11100 Worin jetzt der Vorteil liegen soll diesen Vorgang auf Teilstücke zu je 32 Bit aufzusplitten leuchtet mir nicht ganz ein.
|
Ringding
Pilot
|
Die Frage kann man jetzt wohl nur noch durch Benchmarking klären. Vielleicht komm ich ja mal dazu.
|
Anmeldung