Een gids voor BitSet in Java
1. Overzicht
In deze tutorial gaan we zien hoe we BitSets om een vector van bits weer te geven.
Eerst beginnen we met de grondgedachte achter het niet gebruiken van de boolean []. Vervolgens nadat u vertrouwd bent geraakt met het BitSet internals, zullen we de API nader bekijken.
2. Reeks bits
Om reeksen bits op te slaan en te manipuleren, zou je kunnen stellen dat we deze zouden moeten gebruiken boolean [] als onze datastructuur. Op het eerste gezicht lijkt dat misschien een redelijke suggestie.
Elk boolean lid in een boolean [] verbruikt gewoonlijk één byte in plaats van slechts één bit. Dus als we krappe geheugenvereisten hebben, of als we gewoon streven naar een kleinere geheugenvoetafdruk, boolean [] zijn verre van ideaal.
Laten we, om de zaken concreter te maken, eens kijken hoeveel ruimte a boolean [] met 1024 elementen verbruikt:
boolean [] bits = nieuwe boolean [1024]; System.out.println (ClassLayout.parseInstance (bits) .toPrintable ());Idealiter verwachten we een geheugenvoetafdruk van 1024 bits van deze array. De Java Object Layout (JOL) onthult echter een heel andere realiteit:
[Interne objecten Z: OFFSET GROOTTE TYPE BESCHRIJVING WAARDE 0 4 (objectkop) 01 00 00 00 (00000001 00000000 00000000 00000000) (1) 4 4 (objectkop) 00 00 00 00 (00000000 00000000 00000000 00000000) (0) 8 4 (objectheader) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483) 12 4 (objectheader) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024) 16 1024 boolean [Z. Nvt Instantiegrootte: 1040 bytesAls we de overhead van de objectheader negeren, verbruiken de array-elementen 1024 bytes in plaats van de verwachte 1024 bits. Dat is 700% meer geheugen dan we hadden verwacht.
Deadresseerbaarheidsproblemen en het scheuren van woorden zijn de belangrijkste redenen waarom booleans zijn meer dan slechts een enkel bit.
Om dit probleem op te lossen, kunnen we een combinatie van numerieke gegevenstypen gebruiken (zoals lang) en bitsgewijze bewerkingen. Dat is waar de BitSet komt binnen.
3. Hoe BitSet Werken
Zoals we eerder vermeldden, om het geheugengebruik van één bit per vlag te bereiken, de BitSet API gebruikt een combinatie van numerieke basisgegevenstypen en bitsgewijze bewerkingen.
Laten we voor de eenvoud aannemen dat we acht vlaggen met één vertegenwoordigen byte. In eerste instantie initialiseren we alle bits van deze single byte met nul:
Als we nu het bit op positie drie op willen zetten waar, we moeten eerst het getal 1 met drie naar links verschuiven:
En dan of het resultaat met de stroom byte waarde:
Hetzelfde proces zal gebeuren als u besluit om de bit op index zeven in te stellen:
Zoals hierboven getoond, voeren we een verschuiving naar links met zeven bits uit en combineren we het resultaat met het vorige byte waarde met behulp van de of operator.
3.1. Een bitindex krijgen
Om te controleren of een bepaalde bitindex is ingesteld op waar of niet, we gebruiken de en operator. Hier is bijvoorbeeld hoe we controleren of index drie is ingesteld:
- Een verschuiving naar links uitvoeren met drie bits op de waarde één
- Anding het resultaat met de stroom byte waarde
- Als het resultaat groter is dan nul, hebben we een overeenkomst gevonden en is die bitindex daadwerkelijk ingesteld. Anders is de aangevraagde index duidelijk of gelijk aan false
Het bovenstaande diagram toont de get-bewerkingsstappen voor index drie. Als we echter naar een duidelijke index vragen, zal het resultaat anders zijn:
Sinds de en resultaat is gelijk aan nul, index vier is duidelijk.
3.2. De opslag laten groeien
Momenteel kunnen we alleen een vector van 8 bits opslaan. Om verder te gaan dan deze beperking, we hoeven alleen maar een reeks bytes, in plaats van een enkele byte, dat is het!
Nu moeten we elke keer dat we een specifieke index moeten instellen, ophalen of wissen, eerst het corresponderende array-element vinden. Stel dat we index 14 gaan instellen:
Zoals te zien is in het bovenstaande diagram, hebben we na het vinden van het juiste array-element de juiste index ingesteld.
Als we hier een index van meer dan 15 willen instellen, is de BitSet zal eerst zijn interne array uitbreiden. Pas nadat de array is uitgebreid en de elementen zijn gekopieerd, wordt de gevraagde bit ingesteld. Dit lijkt enigszins op hoe ArrayList werkt intern.
Tot nu toe hebben we de byte gegevenstype voor de eenvoud. De BitSet API gebruikt echter een reeks lang waarden intern.
4. Het BitSet API
Nu we genoeg weten over de theorie, is het tijd om te zien wat de BitSet API ziet eruit als.
Laten we om te beginnen de geheugenvoetafdruk van een BitSet instantie met 1024 bits met de boolean [] we zagen eerder:
BitSet bitSet = nieuwe BitSet (1024); System.out.println (GraphLayout.parseInstance (bitSet) .toPrintable ());Hiermee wordt zowel de ondiepe afmeting van de BitSet instantie en de grootte van de interne array:
[email protected] object externals: ADRESGROOTTE TYPE PAD WAARDE 70f97d208 24 java.util.BitSet (object) 70f97d220 144 [J .words [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0]Zoals hierboven getoond, gebruikt het een lang[] met 16 elementen (16 * 64 bits = 1024 bits) intern. In ieder geval, deze instantie gebruikt in totaal 168 bytes, terwijl de boolean [] gebruikten 1024 bytes.
Hoe meer bits we hebben, hoe groter het verschil in footprint. Als u bijvoorbeeld 1024 * 1024 bits wilt opslaan, moet de boolean [] verbruikt 1 MB, en het BitSet instantie verbruikt ongeveer 130 KB.
4.1. Constructie BitSets
De eenvoudigste manier om een BitSet instantie is om de no-arg constructor te gebruiken:
BitSet bitSet = nieuwe BitSet ();Dit zal een BitSet instantie met een lang[] van maat één. Het kan deze array natuurlijk indien nodig automatisch laten groeien.
Het is ook mogelijk om een BitSet met een initieel aantal bits:
BitSet bitSet = nieuwe BitSet (100_000);Hier heeft de interne array genoeg elementen om 100.000 bits te bevatten. Deze constructor is handig als we al een redelijke schatting hebben van het aantal bits dat moet worden opgeslagen. In dergelijke gevallen, het kan het onnodig kopiëren van array-elementen tijdens het groeien ervan voorkomen of verminderen.
Het is zelfs mogelijk om een BitSet van een bestaand lang[], byte[], LongBuffer, en ByteBuffer. Hier maken we bijvoorbeeld een BitSet instantie van een gegeven lang[]:
BitSet bitSet = BitSet.valueOf (nieuw lang [] {42, 12});Er zijn nog drie overbelaste versies van de waarde van() statische fabrieksmethode om de andere genoemde typen te ondersteunen.
4.2. Bits instellen
We kunnen de waarde van een bepaalde index instellen op waar de ... gebruiken set (index) methode:
BitSet bitSet = nieuwe BitSet (); bitSet.set (10); assertThat (bitSet.get (10)). isTrue ();Zoals gewoonlijk zijn de indices op nul gebaseerd. Het is zelfs mogelijk om een reeks bits in te stellen op waar de ... gebruiken set (van inclusief, tot exclusief) methode:
bitSet.set (20, 30); voor (int i = 20; i <= 29; i ++) {assertThat (bitSet.get (i)). isTrue (); } assertThat (bitSet.get (30)). isFalse ();Zoals blijkt uit de handtekening van de methode, is de beginindex inclusief en de eindindex exclusief.
Als we het hebben over het instellen van een index, bedoelen we meestal het instellen op waar. Ondanks deze terminologie kunnen we een bepaalde bitindex instellen op false de ... gebruiken set (index, boolean) methode:
bitSet.set (10, false); assertThat (bitSet.get (10)). isFalse ();Deze versie ondersteunt ook het instellen van een reeks waarden:
bitSet.set (20, 30, false); voor (int i = 20; i <= 29; i ++) {assertThat (bitSet.get (i)). isFalse (); }4.3. Bits wissen
In plaats van een specifieke bitindex in te stellen op false, kunnen we het eenvoudig wissen met de duidelijk (index) methode:
bitSet.set (42); assertThat (bitSet.get (42)). isTrue (); bitSet.clear (42); assertThat (bitSet.get (42)). isFalse ();Bovendien kunnen we ook een reeks bits wissen met de clear (fromInclusief, naarExclusief) overbelaste versie:
bitSet.set (10, 20); voor (int i = 10; i <20; i ++) {assertThat (bitSet.get (i)). isTrue (); } bitSet.clear (10, 20); voor (int i = 10; i <20; i ++) {assertThat (bitSet.get (i)). isFalse (); }Interessant is dat als we deze methode aanroepen zonder argumenten door te geven, worden alle ingestelde bits gewist:
bitSet.set (10, 20); bitSet.clear (); voor (int i = 0; i <100; i ++) {assertThat (bitSet.get (i)). isFalse (); }Zoals hierboven weergegeven, nadat u het Doorzichtig() methode, worden alle bits op nul gezet.
4.4. Bits krijgen
Tot nu toe hebben we de krijgen (index) methode vrij uitgebreid. Als de gevraagde bitindex is ingesteld, keert deze methode terug waar. Anders keert het terug false:
bitSet.set (42); assertThat (bitSet.get (42)). isTrue (); assertThat (bitSet.get (43)). isFalse ();Gelijkwaardig aan set en Doorzichtig, kunnen we een reeks bitindices krijgen met behulp van de krijgen (fromInclusief, naarExclusief) methode:
bitSet.set (10, 20); BitSet newBitSet = bitSet.get (10, 20); voor (int i = 0; i <10; i ++) {assertThat (newBitSet.get (i)). isTrue (); }Zoals hierboven getoond, retourneert deze methode een andere BitSet in het [20, 30) bereik van de huidige. Dat wil zeggen, index 20 van de bitSet variabele is gelijk aan index nul van de newBitSet variabele.
4.5. Bits omdraaien
Om de huidige bitindexwaarde te ontkennen, kunnen we de flip (index) methode. Dat wil zeggen, het zal veranderen waar waarden naar false en vice versa:
bitSet.set (42); bitSet.flip (42); assertThat (bitSet.get (42)). isFalse (); bitSet.flip (12); assertThat (bitSet.get (12)). isTrue ();Evenzo kunnen we hetzelfde bereiken voor een reeks waarden met behulp van de omdraaien (van exclusief, naar exclusief) methode:
bitSet.flip (30, 40); voor (int i = 30; i <40; i ++) {assertThat (bitSet.get (i)). isTrue (); }4.6. Lengte
Er zijn drie lengteachtige methoden voor een BitSet. De grootte() methode geeft het aantal bits terug dat de interne array kan vertegenwoordigen. Omdat de constructor no-arg bijvoorbeeld een lang[] array met één element, dan de grootte() zal er 64 voor teruggeven:
BitSet defaultBitSet = nieuwe BitSet (); assertThat (defaultBitSet.size ()). isEqualTo (64);Met één 64-bits nummer kunnen we slechts 64 bits vertegenwoordigen. Dit verandert natuurlijk als we het aantal bits expliciet doorgeven:
BitSet bitSet = nieuwe BitSet (1024); assertThat (bitSet.size ()). isEqualTo (1024);Bovendien is de kardinaliteit methode vertegenwoordigt het aantal ingestelde bits in een BitSet:
assertThat (bitSet.cardinality ()). isEqualTo (0); bitSet.set (10, 30); assertThat (bitSet.cardinality ()). isEqualTo (30 - 10);In eerste instantie retourneert deze methode nul, zoals alle bits dat zijn false. Na het instellen van het bereik [10, 30) op waar, dan de kardinaliteit method call retourneert 20.
Ook de lengte() methode retourneert de ene index na de index van de laatste ingestelde bit:
assertThat (bitSet.length ()). isEqualTo (30); bitSet.set (100); assertThat (bitSet.length ()). isEqualTo (101);In eerste instantie is de laatst ingestelde index 29, dus deze methode retourneert 30. Als we de index 100 instellen op true, dan is de lengte() methode retourneert 101. Het is ook vermeldenswaard dat deze methode nul retourneert als alle bits duidelijk zijn.
eindelijk, de is leeg() methode retourneert false als er tenminste één set bit in de BitSet. Anders keert het terug waar:
assertThat (bitSet.isEmpty ()). isFalse (); bitSet.clear (); assertThat (bitSet.isEmpty ()). isTrue ();4.7. Combineren met andere BitSets
De snijdt (BitSet) methode duurt een andere BitSet en keert terug waar wanneer twee BitSets hebben iets gemeen. Dat wil zeggen, ze hebben ten minste één setbit in dezelfde index:
BitSet first = nieuwe BitSet (); first.set (5, 10); BitSet second = nieuwe BitSet (); second.set (7, 15); assertThat (first.intersects (second)). isTrue ();Het bereik [7, 9] is in beide ingesteld BitSets, dus deze methode retourneert waar.
Het is ook mogelijk om de logische uit te voeren en operatie op twee BitSets:
eerste. en (tweede); assertThat (first.get (7)). isTrue (); assertThat (first.get (8)). isTrue (); assertThat (first.get (9)). isTrue (); assertThat (first.get (10)). isFalse ();Dit zal een logisch resultaat opleveren en tussen de twee BitSets en wijzigt de eerste variabel met het resultaat. Evenzo kunnen we een logisch uitvoeren xor op twee BitSets, ook:
first.clear (); first.set (5, 10); first.xor (tweede); voor (int i = 5; i <7; i ++) {assertThat (first.get (i)). isTrue (); } voor (int i = 10; i <15; i ++) {assertThat (first.get (i)). isTrue (); }Er zijn andere methoden, zoals de andNot (BitSet) of de of (BitSet),die andere logische bewerkingen op twee kan uitvoeren BitSets.
4.8. Diversen
Vanaf Java 8, er is een stroom() methode om alle set bits van een BitSet. Bijvoorbeeld:
BitSet bitSet = nieuwe BitSet (); bitSet.set (15, 25); bitSet.stream (). forEach (System.out :: println);Hiermee worden alle ingestelde bits naar de console afgedrukt. Omdat dit een IntStreamkunnen we algemene numerieke bewerkingen uitvoeren, zoals optellen, gemiddelde, tellen, enzovoort. Hier tellen we bijvoorbeeld het aantal ingestelde bits:
assertThat (bitSet.stream (). count ()). isEqualTo (10);Ook, de nextSetBit (fromIndex) methode retourneert de volgende ingestelde bitindex, beginnend bij de fromIndex:
assertThat (bitSet.nextSetBit (13)). isEqualTo (15);De fromIndex zelf is in deze berekening meegenomen. Als er geen is waar beetje links in de BitSet, het zal -1 teruggeven:
assertThat (bitSet.nextSetBit (25)). isEqualTo (-1);Evenzo de nextClearBit (fromIndex) geeft de volgende duidelijke index terug beginnend met de fromIndex:
assertThat (bitSet.nextClearBit (23)). isEqualTo (25);Aan de andere kant is het previousClearBit (fromIndex) geeft de index terug van de dichtstbijzijnde duidelijke index in de tegenovergestelde richting:
assertThat (bitSet.previousClearBit (24)). isEqualTo (14);Hetzelfde geldt voor previousSetBit (fromIndex):
assertThat (bitSet.previousSetBit (29)). isEqualTo (24); assertThat (bitSet.previousSetBit (14)). isEqualTo (-1);Bovendien kunnen we een BitSet naar een byte[] of een lang[] de ... gebruiken toByteArray () of toLongArray () methoden, respectievelijk:
byte [] bytes = bitSet.toByteArray (); long [] longs = bitSet.toLongArray ();5. Conclusie
In deze tutorial hebben we gezien hoe we BitSets om een vector van bits weer te geven.
In eerste instantie raakten we bekend met de grondgedachte achter het niet gebruiken van boolean [] om een vector van bits weer te geven. Toen zagen we hoe a BitSet werkt intern en hoe de API eruit ziet.
Zoals gewoonlijk zijn alle voorbeelden beschikbaar op GitHub.
