4. Datenstruktur große binäre Matrix

Datenstruktur große binäre Matrix

  • S

    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?

    0
  • C

    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:

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

    2. 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.

    3. 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?

    0
  • M

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

    CBfan schrieb:

    1. 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:

    1. ... 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:

    1. 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"

    0
  • C

    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!).

    0
  • M

    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.

    0
Anmelden zum Antworten