Datenstruktur große binäre Matrix

[CBfan]

Liebe Leser/innen!

Grüß Gott und ich bin neu hier. Bin gerade auf C umgestiegen und quäl mich noch mit den Anfängen herum. Da kommt's mir gar nicht entgegen, dass ich schon auf ein handfestes Problem gestoßen bin: Ich will eine große binäre Matrix abspeichern und habe gehört, dass dies in der Regel mit einer Art "Bitmapzugriff" zu bewerkstelligen ist. So wie ich das verstanden habe, werden die einzelnen bits eines (z.B.) Integerwerts dafür hergenommen, jene 0/1-Information zu speichern. Noch anmerken sollte ich vielleicht, dass meine abzuspeichernde Matrix keine wie immer gearteten Strukturen (etwa Dreiecksmatrix) aufweist. Bin jetzt schon Tage auf Internetrecherche, leider aber erfolglos. Vielen Dank für eine etwaige Hilfe, einen Denkansatz oder link.

Noch'n schön Sonntag!

[c.rackwitz]

CBfan schrieb:

"Bitmapzugriff"... So wie ich das verstanden habe, werden die einzelnen bits eines (z.B.) Integerwerts dafür hergenommen, jene 0/1-Information zu speichern.

falschinformation.

es heisst "binaer" und hat zwangsweise mit bits und bytes zu tun. schliesslich hast du ja nen computer vor dir und keinen abakus.

du willst:

f = fopen("dateiname", "wb"); // "wb" fuer "schreiben" und "binaer"
// binaer deswegen, weil bei nicht-binaer zeilenumbrueche umgewandelt werden koennten, was wiederum deine gespeicherten binaerdaten zerschiessen wuerde
fwrite(...irgendwelche parameter...);
fclose(f);

[CBfan]

Danke, c.rackwitz, für deine schnelle Reaktion! Leider denke ich nicht, dass du mich auf die richtige Spur geführt hast - aber das liegt wahrscheinlich daran, dass ich mich schlecht ausgedrückt habe: ich will keine auf der Festplatte gespeicherte binäre Datei lesen (oder dorthin schreiben), sondern im Programm eine binäre Matrix mit Hilfe jener Speicher/Datenstruktur (die ich leider nur vage wiederzugeben vermag) verwalten. (Die Matrix selbst könnte in diesem Programm auch ganz einfach eine mit rand() simulierte sein.)

Hilft das ein bisschen weiter?

[c.rackwitz]

achso, du willst ein 2-dimensionales array?

dynamisch, also in der groesse waehlbar:
http://www.c-plusplus.net/forum/viewtopic-var-p-is-933701.html#933701
http://www.c-plusplus.net/forum/viewtopic-var-p-is-989590.html#989590

feste groesse:
int matrix[spalten][zeilen];

[CBfan]

Wir kommen der Sache näher. Richtig, ich meine ein 2-dimensionales Array. Aber deine Varianten scheinen mir alle dynamisch angelegte Felder und Listen zu sein, die so auf diese Weise eine solche Matrix abbilden und zugängig machen. Das aber will ich nicht ...

Stell dir mal eine einzige int Varibale vor. Die besteht doch - so war's in Pascal (da komm ich her) zumindest - aus 16 bits. Das heißt also, wenn wir uns nun eine Zeile meiner Matrix vorstellen, dass mir mit 10 int Variablen (sozusagen 'nebeneinander') insgesamt 10.16=160 bits, oder besser 160 binäre Positionen, zur Verfügung stehen. Und genau die will ich nützen. Bloß weiß ich leider nicht wie

[Sepp Brannigan]

Hallo CBfan,
sowie ich dein Problem glaube verstanden zu haben, suchst du in etwa sowas:

#define BITS_X       1024
#define BITS_Y       1024
#define BLOCK_SIZE   (sizeof(unsigned int) * 8)
#define DIM_X        (BITS_X / BLOCK_SIZE)
#define DIM_Y        BITS_Y

unsigned int bitMatrix[DIM_Y][DIM_X];

typedef char Bit;

Bit getBit( int x, int y ) {
   unsigned int bit_block, bit_mask;
   unsigned char bit_shift;

   // entspr. block aus matrix holen ...
   bit_block = bitMatrix[y][x / BLOCK_SIZE];

   // bitposition im block ...
   bit_shift = x % BLOCK_SIZE;
   // maske zum rausfummeln des entspr. bits
   bit_mask = 0x1 << bit_shift;

   return ((bit_block & bit_mask) == 1);
}

void setBit( int x, int y, Bit bit ) {
   unsigned int bit_block, bit_mask;
   unsigned char bit_shift;

   // entspr. block aus matrix holen ...
   bit_block = bitMatrix[y][x / BLOCK_SIZE];   

   // bitposition im block ...
   bit_shift = x % BLOCK_SIZE;
   // maske zum rausfummeln des entspr. bits
   bit_mask = 0x1 << bit_shift;

   // bit setzen oder loeschen?
   /* bugfix: thx to Miq */
   if(bit) { 
      bitMatrix[y][x/BLOCK_SIZE] |= bit_mask; 
   } 
   else { 
      bitMatrix[y][x/BLOCK_SIZE] &= (~bit_mask); 
   }
}

soweit mal zum Hirndump -> also weder vollständig (checks ...) noch getestet!
Auf bits kann man in normal-C nicht direkt zugreifen, daher das Gefrickel mit den Bitmasken. Je nachdem wie die Bitmatrix sonst noch so interpretiert wird, z.B. als Graphik-Bitmap, musst evtl. die shifts entsprechend anpassen.

grüße

[CBfan]

Woot! Sepp, das scheint mir genau das zu sein, was ich suche. Ich hab einfach

{
  int main()
  setBit(10,17,1);
  printf("10,17=%i\n",getBit(10,17));
  getchar();	
  return 0;
}

angehängt und das Ding fehlerlos compiliert. Dies hat dann den output "10,17=0" produziert (anstatt der erhofften "10,17=1"). An dieser Stelle bleibt mir offensichtlich wohl wirklich nichts Anderes mehr übrig, als noch mal darauf hinzuweisen, dass ich C-newbie bin. Tut mir aber dennoch leid, wenn ich dir mit meiner naiven Antwort das nackte Gruseln beigebracht habe ... Könntest vielleicht so nett sein und mir noch ein wenig weiter auf die Beinchen helfen?

P.S.: wie bekommt man hier Farbe in den [code]?

Edit: Farbe gefunden!

[Miq]

Das

return ((bit_block & bit_mask) == 1);

ist der Übeltäter. Der Ausdruck

return ((bit_block & bit_mask) ? 1 : 0);

funktioniert wahrscheinlich besser.

[CBfan]

Leider nein (dennoch danke für deinen Einsatz)!

[Miq]

Oh, sorry, einen habe ich in setBit übersehen:

if(bit)
{
   bitMatrix[y][x/BLOCK_SIZE] |= bit_mask;
}
else
{
   bitMatrix[y][x/BLOCK_SIZE] &= (~bit_mask);
}

[Sepp Brannigan]

wow - das is teamwork! thx Miq.
Klar, ohne Zuweisung passiert hier natürlich garnix ...
In deinem Vorschlag fürs return seh ich allerdings keinen Unterschied zwischen den beiden Varianten ...

[CBfan]

Sepp und Miq, das war tatsächlich tolle Teamarbeit - erst einmal herzlichen Dank! Gebt mir bitte ein bisschen Zeit, damit ich das verdauen kann und dann würd' ich mich bitte gerne wieder melden, um ein paar Fragen zu stellen. Noch'n schönen Abend und bis bald!

[Miq]

Sepp Brannigan schrieb:

wow - das is teamwork! thx Miq.
Klar, ohne Zuweisung passiert hier natürlich garnix ...
In deinem Vorschlag fürs return seh ich allerdings keinen Unterschied zwischen den beiden Varianten ...

Tja, bit_mask ist z.B. 0x00100000, und bit_block 0x3fa256D0, dann ist Dein Ausdruck bit_block & bit_mask == 0x00100000, und das ist != 1, obwohl das Bit gesetzt ist.

[Sepp Brannigan]

*anshirnklatsch* - logo!

[CBfan]

(Gemessen an /meinem/ Verständnis würde mich ein entsprechendes *anshirnklatsch* in Lebensgefahr bringen Aber ich bemüh mich.

(M)Ein kleines Progrämmchen läuft jetzt. Die wesentlichen Bestandteile sind die Prozeduren setBit und getBit sowie die bitMatrix. Ich kann mit setBit schreiben und mit getBit lesen. D.h. um bitMatrix selbst brauch ich mich gar nicht kümmern. Hier einge fragwürdige Punkte:

1. Warum wird BITS_X=1024 und BITS_Y=1024 angenommen? (Ich frage mich das, weil diese beiden Werte ja einen Einfluss auf die Dimensionen von bitMatrix haben.)

2. Müssen BITS_X und BITS_Y immer 2er-Potenzen sein, so wie hier 2^10=1024?

3. Das maximale set/getBit ist also eines mit (DIM_Y=1024,DIM_X=32), in anderen Worten, ich kann eine 0-1-Matrix der Größe 1024x32 verwalten? (32, weil 1024/BLOCK_SIZE=32 gilt). Was ist aber, wenn ich gerne eine "seitenverkehrte" Matrix, also eine mit 32x1024, hätte oder gar eine mit Nicht-2er-Potenzen, z.B.: 30x2000?

4. Wo ist denn eigentlich die Speicherplatzersparnis - um die es mir ursprünglich ja ging - zu finden? bitMatrix benötigt m.W. 1024*32*4/1024=128KB Speicherplatz. Und jetzt nehmen wir mal an, ich benötige tatsächlich eine Bool'sche Matrix der Größenordnung 1024x32. Warum schreibe/lese ich dann meine Einsen und Nullen nicht gleich direkt nach/von bitMatrix (bei gleichen 128KB Speicherplatzbedarf!)? (Hier unterläuft mir offenbar ein fatal error in meiner Vorstellung.)

5. Ich bin draufgekommen, dass ich (z.B.) locker noch ein Array über int dummy[9999][9999]; definieren kann (was natürlich nicht wirklich wahr sein kann)! Weder der Compiler regt sich auf, noch quälen mich irgendwelche runtime errors. In Pascal wäre das erst gar nicht compilierbar gewesen. Oder andersrum: Wie erfahre ich denn die maximal möglichen Dimensionen eines Vektors (eines Arrays, einer Struktur usw.) in C?

6. Gibt es (wie in Pascal) eine Möglichkeit den belegten Speicherplatz einer exe zu erfahren, ich meine code und data size ebenso wie stack und heap size?

Wie immer, ein dickes Dankeschön an euch.

[Miq]

CBfan schrieb:

...
(M)Ein kleines Progrämmchen läuft jetzt. Die wesentlichen Bestandteile sind die Prozeduren setBit und getBit sowie die bitMatrix. Ich kann mit setBit schreiben und mit getBit lesen. D.h. um bitMatrix selbst brauch ich mich gar nicht kümmern.

Fein!

CBfan schrieb:

Hier einge fragwürdige Punkte:

1. Warum wird BITS_X=1024 und BITS_Y=1024 angenommen? (Ich frage mich das, weil diese beiden Werte ja einen Einfluss auf die Dimensionen von bitMatrix haben.)

Ich denke, da wollte Sepp nur ein Beispiel geben; Da trägst Du genau die Bit-Dimensionen ein, die Deine "echte" Matrix haben soll.

CBfan schrieb:

2. Müssen BITS_X und BITS_Y immer 2er-Potenzen sein, so wie hier 2^10=1024?

Nein. Macht es aber u.U. schneller in der Verarbeitung.

CBfan schrieb:

3. Das maximale set/getBit ist also eines mit (DIM_Y=1024,DIM_X=32), in anderen Worten, ich kann eine 0-1-Matrix der Größe 1024x32 verwalten? (32, weil 1024/BLOCK_SIZE=32 gilt). Was ist aber, wenn ich gerne eine "seitenverkehrte" Matrix, also eine mit 32x1024, hätte oder gar eine mit Nicht-2er-Potenzen, z.B.: 30x2000?

Nein! Die Matrix ist 1024x1024 Bit, nur werden jeweils 32 Bit in ein unsigned int gepackt. Alle Dimensionen gehen prinzipiell, die Packerei ist eine rein interne Darstellung, die der Anwender von setBit und getBit am besten gar nicht kennen soll. (C++ wäre hier noch besser, um die Implementierung zu kapseln...)

CBfan schrieb:

4. Wo ist denn eigentlich die Speicherplatzersparnis - um die es mir ursprünglich ja ging - zu finden? bitMatrix benötigt m.W. 1024*32*4/1024=128KB Speicherplatz. Und jetzt nehmen wir mal an, ich benötige tatsächlich eine Bool'sche Matrix der Größenordnung 1024x32. Warum schreibe/lese ich dann meine Einsen und Nullen nicht gleich direkt nach/von bitMatrix (bei gleichen 128KB Speicherplatzbedarf!)? (Hier unterläuft mir offenbar ein fatal error in meiner Vorstellung.)

Bit-Matrizen gibt es in C nativ nicht, deswegen Sepp's Methode, ints zu nehmen. In C könntest Du alternativ so was wie

unsigned char matrix[1000][1000];

benutzen, würdest aber den achtfachen Speicher von Sepp's Lösung brauchen, bei unsigned int sogar den 32fachen!

CBfan schrieb:

5. Ich bin draufgekommen, dass ich (z.B.) locker noch ein Array über int dummy[9999][9999]; definieren kann (was natürlich nicht wirklich wahr sein kann)! Weder der Compiler regt sich auf, noch quälen mich irgendwelche runtime errors. In Pascal wäre das erst gar nicht compilierbar gewesen. Oder andersrum: Wie erfahre ich denn die maximal möglichen Dimensionen eines Vektors (eines Arrays, einer Struktur usw.) in C?

Warum kann das nicht wahr sein? Es gibt sogar noch viel größere Matrizen in der Realität... Der Haken steckt in der Architektur der Maschine, auf der Du Dein Programm laufen läßt - manche begrenzen den en bloc allozierbaren Speicher auf recht kleine Größen, so dass man da sowieso mit einer eigenen Speicherverwaltung arbeiten muss. Macht bei immer wechselnden Matrizengrößen eh' mehr Sinn.

CBfan schrieb:

6. Gibt es (wie in Pascal) eine Möglichkeit den belegten Speicherplatz einer exe zu erfahren, ich meine code und data size ebenso wie stack und heap size?

Uh... Falsche Baustelle - ich bin UN*X-Bastler, PCs kann ich nicht gut...

CBfan schrieb:

Wie immer, ein dickes Dankeschön an euch.

Gerne!

[CBfan]

Also mein fatal error war, dass die Matrixgröße nicht durch DIM_X und DIM_Y bestimmt ist, sondern durch BITS_X und BITS_Y. Dadurch wird auch klar, wo der Speicherplatzgewinn liegt: nämlich bei DIM_X=(BITS_X / BLOCK_SIZE). Jetzt passt das alles wieder wunderschön zusammen

Bit-Matrizen gibt es in C nativ nicht, deswegen Sepp's Methode, ints zu nehmen. In C könntest Du alternativ so was wie
Code:
unsigned char matrix[1000][1000];
Code:
unsigned char matrix[1000][1000];
Code:
unsigned char matrix[1000][1000];

benutzen, würdest aber den achtfachen Speicher von Sepp's Lösung brauchen, bei unsigned int sogar den 32fachen!

Okay, es gibt keinen extra bool'schen Typ (daszumindest wußte ich ja). Was mich vielmehr wundert(e), ist dass ich wirklich noch (um ein anderes Phantasiebeispiel zu nehmen) mit einer Zeile "unsigned char dummy [9999][9999];" eine riiiiiesige Matrix zu meinem Progrämmchen hinzufügen kann - und es kann noch immer compiliert werden und läuft fehlerlos. Matrix dummy hat aber eine Größe von 390546KB - und die haben nun in meiner WindowsXP-PC-Architektur ganz ganz gewiss nicht wirklich Platz. Dewegen meine Frage, wie man solche Speichergrenzen nun tatsächlich sinnig betimmen kann!?

Womit ein anderer Versuch nahe lag: Warum kann ich bei BITS_X=BITS_Y=1024 (die somit die Größe meiner 0-1 Matrix angeben) problemslos ein setBit(1100,1100,1) ausführen und bekomm durch getBit(1100,1100) über printf auch noch das richtige Ergebnis? Hier hätte mein Pascal compiler schon "constant out of range" geschrien! Nebenbei bemerkt, kann man in Pascal runtime errors auf Grund eines range check errors auch - wie der Begriff "runtime error" ja bereits klar macht - (erst) während der Laufzeit abfangen (z.B. wenn eine ständig inkrementierte Variable x bei einem Aufruf A[x=11] mit der Grenze von A, die auf 10 gesetzt war, kollidiert))!?

Dank'da nochmal, ich lerne hier sehr effizient

[Sepp Brannigan]

Hallo ihr beiden,
wollt hier nur schnell Miq's Annahmen bzgl. meines Beispiels bestätigen.
Sonst wurde ja schon alles gesagt, nehm ich mal an.

Zu den Speichergrenzen für solche Dinger denk ich mal, dass die für ne 32bit-Architektur irgendwo im Bereich von 4GB liegen sollten. Zumindest ist das ja der max. Adressierbare Speicher (auch XP, denk ich, oder war da was mit 2GB?) und über virtual memory machbar. Dass die Kiste dabei endlos pagefaults hinnehmen muss, ist klar ... aber das ist doch dem Compiler egal. Drum sollte man also auch solch große Matrizen lieber zeileweise durchlaufen ...
Nach dieser Theorie sollte ein unsigned int riesenMatrix[32768][32768]; dann schon eher Probleme machen, oder? keine Ahnung - nicht getestet.

Zum printf-effekt und dem Zugriffsfehler: Genau das meinte das "(checks ...)" in den Bemerkungen zur ersten Codeversion - es ist wahrscheinlich, dass deinem Prozess da der Matrixspeicher in page-Einheiten zugeteilt wird, drum kannst wohl ne ganze Zeit drüber rausschreiben ohne in ner fremden page zu landen und nen segfault zu bekommen. Aber strapazieren würd ich dieses "Verfahren" nicht ...

grüße

[Miq]

Eine vernünftige Implementation in C++ würde auch die Speichergrenzen checken...

[CBfan]

Was eure Speichergrenzendiskussion betrifft, bin ich schlicht und einfach überfordert: "pagefaults", "Matrixspeicher in page-Einheiten zugeteilt" oder auf "ner fremden page zu landen und nen segfault" bekommen - damit kann ich nicht wirklich viel anfangen (was natürlich mein Problem ist). Aber Miqs Bemerkung

Eine vernünftige Implementation in C++ würde auch die Speichergrenzen checken

tät ich schon noch gern aufgreifen: Ich will ja vernünftig programmieren, also wie mache ich das denn - in Ansätzen zumindest?

Und wäre ich euch auch sehr dankbar, wenn ihr mir in Kürze erklären könntet, was set/getBit nun eigentlich ganz originär tun. Hab in all meinen (noch wenigen) C(++) Büchern gesucht und hab auch das Netz bemüht, aber ein "bit_mask = 0x1 << bit_shift;" oder "return ((bit_block & bit_mask) ? 1 : 0);" (beide aus getBit) ... da steig ich leider aus! Oder könntet ihr mir vielleicht einen Tipp oder link geben, wo ich mich diesbezüglich weiter informieren kann?