streamalism.org

1. Oversikt

I denne opplæringen skal vi se hvordan vi kan bruke BitSets for å representere en vektor av biter.

Først begynner vi med begrunnelsen bak å ikke bruke boolsk []. Så etter å ha blitt kjent med BitSet internt, vil vi se nærmere på API-en.

2. Array of Bits

For å lagre og manipulere matriser med biter, kan man argumentere for at vi bør bruke boolsk [] som datastrukturen vår. Ved første øyekast kan det virke som et rimelig forslag.

Imidlertid hver boolsk medlem i en boolsk [] bruker vanligvis en byte i stedet for bare en bit. Så når vi har strenge minnekrav, eller bare sikter mot et redusert minnefotavtrykk, boolsk [] er langt fra ideelle.

For å gjøre saken mer konkret, la oss se hvor mye plass a boolsk [] med 1024 elementer forbruker:

boolsk [] bits = ny boolsk [1024]; System.out.println (ClassLayout.parseInstance (bits) .toPrintable ());

Ideelt sett forventer vi et 1024-biters minnefotavtrykk fra denne matrisen. Imidlertid avslører Java Object Layout (JOL) en helt annen virkelighet:

[Z objekt interner: OFFSET STØRRELSE TYPE BESKRIVELSE VERDI 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. N / A Forekomststørrelse: 1040 byte

Hvis vi ignorerer overhead på objektoverskrift, bruker matriseelementene 1024 byte, i stedet for de forventede 1024 bitene. Det er 700% mer minne enn det vi forventet.

Deadresserbarhetsproblemer og ordsriving er de viktigste årsakene til at boolsks er mer enn bare en enkeltbit.

For å løse dette problemet kan vi bruke en kombinasjon av numeriske datatyper (for eksempel lang) og bitvise operasjoner. Det er der BitSet kommer inn.

3. Hvordan BitSet Virker

Som vi nevnte tidligere, for å oppnå en bit per minneforbruk, er BitSet API bruker en kombinasjon av grunnleggende numeriske datatyper og bitvise operasjoner.

For enkelhets skyld, la oss anta at vi skal representere åtte flagg med ett byte. Først initialiserer vi alle biter av denne singelen byte med null:

Nå hvis vi vil sette biten i posisjon tre til ekte, vi bør først skifte nummer 1 med tre:

Og så eller resultatet med strømmen byte verdi:

Den samme prosessen vil skje hvis du bestemmer deg for å sette biten til indeks syv:

Som vist ovenfor utfører vi et venstre-skift med syv bits og kombinerer resultatet med det forrige byte verdi ved hjelp av eller operatør.

3.1. Få en bitindeks

For å sjekke om en bestemt bitindeks er satt til ekte eller ikke, vi bruker og operatør. For eksempel, her er hvordan vi sjekker om indeks tre er satt:

1. Utfører en venstre-skift med tre biter på verdien en
2. Anding resultatet med strømmen byte verdi
3. Hvis resultatet er større enn null, fant vi en kamp, ​​og den bitindeksen er faktisk satt. Ellers er den forespurte indeksen klar eller lik falsk

Ovenstående diagram viser trinnene for å få operasjoner for indeks tre. Hvis vi spør om en klar indeks, vil resultatet imidlertid være annerledes:

Siden og resultatet er lik null, indeks fire er klar.

3.2. Voksende lagring

For øyeblikket kan vi bare lagre en vektor på 8 bits. For å gå utover denne begrensningen, vi må bare bruke en rekke bytes, i stedet for en singel byte, det er det!

Nå, hver gang vi trenger å sette, hente eller fjerne en bestemt indeks, bør vi først finne det tilsvarende arrayelementet. La oss for eksempel anta at vi skal sette indeks 14:

Som vist i diagrammet ovenfor, etter å ha funnet riktig arrayelement, satte vi inn den rette indeksen.

Også, hvis vi vil sette en indeks utover 15 her, vil BitSet vil utvide sitt interne utvalg først. Først etter å ha utvidet matrisen og kopiert elementene, vil den angi den forespurte biten. Dette ligner noe på hvordan ArrayList jobber internt.

Så langt har vi brukt byte datatype for enkelhets skyld. De BitSet API bruker imidlertid en rekke lang verdier internt.

4. Den BitSet API

Nå som vi vet nok om teorien, er det på tide å se hva BitSet API ser ut som.

For det første, la oss sammenligne minnefotavtrykket til en BitSet forekomst med 1024 bits med boolsk [] vi så tidligere:

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

Dette vil skrive ut både den grunne størrelsen på BitSet forekomst og størrelsen på den interne matrisen:

[e-postbeskyttet] objekt eksternt: ADRESSESTØRRELSE TYPE BANEVERDI 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]

Som vist ovenfor bruker den en lang[] med 16 elementer (16 * 64 bits = 1024 bits) internt. Uansett, denne forekomsten bruker totalt 168 byte, mens boolsk [] brukte 1024 byte.

Jo flere biter vi har, jo mer øker fotavtrykkforskjellen. For eksempel, for å lagre 1024 * 1024 bits, boolsk [] bruker 1 MB, og BitSet forekomst forbruker rundt 130 KB.

4.1. Konstruksjon BitSets

Den enkleste måten å lage en BitSet eksempel er å bruke no-arg-konstruktøren:

BitSet bitSet = ny BitSet ();

Dette vil skape en BitSet eksempel med en lang[] av størrelse en. Selvfølgelig kan den automatisk utvide denne matrisen om nødvendig.

Det er også mulig å lage en BitSet med et innledende antall bits:

BitSet bitSet = ny BitSet (100_000);

Her vil den interne matrisen ha nok elementer til å romme 100.000 bits. Denne konstruktøren kommer godt med når vi allerede har et rimelig estimat på antall bits å lagre. I slike brukstilfeller det kan forhindre eller redusere unødvendig kopiering av matriseelementer mens den vokser.

Det er til og med mulig å lage en BitSet fra en eksisterende lang[], byte [], LongBuffer, og ByteBuffer. Her lager vi for eksempel en BitSet forekomst fra en gitt lang[]:

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

Det er tre flere overbelastede versjoner av verdien av() statisk fabrikkmetode for å støtte de andre nevnte typene.

4.2. Sette biter

Vi kan sette verdien til en bestemt indeks til ekte bruker sett (indeks) metode:

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

Som vanlig er indeksene nullbaserte. Det er til og med mulig å sette et utvalg av biter til ekte bruker sett (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 av metodesignaturen, er begynnelsesindeksen inkluderende, og den endelige er eksklusiv.

Når vi sier å sette en indeks, mener vi vanligvis å sette den til ekte. Til tross for denne terminologien kan vi sette en bestemt bitindeks til falsk bruker sett (indeks, boolsk) metode:

bitSet.set (10, false); assertThat (bitSet.get (10)). isFalse ();

Denne versjonen støtter også innstilling av en rekke verdier:

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

4.3. Rydding av biter

I stedet for å sette en spesifikk bitindeks til falsk, kan vi ganske enkelt fjerne det ved hjelp av klar (indeks) metode:

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

Videre kan vi også fjerne et utvalg av biter med klar (fraInclusive, toExclusive) overbelastet versjon:

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, hvis vi kaller denne metoden uten å sende noen argumenter, vil det fjerne alle settbiter:

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

Som vist ovenfor, etter å ha ringt klar() metode, er alle biter satt til null.

4.4. Å få biter

Så langt har vi brukt få (indeks) metode ganske omfattende. Når den forespurte bitindeksen er satt, vil denne metoden returnere ekte. Ellers kommer den tilbake falsk:

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

Lik sett og klar, kan vi få en rekke bitindekser ved hjelp av 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 metoden en annen BitSet i [20, 30) -området til den nåværende. Det vil si indeks 20 av bitSet variabel tilsvarer indeks null på newBitSet variabel.

4.5. Flipping Bits

For å negere den nåværende bitindeksverdien, kan vi bruke flip (indeks) metode. Det vil si at det vil snu ekte verdier til falsk og vice versa:

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

På samme måte kan vi oppnå det samme for en rekke verdier ved hjelp av flip (fraInclusive, toExclusive) metode:

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

4.6. Lengde

Det er tre lengdelignende metoder for a BitSet. De størrelse() metoden returnerer antall bits den interne matrisen kan representere. For eksempel, siden ingen arg-konstruktøren tildeler en lang[] matrise med ett element, deretter størrelse() vil returnere 64 for det:

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

Med ett 64-bits nummer kan vi bare representere 64 bits. Selvfølgelig vil dette endre seg hvis vi passerer antall biter eksplisitt:

BitSet bitSet = ny BitSet (1024); assertThat (bitSet.size ()). erEqualTo (1024);

Videre, den kardinalitet () metoden representerer antall settbiter i a BitSet:

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

Først returnerer denne metoden null som alle biter er falsk. Etter å ha satt [10, 30) -området til ekte, og så kardinalitet () metodeanrop returnerer 20.

Også, den lengde() metoden returnerer den ene indeksen etter indeksen til den siste settbiten:

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

Først er den siste settindeksen 29, så denne metoden returnerer 30. Når vi setter indeksen 100 til sann, så blir lengde() metoden returnerer 101. Det er også verdt å nevne at denne metoden vil gi null hvis alle biter er klare.

Til slutt, er tom() metoden returnerer falsk når det er minst ett sett bit i BitSet. Ellers kommer den tilbake ekte:

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

4.7. Kombinere med annet BitSets

De krysser (BitSet) metoden tar en annen BitSet og kommer tilbake ekte når to BitSets har noe til felles. Det vil si at de har minst en settbit i samme indeks:

BitSet først = nytt BitSet (); first.set (5, 10); BitSet sekund = ny BitSet (); second.set (7, 15); assertThat (første kryss (andre)). er sann ();

[7, 9] -området er angitt i begge BitSets, så denne metoden returnerer ekte.

Det er også mulig å utføre det logiske og operasjon på to BitSets:

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

Dette vil være logisk og mellom de to BitSets og endrer først variabel med resultatet. På samme måte kan vi utføre en logisk xor på to BitSets også:

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

Det er andre metoder som andNot (BitSet) eller eller (BitSet),som kan utføre andre logiske operasjoner på to BitSets.

4.8. Diverse

Fra og med Java 8, det er en strøm() metode for å streame alle settbiter av a BitSet. For eksempel:

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

Dette vil skrive ut alle settbiter til konsollen. Siden dette vil returnere en IntStream, kan vi utføre vanlige numeriske operasjoner som summering, gjennomsnitt, telling, og så videre. For eksempel teller vi her antall settbiter:

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

Også, de nextSetBit (fraIndex) metoden vil returnere neste sett bitindeks med start fra fraIndex:

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

De fraIndex selv er inkludert i denne beregningen. Når det ikke er noen ekte litt igjen i BitSet, det kommer tilbake -1:

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

På samme måte, de nextClearBit (fraIndex) returnerer neste klare indeks med start fra fraIndex:

assertThat (bitSet.nextClearBit (23)). erEqualTo (25);

På den annen side, den previousClearBit (fraIndex) returnerer indeksen til nærmeste klare indeks i motsatt retning:

assertThat (bitSet.previousClearBit (24)). erEqualTo (14);

Det samme gjelder for previousSetBit (fraIndex):

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

Videre kan vi konvertere en BitSet til en byte [] eller a lang[] bruker toByteArray () eller toLongArray () metoder, henholdsvis:

byte [] byte = bitSet.toByteArray (); lang [] lengter = bitSet.toLongArray ();

5. Konklusjon

I denne opplæringen så vi hvordan vi kan bruke BitSets for å representere en vektor av biter.

Først ble vi kjent med begrunnelsen bak å ikke bruke boolsk [] å representere en vektor av biter. Så så vi hvordan en BitSet fungerer internt og hvordan API-en ser ut.

Som vanlig er alle eksemplene tilgjengelige på GitHub.