3. Dynamisches <bitset>

Dynamisches <bitset>

  • S

    Hallo,

    ich habe ein kleines Problem mit <bitset>. Ich habe folgenden Code geschrieben:

    template<uint64_t N_T>
    bool generate( bitset<N_T>& rand_bits, uint64_t n, uint64_t N )
{
    for( uint64_t i=0; i<n; ) {
        uint64_t rand_pos = gsl_rng_get( rng ) % N;
        if( rand_bits.test( rand_pos ) == false ) {
            rand_bits.set( rand_pos );
            i++;
        }
    }

    return true;
}

int main( int argc, char *argv[] )
{
    if( argc < 3 ) {
        cerr << "To few arguments!\n";
        return 1;
    }
    uint64_t n = (uint64_t)atoll( argv[1] );
    uint64_t N = (uint64_t)atoll( argv[2] );
    cout << "n: " << n << endl;
    cout << "N: " << N << endl;

    const uint64_t NN = N;
    bitset<NN> bit_samples;
    generate( bit_samples<NN>, n, N );

    return 0;
}

    Der Compiler meckert:
    error: non-constant NN' cannot be used as template argument error: ISO C++ forbids declaration ofbit_samples' with no type

    Wie bekomme ich das hin?

    Viele Grüße
    Bastian

    0
  • H

    Wie bekomme ich das hin?

    Mit bitsets gar nicht. Der non-type-Parameter eines bitsets muss eine integrale Compilezeitkonstante sein. Ein über Kommandozeilenparameter angegebener Wert kann aber natürlich keine Compilezeitkonstante sein (der Wert steht ja erst zu dem Zeitpunkt fest, wo jemand das Programm startet. Da ist der Compilerlauf natürlich längst abgeschlossen).

    Falls du keine günstige Maximlalänge hast, bleibt dir nur ein dynamischer Container wie z.B. vector<bool> oder vector<char>.

    0
  • S

    Dann kann ich meinen Ansatz ja total vergessen.
    Dann beschreibe ich noch mal was ich eigentlich machen wollte:

    Ich benötige ein binäres File, in dem jedes Bit eine Randomzahl repräsentiert.
    Beispiel: Ich benötige z.B. 2 Zahlen zwischen 0 und 7, dann erhalte vielleicht 2 und 5. Dazu setze ich jetzt einfach Bit 2 und 5 in meinem Bitset auf true und erhalte somit 001001000. Man könnte sich jetzt natürlich auch einfach 2 und 5 in einem vector<int> merken, dafür benötige ich dann aber schon 2*4 Byte Platz. In der Praxis werden es wahrscheinlich 100*106 Zufallszahlen sein. Also ca. 100MB im Bitset bzw. 3,2GB im Vector. Das macht dann schon einen erheblichen Unterschied.
    Ein Bitweises Seeken ist nicht nötig. Es wird höchstens am Ende schwierig, wenn 1 bis 7 Bytes übrig sind.
    Da ich mir allerdings noch ca. 1000 dieser Files anlegen möchte kann ich nicht mal die 100 MB im Speicher halten. Ich habe mir dann gedacht, dass ich dann immer jeweils nur 1000 Byte aus einem Bitset im Speicher behalte und die Bitsetfiles dann sequentiell in 1000 Byte-Schritten abarbeite.

    Ich muss also Bitfiles schreiben und auslesen können.

    Viele Grüße
    Bastian

    0
  • H

    Hallo,
    was spricht jetzt genau gegen std::vector<bool>?

    0
  • I

    Wie groß ist denn die Dichte deiner Zufallszahlen?

    Vielleicht ist ja eine dünn besetzte Matrix eine Möglichkeit, die Datenmenge klein zu halten

    Wie Groß soll den der Zahlenbereich sein?
    0-100 und davon 100*106 Zufallszahlen.

    Man könnte jetzt den Zahlenbereich als quasi dünnbesetzt betrachten. Zweitens wäre ein Paging möglich.

    32-32-32-32 (128) [78,99] würde dann 0-0-xx-xx

    oder

    1. 32-32-32-32 [78] würde dann 0-0-xx-0
    2. 32-32-32-32 [99] würde dann 0-0-0-xx

    Wobei sich Paging und dünnbestzt fast aufheben.
    Ist nur ein Gedankengang

    0
  • S

    HumeSikkins schrieb:

    Hallo,
    was spricht jetzt genau gegen std::vector<bool>?

    Nichts, ich weiß nur nicht wie ich die Bits in ein File schreibe und danch wieder einlese.

    0
  • S

    idefix schrieb:

    Wie groß ist denn die Dichte deiner Zufallszahlen?
    [...]

    Ich denke, die Dichte ist nicht vorhersehbar.

    Folgende Anforderungen habe ich:
    - Es sollen n Zufallszahlen aus einem Bereich von 0...N gezogen werden.
    - Dabei dürfen keine Wiederholungen auftreten.
    - Die Zahlen sollen aufsteigend sortiert sein.

    Zu erwartende Größenordnungen:
    n = 10 000 000
    N = 100 000 000

    0
  • I

    Vorschlag:

    Quasi Paging:

    Vector<bitset<32>>

    N/32 ist gleich der Index Vector
    N%32 gleich gesetztes bit des Bitsets

    Überlegung:

    Index 24 / 32 = 0
    bit = 24 % 32= 24

    Index 1000 / 32 = 31
    bit = 1000 % 32 = 8

    Speichern:

    for(i=0;i<Vector.size();i++)
    {
    save_to_bin_file(Vector[].to_ulong());
    }

    laden: Naja, andersrum halt:

    Anmerkung:
    The member function throws overflow_error if any bit in the bit sequence has a bit value that cannot be represented as a value of type unsigned long. Otherwise, it returns the sum of the bit values in the bit sequence.

    Man könnte noch ein dünnbesetzte Matrix anstelle des Vectors nehmen. Hm, weiß nicht ob sich das wirklich lohnt

    0
  • I

    oder map<int,bitset<32>>

    0
  • S

    Welchen Vorteil bietet in diesem Fall <map> geneüber <vector>?

    0
  • I

    Ein vector ist ein geschlossener Bereich, dass heißt wenn das bitset nicht gebraucht wird ist es troztdem vorhanden. Eine Map legt nur auf bedarf an. Du kannst also die Lücken aus nutzen. Zweiter Vorteil um kopiererei, wegen dynamisch, entfällt.

    Angenommen 28 und 10000 sind gefallen.

    Vector = 10000%32 =16 Elemente
    davon werden aber nur 2 benötig Rest ist 0

    Map hat nur 2 Elemente

    Element=bitset

    0
  • I

    idefix schrieb:

    Vorschlag:

    Speichern:

    for(i=0;i<Vector.size();i++)
    {
    save_to_bin_file(Vector[].to_ulong());
    }

    muß dann natürlich in

    map<...>::iterator iter;
for(iter=Map.begin();iter!=Map.end();iter++)
{
  save_to_bin_file((*iter).first,(*iter).second.to_ulong());
}
    0
  • S

    idefix schrieb:

    Ein vector ist ein geschlossener Bereich, dass heißt wenn das bitset nicht gebraucht wird ist es troztdem vorhanden. Eine Map legt nur auf bedarf an. Du kannst also die Lücken aus nutzen. Zweiter Vorteil um kopiererei, wegen dynamisch, entfällt.

    Angenommen 28 und 10000 sind gefallen.

    Vector = 10000%32 =16 Elemente
    davon werden aber nur 2 benötig Rest ist 0

    Map hat nur 2 Elemente

    Element=bitset

    Das sehe ich nicht so. Ich habe gerade ein Bitset zur Reduzierung des Speicherverbrauchs gewählt.

    Beispiel mit 10 aus 0...100:

    vector< bitset<32> > : ( 100 Bits ) / 8 + 1 = 13 Bytes
    map< int, bitset<32> > : ( 10*64 Bits ) / 8 = 80 Bytes

    Selbst bei 2 aus 0...100 hat die <map> bereits 16 Bytes und das <bitset> nur 13 Bytes.

    0
  • S

    Ich habe das jetzt folgendermaßen gemacht:

    bool RandomList::generateFile( string file, uint64_t n, uint64_t N )
{
    ofstream o_file( file.c_str(), ios::out | ios::trunc | ios::binary );
    if( !o_file ) {
        perror( "ofstream" );
        exit( 1 );
    }

    const size_t BITSET_LEN = sizeof( unsigned long ) * 8;
    const size_t VECTOR_LEN = ( ( N % BITSET_LEN ) > 0 ) ?
                                  ( N / BITSET_LEN + 1 ) : ( N / BITSET_LEN );
    vector< bitset<BITSET_LEN> > rand_bits( VECTOR_LEN );

    for( size_t i=0; i<n; ) { 
        size_t rand_pos = random() % N;
        if( !rand_bits[rand_pos/BITSET_LEN].test( rand_pos%BITSET_LEN ) ) {
            rand_bits[rand_pos/BITSET_LEN].set( rand_pos%BITSET_LEN );
            i++;
        }
    }

    for( size_t i=0; i<VECTOR_LEN; i++ ) {
        o_file << rand_bits[i].to_ulong();
    }     
    o_file.close();

    cout << "Written random bits:\n";
    for( size_t i=0; i<VECTOR_LEN; i++ ) {
        for( size_t b=0; b<BITSET_LEN; b++ ) {
            if( rand_bits[i].test( b ) ) {
                cout << i*BITSET_LEN+b << " ";
            }
        }
    }
    cout << endl << endl;

    return true;
}

    Mein Problem ist das...

    o_file << rand_bits[i].to_ulong();

    ... nur den ASCII-Code für den unsigned int Wert in das File schreibt (z.B. 8 aus 0...8 = 255 im File).
    Wie kann ich ihm jetzt noch sagen, das er die Bytes RAW wegschreiben soll?

    0
  • G

    mit http://www.cplusplus.com/ref/iostream/ostream/write.html

    o_file.write( reinterpret_cast<const char *>( &rand_bits[i].to_ulong() ), sizeof( rand_bits[i].to_ulong() ) ) ;

    irgend wir habe ich aber das gefühl das es noch besser geht

    0
  • S

    Bei mir funktioniert es leider nicht so, ich bekomme folgende Fehlermeldung beim Compilieren:

    error: non-lvalue in unary `&'

    Ich habe folgende g++ Version:
    g++ (GCC) 3.3 20030226 (prerelease) (SuSE Linux)

    0
  • O

    Wenn man eine temporäre Variable einbaut (ist hier IMHO (!) eh schöner), geht es auch:

    unsigned long val = rand_bits[i].to_ulong();
o_file.write(reinterpret_cast<const char*>(&val), sizeof(val));
    0
  • I

    schern schrieb:

    Das sehe ich nicht so. Ich habe gerade ein Bitset zur Reduzierung des Speicherverbrauchs gewählt.

    Beispiel mit 10 aus 0...100:

    vector< bitset<32> > : ( 100 Bits ) / 8 + 1 = 13 Bytes
    map< int, bitset<32> > : ( 10*64 Bits ) / 8 = 80 Bytes

    Selbst bei 2 aus 0...100 hat die <map> bereits 16 Bytes und das <bitset> nur 13 Bytes.

    Ja, du hast Recht. Ich habe bei der Map den Index vergessen.

    Ich bin aber mit deiner Rechnung nicht ganz einverstanden.

    Bereich: 0 bis 100 wird mit 4 bitsets abgebildet.
    also
    vector: 4 * 32 Bit = 4 * 4 Byte = 16 Byte
    map: 4 * (32 Bit + 4 Byte) = 32 Byte

    Dem Vector ist es allerding egal ob eine alle Zahlen gefallen sind.

    Angenommen 10 Zahlen sind ganz rein zufällig 1-10,
    dann würde die Map nur 1*(32 Bit + 4 Byte)= 8 Byte groß sein.

    Allerdings hatte ich dich schon nach der Dichte, wenn auch etwas missverständlich, gefragt. Hinzu kommt das ein Zufallsgenerator die Zahlen ja gut über ein Bereich verteilen soll. Somit ist der Vector schon die bessere Alternative.
    Bei einem Bereich von 0...100000 ergeben sich 3125 bitsets und bie 10000 Zahlen ist es unwahrscheinlich das ein Bitset nicht benutzt wird.

    0
  • C

    HumeSikkins schrieb:

    was spricht jetzt genau gegen std::vector<bool>?

    Ist vector<bool> nicht irgendwas Abgedrehtes, nur kein container?
    In "Effective STL" steht IMHO, dass man vector<bool> nur selten benutzen sollte, da es sich nicht wie ein Container verhält.

    0
  • S

    idefix schrieb:

    [...]
    Bereich: 0 bis 100 wird mit 4 bitsets abgebildet.
    also
    vector: 4 * 32 Bit = 4 * 4 Byte = 16 Byte
    map: 4 * (32 Bit + 4 Byte) = 32 Byte

    Ups, da habe ich mich wohl verrechnet 😕

    idefix schrieb:

    Dem Vector ist es allerding egal ob eine alle Zahlen gefallen sind.

    Angenommen 10 Zahlen sind ganz rein zufällig 1-10,
    dann würde die Map nur 1*(32 Bit + 4 Byte)= 8 Byte groß sein.

    Stimmt, ist aber relativ unwahrscheinlich.

    idefix schrieb:

    Allerdings hatte ich dich schon nach der Dichte, wenn auch etwas missverständlich, gefragt.
    [...]

    Über die Dichte kann ich leider keine Aussage machen. Ich verwende den "Mersenne Twister" Random-Generator (gsl_rng_mt19937 http://sources.redhat.com/gsl/ref/gsl-ref_17.html#SEC269) der GSL http://www.gnu.org/software/gsl/gsl.html.

    Viele Grüße
    Bastian

    0
Anmelden zum Antworten