Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
09.11.2006, 21:33 Uhr
~grimmel
Gast

Hallo,

ich würde gerne ein bitweises ODER machen. Ich habe ein array aus 0 und 1 en.
Dieses array kann dimension von über 1000 haben.
was ich machen will: Ich will in einem zweiten array was auch nur aus 0 und 1 en besteht ob es eine teilmenge an 1en hat - also z.B:

00101 ODER 00100 -> JA ist teilmenge
00101 ODER 00110 -> NEIN keine teilmenge

Jetzt würde ich gerne dieses array mit einem anderen über bitweises oder verknüpfen also jede stelle mit jeder über ein ODER machen.
Nur weiß ich bei solchen dimension nicht wie ich das hanhaben soll...ich glaube nicht dass ein int über 2000 Bits verfügen kann...*grmpf bin etwas durcheinander

Warum ich das machen will/muss sei dahingestellt....
wäre es nicht zu teuer über jede stelle der beiden arrays solange zu laufen bis im 2ten array eine 1 und im vergleicharray eine 0 auftritt? (siehe oben 4te index). Wäre doch im worst case O(anzahl elemente des arrays)...?

Hat jemand ratschlag

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
09.11.2006, 22:42 Uhr
virtual
Sexiest Bit alive
(Operator)

Also erstmal begrenzen wir mal Dein Problem auf Mengen mit sagen wir mal 8 Elementen (Keine Angst, man kann das leicht "unbegrenzt" erweitern)

Sei also A eine Bitmaske, bei der für jedes Enthaltene Element das korrespondierende Bit gesetzt ist und B ebenso eine entsprechende Bitmaske, Wenn ich A und B Verordere bekomme ich eine weitere Bitmaske, C:

C = A oder B

Semantisch drückt C jedoch die Vereinigungsmenge von A und B aus. Damit lässt sich in Hinblick auf Teilmengen nur schwer eine Aussage treffen. Beispiel:

A = 00011111
B = 11111000
=> C = 11111111

Anders sieht es mit der UND Verknüpfung aus:

C = A und B

Semantisch drück C nunmehr die Schnittmenge von A un B aus:

A = 00011111
B = 11111000
=> C = 00011000

In Hinblick auf Teilmengen kann man nun folgende Aussage treffen:

(C = A und B) und C=B <=> B ist Teilmenge von A

Oder, ein wenig kürzer ausgedrückt: Um Eine Aussage bzgl. Teilmengen zu treffen brauchst Du eine Bitweise UND verknüpfung, weniger die ODER Verknüpfung.

Ein int hat in der Regel keine 2000 Bit, das ist korrekt. Du hast im Prinzip nun die Möglichkeit, einfach mehrere ints zu einer Menge zusammen zu fassen

Du kannst in C++ zB std::set<int> verwenden und aus dem Header <algorithm> Agorithmen nehmen, um Dein Problem zu fassen.

Du kannst in C++ auch std::vector<bool> nehmen, musst dann aber die UND Operation noch selbst ausprogrammieren

Du kannst auch eigenhändig eine entsprechende Klasse schreiben, was ggf. eine echte alternative ist.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
09.11.2006, 22:43 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

Hi,
in der Datenform müsstest du es. Wenn du deine Bits immer alle in ints speichern würdest (also 32 pro int z.b) dann bräuchtest du nur zum vergleich jeweils die ints durchlaufen lassen, wodurch du schon nur noch 1000/32 durchläufe hättest. (int64 und co bringen auf 32bit rechnern nichts mehr, da er dann trotzdem teilt, auf 64bittern wären natürlich int64 besser)
momentan müsstest du dann alle durchlaufen lassen, seh da keine einfachere methode.

bzw könntest evtl mehrere tests gleichzeitig machen (wenn das z.b chars sind könntest du das ganze array in ints casten und somit immer 4 bzw 8 auf einmal immerhin schon in einem rutsch testen)
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
09.11.2006, 22:53 Uhr
~grimmel
Gast

Danke für eure regen antworten...

@virtual: um die teilmengenzugehörigkeit zu testen muss bei dem ergebnis: A UND B etwas ungleich 0 rauskommen oder nicht?

Zitat:

Du kannst in C++ zB std::set<int> verwenden und aus dem Header <algorithm> Agorithmen nehmen, um Dein Problem zu fassen.

Du kannst in C++ auch std::vector<bool> nehmen, musst dann aber die UND Operation noch selbst ausprogrammieren

wäre das wirklich schneller als eine schleife über das eine array?

@FloSoft:

Zitat:

bzw könntest evtl mehrere tests gleichzeitig machen (wenn das z.b chars sind könntest du das ganze array in ints casten und somit immer 4 bzw 8 auf einmal immerhin schon in einem rutsch testen)

es sind in der tat char arrays. Nur kann ich dir mit deiner aussage leider nicht ganz folgen was ud mit mit "in ints casten und somit immer 4 bzw. 8 auf einmal..." meinst

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
09.11.2006, 23:19 Uhr
Blubber2063

Naja du kannst je nach CPU entweder optimal 32, bzw 64 bit verarbeiten. Da du ein Feld hast, kannst du 2 Chars 2 * 1 Byte in einen Int Casten und führst damit nur 1 anstatt 2 Testoperationen aus. Du musst nur aufpassen, das du an der richtigen Stelle Castest.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
10.11.2006, 09:58 Uhr
virtual
Sexiest Bit alive
(Operator)

Zitat von ~grimmel:

Danke für eure regen antworten...

@virtual: um die teilmengenzugehörigkeit zu testen muss bei dem ergebnis: A UND B etwas ungleich 0 rauskommen oder nicht?

Nein. Angenommen A ist die potentielle Obermenge und B die Teilmenge, dann muß bei A&B genau B rauskommen. Mach es Dir am besten mal an einer zwei elementigen Menge A Klar:

A = 01

Ist B = 11, so ist B gewiss keine Teilmenge von A (sondern umgekehrt), aber A&B != 0, genauer gesagt (A&B = B)

Zitat von ~grimmel:

wäre das wirklich schneller als eine schleife über das eine array?

Ich würde es hinsichtlich Performance wie flosoft halten. Hinsichtlich Portabiltät zwischen verschiedenen Systemen nicht. Denkbar wäre (nur Pseudocode):

C++:

class menge {
     const unsigned BPU = sizeof(unsigned)*8; // Anzahl der Bits pro unsigned

     std::vector<unsigned> elements;

     unsigned count;

public:
     void add_element(unsigned i) {
         unsigned bit = i%BPU;
         unsigned unit = i/BPU;

         // Geht auch effizienter: Menge vergrößern:
         while (elements.size()<=unit) elements.push_back(0);

         // Element setzen
         if (0==(elements[unit]&(1<<bit)) {
             elements[unit] |= 1<<bit;
             ++count;
         }
     }

     void remove_element(unsigned i) {
         unsigned bit = i%BPU;
         unsigned unit = i/BPU;

        if (unit < elements.size() && 0!=(elements[unit]&(1<<bit)) {
            elements[unit] &= ~(1<<bit);
             --count;
        }
     }

     // Bilde schnitt menge
     menge intersection(const menge& other) const {
          menge inter;
          for(int i=0; i<elements.size() && i<other.elements.size(); ++i) {
               inter.elements.push_back(elements[i]&other.elements[i]);
          }
          return inter;
     }
}

Zur prüfung der Teilmenge reicht dann:

C++:

bool istTeilmenege(const menge& obermenge, const menge& teilmenge) {
return obermenge.intersection(teilmenge)==teilmenge;
}

Wobei der Operator == halt noch überladen werden muß.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: