Dynamisches <bitset>

idefix

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

idefix

oder map<int,bitset<32>>

schern

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

idefix

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

idefix

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());
}

schern

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.

schern

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?

Gerard

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

schern

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)

operator void

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

idefix

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.

Christoph

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.

schern

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

HumeSikkins

Ist vector<bool> nicht irgendwas Abgedrehtes, nur kein container?

Umfasst der Begriff "Abgedreht" bei dir explizite Templatespezalisierung + die Anwendung des Proxy-Patterns? Falls ja, dann ist vector<bool> in der Tat abgedreht
Richtig ist auch, dass vector<bool> die im Standard festgelegten Container-Bedingungen *nicht* erfüllt. Es ist also kein Container im Sinne des C++ Standards.

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

Auch das stimmt. Nur heißt "selten" ja nicht "nie". vector<bool> ist kein Container und (was problematischer ist) drückt einem auch noch eine ganz bestimmte Optimierung auf's Auge. Dazu kommt, dass ein vector<bool> keine bools enthält, was nicht gerade zum Verständnis beiträgt.

Da ich aber in der Frage nirgends erkennen konnte, dass unbedingt ein Container (im Sinne des C++ Standards) benötigt wird und da *explizit* der Wunsch nach Größenoptimierung aufkam, sehe ich nicht, warum man vector<bool> hier von vorneherein ausschließen sollte.

Helium

Was ist eigentlich mit boost::dynamic_bitset? Ich habs mir noch nie angeschaut, kann also nicht sagen, ob es hier passend ist.

schern

Helium schrieb:

Was ist eigentlich mit boost::dynamic_bitset? Ich habs mir noch nie angeschaut, kann also nicht sagen, ob es hier passend ist.

Davon habe ich ja noch nie was gehört. Hast Du vielleicht mal 'ne Referenz parat?

HumeSikkins

Hast Du vielleicht mal 'ne Referenz parat?

Startest du hier:
http://www.boost.org

Dann dem Link "Documentation" folgen.
Und schwupps:

http://www.boost.org/libs/dynamic_bitset/dynamic_bitset.html

Dynamisches &lt;bitset&gt;

Dynamisches <bitset>