En guide til BitSet i Java

1. Oversigt

I denne vejledning skal vi se, hvordan vi kan bruge BitSets for at repræsentere en vektor af bits.

Først starter vi med begrundelsen bag ikke at bruge boolsk []. Så efter at blive fortrolig med BitSet interner, ser vi nærmere på dets API.

2. Array of Bits

For at gemme og manipulere arrays af bits kan man argumentere for, at vi skal bruge boolsk [] som vores datastruktur. Ved første øjekast kan det virke som et rimeligt forslag.

Dog hver boolsk medlem i en boolsk [] bruger normalt en byte i stedet for kun en bit. Så når vi har stramme hukommelseskrav, eller hvis vi bare sigter mod et reduceret hukommelsesfodaftryk, boolsk [] er langt fra at være ideelle.

For at gøre tingene mere konkrete, lad os se, hvor meget plads a boolsk [] med 1024 elementer forbruger:

boolske [] bits = nye boolske [1024]; System.out.println (ClassLayout.parseInstance (bits) .toPrintable ());

Ideelt set forventer vi et 1024-bit hukommelsesfodaftryk fra dette array. Imidlertid afslører Java Object Layout (JOL) en helt anden virkelighed:

[Z objekt interner: OFFSET STØRRELSE TYPE BESKRIVELSE VÆRDI 0 4 (objekt header) 01 00 00 00 (00000001 00000000 00000000 00000000) (1) 4 4 (objekt header) 00 00 00 00 (00000000 00000000 00000000 00000000) (0) 8 4 (objektoverskrift) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483) 12 4 (objektoverskrift) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024) 16 1024 boolsk [Z. Ikke relevant Instansstørrelse: 1040 bytes

Hvis vi ignorerer objektoverskriftens overhead, forbruger arrayelementerne 1024 bytes i stedet for de forventede 1024 bits. Det er 700% mere hukommelse end forventet.

Detproblemerne med adresserbarhed og ordrivning er de vigtigste grunde til det boolsks er mere end kun en enkelt bit.

For at løse dette problem kan vi bruge en kombination af numeriske datatyper (f.eks lang) og bitvise operationer. Det er her, BitSet kommer i.

3. Hvordan BitSet Arbejder

Som vi nævnte tidligere, for at opnå en bit pr. Flaghukommelsesforbrug, er BitSet API bruger en kombination af grundlæggende numeriske datatyper og bitvise operationer.

Af hensyn til enkelheden antager vi, at vi repræsenterer otte flag med et byte. Først initialiserede vi alle bits af denne single byte med nul:

Nu, hvis vi vil indstille bit på position tre til rigtigt, vi skal først skifte nummer 1 med tre til venstre:

Og så eller dets resultat med strømmen byte værdi:

Den samme proces vil ske, hvis du beslutter at indstille bit ved indeks syv:

Som vist ovenfor udfører vi en venstreforskydning med syv bits og kombinerer resultatet med det foregående byte værdi ved hjælp af eller operatør.

3.1. Få et bitindeks

For at kontrollere, om et bestemt bitindeks er indstillet til rigtigt eller ej, vi bruger og operatør. For eksempel kan vi her kontrollere, om indeks tre er indstillet:

  1. Udførelse af et venstre-skift med tre bits på værdien en
  2. Anding resultatet med strømmen byte værdi
  3. Hvis resultatet er større end nul, fandt vi et match, og det bitindeks er faktisk indstillet. Ellers er det ønskede indeks klart eller lig med falsk

Ovenstående diagram viser trin til få operation for indeks tre. Hvis vi spørger om et klart indeks, vil resultatet imidlertid være anderledes:

Siden den og resultatet er lig med nul, indeks fire er klart.

3.2. Dyrkning af opbevaring

I øjeblikket kan vi kun gemme en vektor på 8 bit. For at gå ud over denne begrænsning, vi skal bare bruge en række bytes, i stedet for en enkelt byte, det er det!

Hver gang vi har brug for at indstille, hente eller rydde et bestemt indeks, skal vi først finde det tilsvarende arrayelement. Lad os for eksempel antage, at vi indstiller indeks 14:

Som vist i ovenstående diagram, efter at have fundet det rigtige array-element, indstillede vi det passende indeks.

Også, hvis vi vil indstille et indeks ud over 15 her, BitSet vil udvide sin interne matrix først. Først efter at have udvidet arrayet og kopieret elementerne, indstiller det den ønskede bit. Dette svarer noget til hvordan ArrayList arbejder internt.

Indtil videre har vi brugt byte datatype for enkelheds skyld. Det BitSet API bruger dog en række lang værdier internt.

4. Den BitSet API

Nu hvor vi ved nok om teorien, er det tid til at se, hvad BitSet API ser ud.

For det første, lad os sammenligne hukommelsesfodaftrykket af en BitSet eksempel med 1024 bits med boolsk [] vi så tidligere:

BitSet bitSet = nyt BitSet (1024); System.out.println (GraphLayout.parseInstance (bitSet) .toPrintable ());

Dette vil udskrive både den lave størrelse af BitSet forekomst og størrelsen på dens interne matrix:

[e-mail-beskyttet] objekt eksternt: ADRESSESTØRRELSE TYPE BANVÆRDI 70f97d208 24 java.util.BitSet (objekt) 70f97d220 144 [J. ord [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0]

Som vist ovenfor bruger den en lang[] med 16 elementer (16 * 64 bits = 1024 bit) internt. Alligevel, denne forekomst bruger i alt 168 byte, mens boolsk [] brugte 1024 byte.

Jo flere bits vi har, jo mere øges forskellen på fodaftryk. For eksempel at gemme 1024 * 1024 bit, boolsk [] bruger 1 MB, og BitSet instans forbruger omkring 130 KB.

4.1. Konstruktion BitSets

Den enkleste måde at oprette en BitSet eksempel er at bruge no-arg konstruktøren:

BitSet bitSet = ny BitSet ();

Dette vil skabe en BitSet eksempel med en lang[] af størrelse en. Selvfølgelig kan den automatisk vokse denne matrix, hvis det er nødvendigt.

Det er også muligt at oprette en BitSet med et indledende antal bits:

BitSet bitSet = nyt BitSet (100_000);

Her vil den interne matrix have nok elementer til at rumme 100.000 bits. Denne konstruktør er praktisk, når vi allerede har et rimeligt skøn over antallet af bits, der skal gemmes. I sådanne brugstilfælde det kan forhindre eller mindske den unødvendige kopiering af matrixelementer, mens den vokser.

Det er endda muligt at oprette en BitSet fra en eksisterende lang[], byte [], LongBufferog ByteBuffer. For eksempel opretter vi her en BitSet eksempel fra en given lang[]:

BitSet bitSet = BitSet.valueOf (ny lang [] {42, 12});

Der er tre mere overbelastede versioner af Værdi af() statisk fabriksmetode til understøttelse af de andre nævnte typer.

4.2. Indstilling af bidder

Vi kan indstille værdien af ​​et bestemt indeks til rigtigt bruger sæt (indeks) metode:

BitSet bitSet = ny BitSet (); bitSet.set (10); assertThat (bitSet.get (10)). isTrue ();

Som normalt er indekserne nulbaserede. Det er endda muligt at indstille en række bits til rigtigt bruger sæt (fraInclusive, toExclusive) metode:

bitSet.set (20, 30); for (int i = 20; i <= 29; i ++) {assertThat (bitSet.get (i)). isTrue (); } assertThat (bitSet.get (30)). isFalse ();

Som det fremgår af metodesignaturen, er begyndelsesindekset inkluderende, og det endelige er eksklusivt.

Når vi siger at indstille et indeks, mener vi normalt at indstille det til rigtigt. På trods af denne terminologi kan vi indstille et bestemt bitindeks til falsk bruger sæt (indeks, boolsk) metode:

bitSet.set (10, false); assertThat (bitSet.get (10)). er Falsk ();

Denne version understøtter også indstilling af en række værdier:

bitSet.set (20, 30, false); for (int i = 20; i <= 29; i ++) {assertThat (bitSet.get (i)). isFalse (); }

4.3. Rydning af bidder

I stedet for at indstille et specifikt bitindeks til falsk, kan vi simpelthen rydde det ved hjælp af klar (indeks) metode:

bitSet.set (42); assertThat (bitSet.get (42)). isTrue (); bitSet.clear (42); assertThat (bitSet.get (42)). er Falsk ();

Desuden kan vi også rydde en række bits med klar (fraInclusive, toExclusive) overbelastet version:

bitSet.set (10, 20); for (int i = 10; i <20; i ++) {assertThat (bitSet.get (i)). isTrue (); } bitSet.clear (10, 20); for (int i = 10; i <20; i ++) {assertThat (bitSet.get (i)). isFalse (); }

Interessant nok hvis vi kalder denne metode uden at videregive argumenter, rydder det alle sætbits:

bitSet.set (10, 20); bitSet.clear (); for (int i = 0; i <100; i ++) {assertThat (bitSet.get (i)). isFalse (); }

Som vist ovenfor, efter at have ringet til klar() metode er alle bits sat til nul.

4.4. At få bid

Indtil videre har vi brugt få (indeks) metode ganske udførligt. Når det anmodede bitindeks er indstillet, vender denne metode tilbage rigtigt. Ellers vender det tilbage falsk:

bitSet.set (42); assertThat (bitSet.get (42)). isTrue (); assertThat (bitSet.get (43)). isFalse ();

Svarende til sæt og klar, kan vi få en række bitindekser ved hjælp af få (fraInclusive, toExclusive) metode:

bitSet.set (10, 20); BitSet newBitSet = bitSet.get (10, 20); for (int i = 0; i <10; i ++) {assertThat (newBitSet.get (i)). isTrue (); }

Som vist ovenfor returnerer denne metode en anden BitSet i området [20, 30) for den aktuelle. Det vil sige indeks 20 på bitSet variabel svarer til indeks nul for newBitSet variabel.

4.5. Flipping Bits

For at negere den aktuelle bitindeksværdi kan vi bruge flip (indeks) metode. Det vil sige, det vender rigtigt værdier til falsk og omvendt:

bitSet.set (42); bitSet.flip (42); assertThat (bitSet.get (42)). er Falsk (); bitSet.flip (12); assertThat (bitSet.get (12)). isTrue ();

På samme måde kan vi opnå det samme for en række værdier ved hjælp af flip (fraInclusive, toExclusive) metode:

bitSet.flip (30, 40); for (int i = 30; i <40; i ++) {assertThat (bitSet.get (i)). isTrue (); }

4.6. Længde

Der er tre længdelignende metoder til a BitSet. Det størrelse() metode returnerer antallet af bits, som den interne matrix kan repræsentere. For eksempel, da no-arg-konstruktøren tildeler en lang[] array med et element, derefter størrelse() returnerer 64 for det:

BitSet defaultBitSet = nyt BitSet (); assertThat (defaultBitSet.size ()). er EqualTo (64);

Med et 64-bit nummer kan vi kun repræsentere 64 bit. Selvfølgelig vil dette ændre sig, hvis vi passerer antallet af bits eksplicit:

BitSet bitSet = nyt BitSet (1024); assertThat (bitSet.size ()). er EqualTo (1024);

Desuden er kardinalitet () metode repræsenterer antallet af sæt bits i a BitSet:

assertThat (bitSet.cardinality ()). er EqualTo (0); bitSet.set (10, 30); assertThat (bitSet.cardinality ()). er EqualTo (30 - 10);

Først returnerer denne metode nul, som alle bits er falsk. Efter indstilling af [10, 30) -området til rigtigt, derefter kardinalitet () metodeopkald returnerer 20.

Også den længde () metode returnerer det ene indeks efter indekset for den sidste sætbit:

assertThat (bitSet.length ()). er EqualTo (30); bitSet.set (100); assertThat (bitSet.length ()). er EqualTo (101);

Først er det sidste indeks 29, så denne metode returnerer 30. Når vi indstiller indekset 100 til sandt, så er længde () metode returnerer 101. Det er også værd at nævne, at denne metode returnerer nul, hvis alle bits er klare.

Endelig blev er tom() metoden vender tilbage falsk når der er mindst en sæt bit i BitSet. Ellers vender det tilbage rigtigt:

assertThat (bitSet.isEmpty ()). isFalse (); bitSet.clear (); assertThat (bitSet.isEmpty ()). isTrue ();

4.7. Kombinerer med andet BitSets

Det krydser (BitSet) metode tager en anden BitSet og vender tilbage rigtigt når to BitSets har noget til fælles. Det vil sige, at de har mindst en sætbit i det samme indeks:

BitSet først = nyt BitSet (); first.set (5, 10); BitSet sekund = ny BitSet (); second.set (7, 15); assertThat (first.intersects (second)). isTrue ();

[7, 9] -området er indstillet i begge BitSets, så denne metode vender tilbage rigtigt.

Det er også muligt at udføre det logiske og drift på to BitSets:

første. og (anden); assertThat (first.get (7)). er sandt (); assertThat (first.get (8)). isTrue (); assertThat (first.get (9)). er sandt (); assertThat (first.get (10)). er Falsk ();

Dette vil udføre en logisk og mellem de to BitSets og ændrer først variabel med resultatet. På samme måde kan vi udføre en logisk xor på to BitSets også:

first.clear (); first.set (5, 10); first.xor (anden); for (int i = 5; i <7; i ++) {assertThat (first.get (i)). isTrue (); } for (int i = 10; i <15; i ++) {assertThat (first.get (i)). isTrue (); }

Der er andre metoder såsom andNot (BitSet) eller den eller (BitSet),som kan udføre andre logiske operationer på to BitSets.

4.8. Diverse

Fra og med Java 8, der er en strøm() metode til at streame alle sæt bits af en BitSet. For eksempel:

BitSet bitSet = ny BitSet (); bitSet.set (15, 25); bitSet.stream (). forEach (System.out :: println);

Dette udskriver alle indstillede bits til konsollen. Da dette vil returnere en IntStream, kan vi udføre almindelige numeriske operationer som summering, gennemsnit, optælling osv. For eksempel tæller vi her antallet af sæt bit:

assertThat (bitSet.stream (). count ()). er EqualTo (10);

Også, det nextSetBit (fraIndex) metoden returnerer det næste indstillede bitindeks startende fra fraIndex:

assertThat (bitSet.nextSetBit (13)). er EqualTo (15);

Det fraIndex selv er inkluderet i denne beregning. Når der ikke er nogen rigtigt lidt tilbage i BitSet, det vender tilbage -1:

assertThat (bitSet.nextSetBit (25)). er EqualTo (-1);

Tilsvarende det nextClearBit (fraIndex) returnerer det næste klare indeks startende fra fraIndex:

assertThat (bitSet.nextClearBit (23)). er EqualTo (25);

På den anden side er previousClearBit (fraIndex) returnerer indekset for det nærmeste klare indeks i den modsatte retning:

assertThat (bitSet.previousClearBit (24)). er EqualTo (14);

Det samme gælder for previousSetBit (fraIndex):

assertThat (bitSet.previousSetBit (29)). er EqualTo (24); assertThat (bitSet.previousSetBit (14)). er EqualTo (-1);

Desuden kan vi konvertere en BitSet til en byte [] eller a lang[] bruger toByteArray () eller toLongArray () metoder henholdsvis:

byte [] bytes = bitSet.toByteArray (); lang [] længes = bitSet.toLongArray ();

5. Konklusion

I denne vejledning så vi, hvordan vi kan bruge BitSets til at repræsentere en vektor af bits.

Først blev vi bekendt med begrundelsen bag ikke at bruge boolsk [] for at repræsentere en vektor af bits. Så så vi, hvordan en BitSet fungerer internt, og hvordan dets API ser ud.

Som sædvanligt er alle eksemplerne tilgængelige på GitHub.