frage zu bit-operations-algo



  • hi,
    stehe momentan etwas aufm schlauch, hoffe jemand kann mit ner idee weiterhelfen:

    ich braeuchte einen algo., der mir fuer eine bestimmte Anzahl von Bit-Woertern folgendes macht:

    Bitwort_0 = 01000
    Bitwort_1 = 01000
    Bitwort_2 = 00100
    Bitwort_3 = 00010
    Bitwort_4 = 00010
    ...
    Bitwort_N = 10000
    ------------------
    Ergebnis: 01010

    Das Ergebnis-Bitwort hat also an i-ter Stelle ein gesetztes Bit, wenn es mindestens zwei Bitwoerter gibt, die an i-ter Stelle ein gesetztes Bit haben.

    Ein Tipp waere schoen.
    Danke,
    Gruss.



  • noch ne kleine anmerkung zu obigem:

    es ist natuerlich zusaetzlich noch das ziel, dies in "schnellster" form umzusetzen.



  • vorab sorry dass ich hier staendig nachtraege poste.

    will nur wissen ob es schneller geht als folgendes:

    ergenis |= ( c0 & c1) |
    ((c0|c1) & c2) |
    ((c0|c1|c2) & c3) |
    ((c0|c1|c2|c3) & c4);

    (uebrigens die bitwoerter c0 bis c4 haben immer nur ein bit gesetzt)

    vielen dank.

    gruss.



  • Wenn die gleichgesetzten Bits immer in hintereinanderfolgenden Variablen stehen, könnte evtl folgendes gehen (nicht getestet):

    int result = (c0&c1) | (c1&c2) | (c2&c3) | (c3&c4);
    


  • pepe75 schrieb:

    ergenis |= ( c0 & c1) |
    ((c0|c1) & c2) |
    ((c0|c1|c2) & c3) |
    ((c0|c1|c2|c3) & c4);

    Wenn ich das ganze für fünf Variable aufstelle und zusammenfasse komm ich auf das selbe. Sieht also ganz gut aus. Zudem sind bitweise Operationen sehr schnell, also sollte das schon verdammt schnell sein 😉
    (wieso eigentlich "ergenis |= ..." und nicht "ergenis = ..."?)
    Vielleicht ist auch das schneller:

    x = c0
    ergenis = x & c1;
    x |= c1;
    ergenis |= x & c2;
    x |= c2;
    ergenis |= x & c3;
    x |= c3;
    ergenis |= x & c4;
    

    pepe75 schrieb:

    (uebrigens die bitwoerter c0 bis c4 haben immer nur ein bit gesetzt)

    Glaube nicht das man mit der Eigenschaft den Algo noch beschleunigen kann. Aber lass mich gerne eines besseren belehren :p



  • Für eine beliebige Anzahl an Elementen:

    char check(char* test, size_t elems)
    {
        char result = 0;
        const char* end = test + elems;
        char* p1 = test;
        char* p2;
        while(p1 != end)
        {        
            p2 = p1 + 1;
            while(p2 != end)
            {
                result |= (*p1 & *p2);
                ++p2;
            }
            ++p1;
        }
        return result;
    }
    


  • danke der antworten.
    while-schleifen-loesung ist (nicht boese gemeint) glaube ich nicht so mein fall, obwohl vielleicht fuer allgemein-fall nuetzlich.

    es geht genauer um eine poker-hand evaluations funktion fuer video-poker.
    da dies fuer ne simulation genutzt werden soll, brauche ich entsprechend schnelle funktionen. fuer bestimmte tests brauchte ich obige funktion, die nur auf 5 bit-woerter beschraenkt ist.

    MfG.



  • pepe75 schrieb:

    obwohl vielleicht fuer allgemein-fall nuetzlich.

    Hier wird lineare durch quadratische Komplexität ersetzt. Das kann kaum als Verbesserung gelten.



  • camper schrieb:

    pepe75 schrieb:

    obwohl vielleicht fuer allgemein-fall nuetzlich.

    Hier wird lineare durch quadratische Komplexität ersetzt. Das kann kaum als Verbesserung gelten.

    Stimmt!
    Man könnte natürlich meinen Ansatz auch mit einer Schleife realisieren, welche dann auch eine lineare Laufzeit hat. Aber bei nur fünf Variablen ist es von Hand fast einfacher... aber das ist geschmackssache, da der Compiler eine Schleife von 0...5 wohl auch "ausschreiben" würde 😉



  • Alternativ funktioniert auch so eine Art Bucketsort.



  • camper schrieb:

    pepe75 schrieb:

    obwohl vielleicht fuer allgemein-fall nuetzlich.

    Hier wird lineare durch quadratische Komplexität ersetzt. Das kann kaum als Verbesserung gelten.

    Okay, dann vielleicht so:

    char check(char* test, size_t elems)
    {
        const char* end = test + elems;
        char result = 0, tmp = 0;
        while(test != end)
        {
            result |= (tmp & *test);
            tmp |= *test;
            ++test;
        }       
        return result;
    }
    


  • Tachyon schrieb:

    Nenne mir eine Alternative für den im Eingangspost angegebenen Fall von N Elementen.

    so wie der vorschlag von lagalopex, aber nur mit einer schleife
    🙂



  • fricky schrieb:

    Tachyon schrieb:

    Nenne mir eine Alternative für den im Eingangspost angegebenen Fall von N Elementen.

    so wie der vorschlag von lagalopex, aber nur mit einer schleife
    🙂

    Das habe ich nie geschrieben. 😃



  • Bucketsort ist möglich, allerdings bedeutet das je Datenwort sowohl eine Lese- als auch eine Schreiboperation in den Speicher - während bei der einfachen Version Schreibvorgänge trivialerweise nur mit Registern arbeiten. Zudem sind Schreibvorgänge in den gleichen Speicherbereich bei den meisten Rechnerarchitekturen nicht oder nur beschränkt parallelisierbar - damit ist Bucketsort nur schwer zu vektorisieren. Eine Parallelisierung dagegen ist offensichtlich leicht möglich - nützt aber nur etwas, wenn wenigstens Schreibvorgänge in unterschiedliche Speicherbereiche (jeder Thread nutzt seine eigene Buckets die erst zum Schluss zusammengeführt werden) parallel möglich sind.

    Der einfache Algorithmus ist hinsichtlich der Operationen je Datenwort im Grunde schon optimal, leidet aber darunter, das er nicht direkt parallelisierbar oder gar vektorisierbar ist, zudem kommt eine Umstellung der Einzeloperationen (out of order execution) nicht in Betracht. Allerdings kann man auch einen rekursiven Algorithmus formulieren.

    unsigned char check(const unsigned char* data, std::size_t N)
    {
        struct once_twice_t
        {
            unsigned char once, twice;
            once_twice_t(unsigned char once, unsigned char twice) : once(once), twice(twice) {}
        };
        struct
        {
            once_twice_t operator()(const unsigned char* data, std::size_t N) const
            {
                if ( N >= 2 )
                {
                    once_twice_t first = ( *this )( data, N / 2 );
                    once_twice_t second = ( *this )( data + N / 2, N - N / 2 );
    // ein bit in .once ist gesetzt, wenn das bit in wenigstens einem Element der Sequenz gesetzt ist
    // ein bit in .twice ist gesetzt, wenn das bit in wenigstens zwei Elementen der Sequenz existiert
    // damit ergeben sich die Vernüpfungsregeln für die Ergebnise mehrere Sequenzen:
                    return once_twice_t( first.once | second.once, first.twice | second.twice | ( first.once & second.once ) );
                }
                else if ( N == 1 )
                    return once_twice_t( *data, 0 );
                else
                    return once_twice_t( 0, 0 );
            }
        } apply_recursive;
        return apply_recursive( data, N ).second;
    }
    

    Haben wir einen rekursiven Algorithmus, ist es trivial, diesen für andere Aufteilungsschemata anzupassen, kombiniert mit dem ursprünglichen einfachen Algorithmus können wir dann sehr leicht und effizient vektorisieren:
    Zur Demonstration verarbeite ich jetzt 4 Bytes pro Schritt. Der Einfachheit halber mache ich ein paar Annahmen - sollten diese nicht erfüllt sein, muss man entsprechend (vergleichsweise trivial) anpassen:
    1. unsigned hat die Größe von 4 char, kein Padding oder Traprepräsentationen
    2. *data ist hinreichend ausgerichtet für unsigned int, zudem verstößt der Zugriff per unsigned* nicht gegen Aliasregeln (oder ist durch Plattformgarantien gedeckt)
    3. N ist ein Vielfaches von 4

    unsigned char check(const void* data, std::size_t N)
    {
        const unsigned* data_p = static_cast< const unsigned* >( data );
        std::size_t n = N / 4;
    // ich bin faul und benutze einfach Tachyons Version:
        const unsigned* end = data_p + n;
        unsigned result = 0, tmp = 0;
        while(data_p != end)
        {
            result |= (tmp & *data_p);
            tmp |= *data_p;
            ++data_p;
        }
    // jetzt aus result und tmp das richtige Resultat ganz analog zum rekursiven Algorithmus ermitteln      
        unsigned char x[4];
        memcpy( x, &tmp, sizeof x );
        unsigned char once[2] = { tmp[0] | x[1], x[2] | x[3] };
        memcpy( x, &result, sizeof x );
        unsigned char twice[2] = { x[0] & x[1], x[2] & x[3] };
        return ( once[0] & once[1] ) | twice[0] | twice[1];
    }
    

    Größere Wortbreiten sind natürlich ebnso möglich, ein Einsatz etwa von SSE-Instruktionen ist absolut denkbar. Es lohnt aber von vornherein nur, wenn die Datenmenge hinreichend groß ist.

    Edit: Code korrigiert und Bezeichner anders gewählt



  • Geht das überhaupt?

    camper schrieb:

    const unsigned* data_p = static_cast< const unsigned* >( data );
    

    Irgendwie verstehe ich die Überleitung von dem rekursiven Teil in den iterativen Teil nicht. Wo liegt der Sinn?

    PS: Mir ist einigermaßen klar, was der rekursive Algorithmus tut. Nur sehe ich daran, was die Komplexität betrifft, wieder einen Rückschritt. Die ist log(N)*N, wenn ich das richtig durchblicke.
    Dann hast Du meine Version vektorisiert. Das ist auch noch klar. Nur den Sinn der Überleitung von rekursiv -> iterativ verstehe ich nicht. Wozu gibst Du die rekursive Version erst an?



  • Tachyon schrieb:

    Geht das überhaupt?

    camper schrieb:

    const unsigned* data_p = static_cast< const unsigned* >( data );
    

    Irgendwie verstehe ich die Überleitung von dem rekursiven Teil in den iterativen Teil nicht. Wo liegt der Sinn?

    Ich habe den Paramtertyp der Funktion auf const void* geändert.

    Sorry, hab einen kleinen Fehler gemacht, es muss im zweiten Fall heißen (once hängt von tmp ab):

    // jetzt aus result und tmp das richtige Resultat ganz analog zum rekursiven Algorithmus ermitteln      
        unsigned char x[4];
        memcpy( x, &tmp, sizeof x );
        unsigned char once[2] = { tmp[0] | x[1], x[2] | x[3] };
        memcpy( x, &result, sizeof x );
        unsigned char twice[2] = { x[0] & x[1], x[2] & x[3] };
        return ( once[0] & once[1] ) | twice[0] | twice[1];
    

    Der Sinn des rekursiven Algorithmus liegt darin, die Regeln zu Finden, die es erlauben, Subsequenzen separat zu berechnen und diese Einzelergebnissedirekt zum Gesamtergebnis zu verknüpfen (das return-Statement entspricht nicht zufällig exakt dem Ausdruck für die Berechnung von .twice).
    Ich empfinde es als einfacher, erst einmal allgemein einen rekursiven Algorithmus zu entwickeln, als direkt bei der Vektorisierung noch zusätzlich mit einem recht starren Speicherlayout kämpfen zu müssen. Jedenfalls glaube ich, dass der zweite Code ohne Vorüberlegungen erheblich schwerer zu verstehen ist.

    PS: Du hast hinsichtlich der Komplexität übrigens unrecht. Es ist O(N+log N) = O(N) ebenfalls linear.



  • camper schrieb:

    unsigned char once[2] = { x[0] | x[1], x[2] | x[3] };
    

    Hmm, wenn ich Dich richtig verstehe, hast Du den rekursiven Algorithmus also angeführt, um die grundlegende Regel für das zerlegen in Sequenzen aufzuzeigen.
    Dadurch soll man dann (anhand der simplen rekursiven Lösung) die Vorschrift für eine iterative Lösung besser erkennen können, oder wie?
    Ich gebe zu, es wird so einigermaßen gut deutlich, aber ich denke denoch, dass es viele nicht verstehen werden.

    camper schrieb:

    PS: Du hast hinsichtlich der Komplexität übrigens unrecht. Es ist O(N+log N) = O(N) ebenfalls linear.

    Jo stimmt. Irgendwie habe ich da eine Schleife zu viel gesehen. 😞



  • Tachyon schrieb:

    Ich gebe zu, es wird so einigermaßen gut deutlich, aber ich denke denoch, dass es viele nicht verstehen werden.

    Das liegt dann entweder an der Schwierigkeit der Sache selbst (die zwangsweise größer ist als der Ursprungsalgorithmus) oder mangelnder Erklärungskompetenz meinerseits - Letzteres könnte aber kompensiert werden, wenn ein Anderer ein bessere Erklärung liefert.


Log in to reply