Datenstruktur große binäre Matrix

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:

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.)
Müssen BITS_X und BITS_Y immer 2er-Potenzen sein, so wie hier 2^10=1024?
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?
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.)
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?
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:

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:

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:

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:

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:

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:

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?

Sepp Brannigan

Sorry wegen Überforderung - es ist immer schwierig den Hintergrund einzuschätzen ...
Was die Speichergrenzendiskussion betrifft - nur ganz grob:
Das Betriebssystem überwacht ja die Nutzung des Speichers und da es nicht über jedes Byte bescheid wissen kann (wär etwas speicherintensiv), welchem Prozess es zugeordnet ist - wird das Ganze in Blöcken eingeteilt - die pages. Die MMU (Teil vieler CPUs) überwacht den Zugriff auf Speicherstellen anhand von Registern, die die Genzen des aktuell zugreifbaren Speichers abstecken. Und genau diese Register werden vom Betriebssystem passend zum aktuell laufenden Prozess gesetzt. Wird von einem Programm also eine Speicherstelle jenseits dieser Grenzen adressiert (also irgendwo in einer fremden page), schmeisst die MMU eine Exception - was sich auf nen "Segmentation fault" - oder kurz "segfault" rausläuft. Soweit nur am Rande - normalerweise alles worauf man als Programmierer unter C achten muss, ist alle seine Zeiger zusammenzuhalten

Zu C++: Sicher gibt es viel schönere und elegantere Möglichkeiten das Ganze in C++ in ner Klasse wegzupacken - am Anfangsproblem ändert das aber garnix und den Check der Indexgrenzen nimmt einem auch C++ nicht ab - und wenns nur per try-catch ist. Allerdings ist das hier der C-Teil dieses Forums, weshalb sich der Ansatz auf folgendes beschränkt:

class BitMatrix {
  public:
     BitMatrix( int bitX, int bitY ) {
       // alles wie gehabt ...
       _matrix = new unsigned int[dimX * dimY];
     }
     ~BitMatrix() { delete[] _matrix; }
     Bit getBit( int x, int y ) { /* wie gehabt ... */ }
     void setBit( int x, int y, Bit bit ) { /* wie gehabt ... */ }

  private:
     unsigned int *_matrix;
};

Tja, was tun die Beiden Funktionen? Die kleinste Speichereinheit worauf in normal C Zugriff erfolgen kann, ist ein Byte. Da wir aber jedes der 8 Bits in diesem Byte ansprechen wollen, müssen wir über sog. Bitmasken vorgehen.
D.h. wir holen uns einfach den ganzen Block und schmeissen alles uninteressante weg. In unserem Fall heisst das: 32 Bits holen, 31 davon werden nicht beachtet.
Dazu brauchen wir die Bitmaske und die erstellt uns

bit_mask = 0x1 << bit_shift;

Wir nehmen hier den Wert 0x1 - was für 8 bit binär 00000001 entspricht und shiften das Ding um #bit_shift Stellen nach links. Also wandert unsere 1 weiter nach links und für bit_shift = 4 ergibt sich: 00010000.
Diese Maske verwenden wir dann mit der bitweisen AND-Verknüpfung - was heisst: Alle Bits die in der Maske 0 sind, sind im Ergebnis auch 0, alle 1-Stellen entsprechen den Bits an der Stelle des verknüpften Wertes. Da wir nur an einem einzigen Bit interessiert sind, reicht die Verknüpfung und der anschliessende Test, ob das Ergebnis 0 oder != 0 war, alles klar?

CBfan

Hallo Sepp, kein Grund für sorry, der mit dem sorry bin wohl eher ich ... und ich hab mir (schon wieder) so meine Gedanken gemacht, die ich kurz zusammenfassen will:

Speichergrenzenbehandlung in C++ geht also. Dein Beispiel basiert wohl auf einem objektorientierten Ansatz; wo hier aber jener Schutzmechanismus eingebaut ist, vermag ich nicht zu entdecken. (Wir belassen's aber einfach dabei;)
Außer die Objektorientiertheit und jede Menge andere Syntax (natürlich mit gegenüber C erweiterten Fähigkeiten, etwa << usw.) hat C++ sicher unendlich viel zu bieten. Auch darüber sollten wir aber jetzt und hier nicht diskutieren. Wohl aber gerne wissen tät ich, wie ein nicht-objektorientierter Speichergrenzenschutzmechanismus aussehen kann (falls es den überhaupt gibt)! Der Grund ist banal: obwohl ich schon seit Ewigkeiten programmiere, habe ich Objekte noch nie benötigt, ich hab mich also dieser neuen Programmiersprache auf Basis des (normalen) C und nicht auf jener von C++ genähert. Übrigens - typisch newbie, - ich verwend den DEV-C++ Compiler.
Was geht denn nun nicht in mein Hirnkastl rein: page hin und page her, ich hab's mit einer quadratischen matrix "unsigned char dummy [DIM][DIM];" ausprobiert (also nicht die Geschichte mit set/getBit): DIM=23000 geht und bei (Ah, er schreit ja doch einmal!) DIM=24000 meldet sich der Compiler mit "size of variable `unsigned int dummy[24000][24000]' is too large". DIM=23000 ist kompilierbar, aber läßt sich net ausführen ... das erste Ausführen ist in der Nähe von DIM=15000 möglich. Dafür gilt aber "sizeof(dummy)=900000000" und das sind grob 858MB. Wie soll das auf meinem Rechner mit (zumindest laut Eigenschaften/Arbeitsplatz) grob 500MB RAM überhaupt gut gehen?

Wie immer, ein herzliches Dankeschön für die Nachhilfe - und einen guten Start in ein tolles Wochenende!

P.S.: Weiß jemand warum Dev-Cpp mit einem schaurigen "bloodshed" verbunden ist?

Miq

@CBfan: sorry, ich war ein paar Tage otk, deswegen erst jetzt eine Reaktion

CBfan schrieb:

Speichergrenzenbehandlung in C++ geht also. Dein Beispiel basiert wohl auf einem objektorientierten Ansatz; wo hier aber jener Schutzmechanismus eingebaut ist, vermag ich nicht zu entdecken. (Wir belassen's aber einfach dabei;)

Ok.

CBfan schrieb:

... Wohl aber gerne wissen tät ich, wie ein nicht-objektorientierter Speichergrenzenschutzmechanismus aussehen kann (falls es den überhaupt gibt)! Der Grund ist banal: obwohl ich schon seit Ewigkeiten programmiere, habe ich Objekte noch nie benötigt, ich hab mich also dieser neuen Programmiersprache auf Basis des (normalen) C und nicht auf jener von C++ genähert. Übrigens - typisch newbie, - ich verwend den DEV-C++ Compiler.

Kein Problem, das machen viele so und leben immer noch
Ein C-Speicherschutz könnte so aussehen, dass Du in setBit und getBit zuerst einen Aufruf der Funktion checkDim einbaust:

unsigned int checkDim(unsigned int x, unsigned int y)
{
   if(x>BITS_X || y>BITS_Y) return 0;
   return 1;
}
...
int getBit( int x, int y )
{
   if(checkDim(x, y))
   {
   ... /* Hier die Funktion, wie bekannt */
   }
   else
   {
   ... /* Hier Fehlerbehandlung, Abbruch oder so was */
   }
}

CBfan schrieb:

Was geht denn nun nicht in mein Hirnkastl rein: page hin und page her, ich hab's mit einer quadratischen matrix "unsigned char dummy [DIM][DIM];" ausprobiert (also nicht die Geschichte mit set/getBit): DIM=23000 geht und bei (Ah, er schreit ja doch einmal!) DIM=24000 meldet sich der Compiler mit "size of variable `unsigned int dummy[24000][24000]' is too large". DIM=23000 ist kompilierbar, aber läßt sich net ausführen ... das erste Ausführen ist in der Nähe von DIM=15000 möglich. Dafür gilt aber "sizeof(dummy)=900000000" und das sind grob 858MB. Wie soll das auf meinem Rechner mit (zumindest laut Eigenschaften/Arbeitsplatz) grob 500MB RAM überhaupt gut gehen?

Könnte es sein, dass bei Deinem PC der virtuelle Speicher noch zum realen dazu kommt? Unter Linux heißt das "Swap"-Speicher, unter XP glaube ich "Virtueller Speicher", die Werte findest Du irgendwo in der Systemsteuerung unter "System->Hardware->Leistung"

CBfan

Kein Problem - ich hoffe, otk bedeutet nix allzu Unangenehmes!(?)

Miq, dein code beschreibt selbst programmiertes range checking. Heisst das also dass es in C kein automatisches range checking gibt (in Pascal konnte man das über Compiler-Schalter zu- und abschalten)?

Solche Selbstkontrollen helfen aber auch nur bedingt, wenn (m)ein Compiler Speicheranforderungen compiliert, die er dann während der runtime gar nicht mehr erfüllen kann - oder noch viel schlimmer, er erlaubt das Compilieren und während des Ausführens des Programms, steht an diesen Speicherstellen nur Blödsinn.

Hab also nachgesehen, was den virtuellen Speicher betrifft. Zu finden unter Arbeitsplatz-Eigenschaften/Erweitert/Systemleistungsoptionen - und hier stehen 768MB virtueller Arbeitssprecher. Ich muss aber zugeben, dass ich annahm, dass dies lediglich die (maximale) Größe der Auslagerungsdatei beschreibt, die Windows für sich, aber nicht für Speicheranforderungen laufender Programme, beansprucht (aber das ist pures Halbwissen!).

Miq

CBfan schrieb:

Kein Problem - ich hoffe, otk bedeutet nix allzu Unangenehmes!(?)

Nee: otk=off the keyboard, ich war weg ohne Computer

CBfan schrieb:

Miq, dein code beschreibt selbst programmiertes range checking. Heisst das also dass es in C kein automatisches range checking gibt (in Pascal konnte man das über Compiler-Schalter zu- und abschalten)?

Richtig vermutet: gibt's in C nicht!

CBfan schrieb:

Hab also nachgesehen, was den virtuellen Speicher betrifft. Zu finden unter Arbeitsplatz-Eigenschaften/Erweitert/Systemleistungsoptionen - und hier stehen 768MB virtueller Arbeitssprecher. Ich muss aber zugeben, dass ich annahm, dass dies lediglich die (maximale) Größe der Auslagerungsdatei beschreibt, die Windows für sich, aber nicht für Speicheranforderungen laufender Programme, beansprucht (aber das ist pures Halbwissen!).

Da bin ich ebenfalls Ratender, Dein 2400x2400-Beispiel deutet aber darauf hin, dass der virtuelle Platz auch an laufende Programme verteilt wird.