Hallo Forum!
Wird für jeden boolean Wert in einem eindimensionalem boolean array auch nur 1 Bit im Arbeitsspeicher reserviert?
Oder wird für jeden Wert ein Byte reserviert. Dann wäre das ja der selbe Platzverbrauch für einen byte-array.
Ich müsste das wissen, weil ich möglichst effizient rechenoperationen mit bit arrays programmieren möchte. Bis jetzt habe ich byte-arrays verwendet, aber boolean wäre platztechnisch vielleicht besser?
Falls boolean bitweise gespeichert würde (was ich energisch bezweifle), würde das zwar Platz sparen, aber sicher massiv Laufzeit kosten. Das Lesen/Schreiben eines Bits braucht bei den meisten Prozessoren mehrere Zyklen, während ein einfacher Lese-/Schreibzugriff üblicherweise 1 oder maximal 2 Zyklen braucht.
Außerdem hast Du auf sowas unter Java eh keinen Einfluß. Wenn die JVM auf einem exotischen Prozessor beschließt, ein Bit in ein 32bit-Wort anzuspeichern, dann tut sie das eben.
Gut, vielen Dank!
Das würde dann wohl auch mehr in Assemblerrichtung gehen um die Ansprüche optimal umzusetzen. Dann weiß ich wenigstens, dass es nicht effizienter geht
In Java gibt es die Klasse Bitset.
Dort hast du eine Meng von Bits, die die Zustände 1 oder 0 annehmen können und nur 1 Bit Speicherplatz benötigen.
Die Zugriffe sollen sehr perfomant sein.
Wenn man sich z.B. die Implementierung von BitSet.set ansieht, wird schnell klar, daß man sich für den gesparten Platz einen ziemlichen Laufzeitoverhead an den Hals hängt:
Code:
public void set(int bitIndex) {
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
int unitIndex = unitIndex(bitIndex);
int unitsRequired = unitIndex + 1;
if (unitsInUse < unitsRequired) {
ensureCapacity(unitsRequired);
bits[unitIndex] |= bit(bitIndex);
unitsInUse = unitsRequired;
} else {
bits[unitIndex] |= bit(bitIndex);
}
}
Und wie gesagt: alleine der Read-Modify-Write-Zugriff per "|=" ist bereits sehr viel teuerer als ein einfacher Speicherzugriff, zumal der Arrayzugriff hier ja auch noch zusötzlich erfolgt.
Hehe, dieses Problem kenne ich zur Genüge (bin bei solchen Sachen auch immer neidisch auf Assembler *g*), darum habe ich auch so meine Vorstellungen davon, dieses Problem zu lösen.
Verwendet man dazu z. B. ein int-Array, dann kann von n Bits auf das Bit i wie folgt zugegriffen werden:
Code:
// Testen auf 0:
(bits[i>>>5]&1<<i)==0
// Testen auf 1:
(bits[i>>>5]&1<<i)!=0
// Setzen:
bits[i>>>5]|=1<<i;
// Löschen:
bits[i>>>5]&=~(1<<i);
// Invertieren:
bits[i>>>5]^=1<<i;
So, hoffentlich habe ich keine Fehler gemacht. :lol: Ein i%32 bzw. i&31 ist übrigens nicht notwendig; wie ich gerade nachgelesen habe, verwenden die Schiebeoperatoren entsprechend des Datentyps nur die unteren 3 (byte), 4 (short), 5 (int) oder 6 (long) Bits des Operanden auf der rechten Seite.
Im Prinzip ist das hier nichts weiter als ein BitSet, nur muss man hier nicht ständig öffentliche Methoden aufrufen und kann bzw. muss selbst entscheiden, ob eine Bereichsüberschreitung abgefangen werden soll. Die Zählung von i beginnt natürlich bei 0, und die Konstante 5 muss natürlich angepasst werden, wenn kein int verwendet wird (sondern vielleicht long oder short). Außerdem prüft hier niemand, ob das Bit in einem festgelegten Bereich liegt, denn durch das Verwenden dieser nativen Datentypen entsteht ein (minimaler) „Verlust“, da in einem byte/short/int/long unter Umständen mehr Bits gespeichert werden als tatsächlich notwendig sind. Die Größe des int-Feldes muss für die Anzahl der zu speichernden Bits entsprechend berechnet werden.
Ich denke, diese Implementierung zum Arbeiten mit Bits in Arrays ist die effizienteste, wenn man bedenkt, dass das Arbeiten mit reinen boolean- oder byte-Arrays mit jedem Datum 7 Bit Datenmüll erzeugt. Damit reduziert sich der Speicherplatzverbrauch auf 1/8 bei hoffentlich verschmerzbarem Rechenaufwand, der aufgrund der Bitoperationen minimal ist. Wenn das immer noch zu langsam ist, muss der Assembler herhalten.
Klar,
Assembler ist schneller schneller als Java, aber . . .
Du könntest auch in klassischen C ( ohne ++ ) sehr schoen und schnell die Bits fliegen lassen (-,
A B E R so eine Implemnetierung ist Hardwareabhängig ! Du machst da annahmen vieviele Byte ein int ( long, short .. ) tatsächlich hat und wie es im RAM dargestellt wird, also die Reihenfolge der BYTES und NIBBLES (LOW- and HIBITS). Ich kann mich dunkel Erinnern, das dies variieren kann.
