streamalism.org

1. Prehľad

V tomto tutoriále sa dozvieme, ako môžeme použiť BitSets predstavuje vektor bitov.

Najprv začneme s odôvodnením nepoužívania boolean []. Potom, ako sa oboznámite s BitSet interných, pozrieme sa bližšie na jeho API.

2. Pole bitov

Na ukladanie a manipuláciu s poľami bitov je možné namietať, že by sme ich mali používať boolean [] ako naša dátová štruktúra. Na prvý pohľad by sa to mohlo zdať ako rozumný návrh.

Avšak každý boolovský člen v a boolean [] zvyčajne spotrebuje jeden bajt namiesto iba jedného bitu. Takže keď máme náročné požiadavky na pamäť, alebo sa zameriavame len na zmenšenú pamäťovú stopu, boolean [] ani zďaleka nie sú ideálne.

Aby sme to upresnili, pozrime sa, koľko miesta a boolean [] s 1024 prvkami spotrebuje:

boolean [] bity = new boolean [1024]; System.out.println (ClassLayout.parseInstance (bity) .toPrintable ());

V ideálnom prípade od tohto poľa očakávame 1024-bitovú pamäťovú stopu. Rozloženie objektov Java (JOL) však odhaľuje úplne inú realitu:

[Interné objekty Z: TYP VEĽKOSTI ODSADY POPIS HODNOTA 0 4 (hlavička objektu) 01 00 00 00 (00000001 00000000 00000000 00000000) (1) 4 4 (hlavička objektu) 00 00 00 00 (00000000 00000000 00000000 00000000) (0) 8 4 (hlavička objektu) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483) 12 4 (hlavička objektu) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024) 16 1024 boolean [Z. N / A Veľkosť inštancie: 1040 bajtov

Ak ignorujeme réžiu hlavičky objektu, prvky poľa spotrebujú 1024 bajtov namiesto očakávaných 1024 bitov. To je o 700% viac pamäte, ako sme očakávali.

Theproblémy s adresovateľnosťou a trhaním slov sú hlavnými dôvodmi, prečo boolovskýsú viac ako iba jeden jediný bit.

Na vyriešenie tohto problému môžeme použiť kombináciu číselných dátových typov (ako napr dlho) a bitové operácie. To je miesto, kde BitSet príde.

3. Ako BitSet Tvorba

Ako sme už spomenuli, na dosiahnutie využitia pamäte typu jeden bit na príznak je potrebné použiť znak BitSet API používa kombináciu základných numerických dátových typov a bitových operácií.

Z dôvodu zjednodušenia predpokladajme, že budeme reprezentovať osem vlajok s jednou bajt. Najskôr inicializujeme všetky bity tohto singla bajt s nulou:

Teraz, ak chceme bit nastaviť na pozíciu tri do pravda, mali by sme najskôr posunúť doľava číslo 1 o tri:

A potom alebo jeho výsledok s prúdom bajt hodnotu:

Rovnaký proces sa stane, ak sa rozhodnete nastaviť bit na indexe sedem:

Ako je uvedené vyššie, vykonáme posun doľava o sedem bitov a výsledok skombinujeme s predchádzajúcim bajt hodnota pomocou alebo operátor.

3.1. Získanie bitového indexu

Skontrolujte, či je konkrétny bitový index nastavený na pravda alebo nie, použijeme a operátor. Napríklad takto skontrolujeme, či je nastavený index tri:

1. Vykonanie ľavého posunu o tri bity na hodnote jeden
2. Anding výsledok s prúdom bajt hodnotu
3. Ak je výsledok väčší ako nula, našli sme zhodu a tento bitový index je skutočne nastavený. V opačnom prípade je požadovaný index jasný alebo rovný nepravdivé

Vyššie uvedený diagram zobrazuje kroky operácie get pre index tri. Ak sa však informujeme o jasnom indexe, bude výsledok iný:

Keďže a výsledok sa rovná nule, index štyri je jasný.

3.2. Rastúce úložisko

V súčasnosti môžeme ukladať iba vektor s 8 bitmi. Aby sme prekročili toto obmedzenie, len musíme použiť pole bajts, namiesto jediného bajt, to je ono!

Teraz, kedykoľvek potrebujeme nastaviť, získať alebo vyčistiť konkrétny index, mali by sme najskôr nájsť zodpovedajúci prvok poľa. Predpokladajme napríklad, že nastavíme index 14:

Ako je znázornené na obrázku vyššie, po nájdení správneho prvku poľa sme nastavili príslušný index.

Pokiaľ tu chceme nastaviť index nad 15, potom BitSet najskôr rozšíri svoje vnútorné pole. Až po rozšírení poľa a skopírovaní prvkov nastaví požadovaný bit. To je do istej miery podobné ako ArrayList pracuje interne.

Doteraz sme používali bajt dátový typ kvôli jednoduchosti. The BitSet API však používa pole dlho hodnoty interne.

4. The BitSet API

Teraz, keď vieme dosť o teórii, je čas zistiť, čo BitSet API vyzerá.

Na úvod si porovnajme pamäťovú stopu a BitSet napríklad s 1024 bitmi s boolean [] videli sme skôr:

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

Týmto sa vytlačí plytká veľkosť súboru BitSet inštancia a veľkosť jeho vnútorného poľa:

[chránené e-mailom] externé objekty: ADRESA VEĽKOSŤ TYPU CESTA HODNOTA 70f97d208 24 java.util.BitSet (objekt) 70f97d220 144 [J. slová [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0]

Ako je uvedené vyššie, používa a dlhé [] so 16 prvkami (16 * 64 bitov = 1024 bitov) interne. Každopádne táto inštancia celkovo využíva 168 bajtov, zatiaľ čo boolean [] využívali 1024 bajtov.

Čím viac bitov máme, tým viac sa zväčšuje stopový rozdiel. Napríklad na uloženie 1024 * 1024 bitov slúži ikona boolean [] spotrebuje 1 MB a BitSet inštancia spotrebuje okolo 130 kB.

4.1. Konštruovanie BitSets

Najjednoduchší spôsob vytvorenia a BitSet inštanciou je použitie konštruktora no-arg:

BitSet bitSet = nový BitSet ();

Týmto sa vytvorí BitSet napríklad s a dlhé [] veľkosti jedna. Toto pole samozrejme môže v prípade potreby automaticky rozšíriť.

Je tiež možné vytvoriť BitSet s počiatočným počtom bitov:

BitSet bitSet = nový BitSet (100_000);

Tu bude mať interné pole dostatok prvkov na uloženie 100 000 bitov. Tento konštruktor sa hodí, keď už máme rozumný odhad počtu bitov, ktoré sa majú uložiť. V takýchto prípadoch použitia môže zabrániť alebo znížiť zbytočné kopírovanie prvkov poľa pri jeho rozširovaní.

Je dokonca možné vytvoriť BitSet z existujúceho dlhé [], byte [], LongBuffera ByteBuffer. Napríklad tu vytvárame a BitSet inštancia z daného dlhé []:

BitSet bitSet = BitSet.valueOf (nové dlhé [] {42, 12});

Existujú tri ďalšie preťažené verzie hodnota() statická továrenská metóda na podporu ostatných spomenutých typov.

4.2. Nastavovanie bitov

Hodnotu konkrétneho indexu môžeme nastaviť na pravda pomocou množina (index) metóda:

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

Ako obvykle, indexy sú založené na nule. Je dokonca možné nastaviť rozsah bitov na pravda pomocou sada (odInclusive, doExclusive) metóda:

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

Ako je zrejmé z podpisu metódy, počiatočný index je inkluzívny a koncový je exkluzívny.

Keď hovoríme o stanovení indexu, máme obvykle na mysli nastavenie pravda. Napriek tejto terminológii môžeme nastaviť konkrétny bitový index na nepravdivé pomocou množina (index, boolean) metóda:

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

Táto verzia podporuje aj nastavenie rozsahu hodnôt:

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

4.3. Čistenie bitov

Namiesto nastavenia konkrétneho bitového indexu na nepravdivé, môžeme to jednoducho vyčistiť pomocou jasný (index) metóda:

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

Okrem toho môžeme tiež vyčistiť celý rad bitov pomocou jasné (od inkluzívneho do exkluzívneho) preťažená verzia:

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

Je zaujímavé, že ak túto metódu zavoláme bez predloženia akýchkoľvek argumentov, vymaže všetky nastavené bity:

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

Ako je uvedené vyššie, po zavolaní na server jasný() metódou sú všetky bity nastavené na nulu.

4.4. Získavanie bitov

Doteraz sme používali získať (index) metóda pomerne obšírne. Keď je nastavený požadovaný bitový index, potom sa táto metóda vráti pravda. V opačnom prípade sa to vráti nepravdivé:

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

Podobný nastaviť a jasný, môžeme získať celý rad bitových indexov pomocou získať (odInclusive, doExclusive) metóda:

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

Ako je uvedené vyššie, táto metóda vracia inú BitSet v rozsahu [20, 30) aktuálneho. To znamená, že index 20 indexu bitSet premenná zodpovedá indexu nula indexu newBitSet premenná.

4.5. Flipping Bits

Na vyvrátenie aktuálnej hodnoty bitového indexu môžeme použiť znak prevrátiť (index) metóda. To znamená, že sa to otočí pravda hodnoty do nepravdivé a naopak:

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

Podobne môžeme dosiahnuť to isté pre celý rad hodnôt pomocou znaku prevrátiť (odInclusive, doExclusive) metóda:

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

4.6. Dĺžka

Existujú tri podobné metódy pre a BitSet. The veľkosť () metóda vracia počet bitov, ktoré môže interné pole predstavovať. Napríklad, pretože konštruktor no-arg alokuje a dlhé [] pole s jedným prvkom, potom veľkosť () za to vráti 64:

BitSet defaultBitSet = nový BitSet (); assertThat (defaultBitSet.size ()). isEqualTo (64);

S jedným 64-bitovým číslom môžeme predstavovať iba 64 bitov. To sa samozrejme zmení, ak explicitne odovzdáme počet bitov:

BitSet bitSet = nový BitSet (1024); assertThat (bitSet.size ()). isEqualTo (1024);

Okrem toho mohutnosť () metóda predstavuje počet nastavených bitov v a BitSet:

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

Najskôr táto metóda vráti nulu, pretože všetky bity sú rovnaké nepravdivé. Po nastavení rozsahu [10, 30) na pravda, potom mohutnosť () volanie metódy vráti 20.

Tiež dĺžka () metóda vráti jeden index za index naposledy nastaveného bitu:

assertThat (bitSet.length ()). isEqualTo (30); bitSet.set (100); assertThat (bitSet.length ()). isEqualTo (101);

Najskôr je posledný nastavený index 29, takže táto metóda vráti 30. Keď nastavíme index 100 na hodnotu true, potom bude hodnota dĺžka () metóda vracia 101. Je tiež potrebné spomenúť, že táto metóda vráti nulu, ak sú všetky bity jasné.

Nakoniec je prázdny() metóda sa vracia nepravdivé keď je v BitSet. V opačnom prípade sa to vráti pravda:

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

4.7. Kombinácia s inými BitSets

The pretína (BitSet) metóda vyžaduje inú BitSet a vráti sa pravda keď dvaja BitSetmajú niečo spoločné. To znamená, že majú najmenej jeden nastavený bit v rovnakom indexe:

BitSet prvý = nový BitSet (); first.set (5, 10); BitSet druhý = nový BitSet (); druhá skupina (7, 15); assertThat (first.intersects (second)). isTrue ();

Rozsah [7, 9] je nastavený v oboch BitSets, takže sa táto metóda vracia pravda.

Je tiež možné vykonať logické a prevádzka na dvoch BitSets:

prvý.a (druhý); assertThat (first.get (7)). isTrue (); assertThat (first.get (8)). isTrue (); assertThat (first.get (9)). isTrue (); assertThat (first.get (10)). isFalse ();

Bude to logické a medzi týmito dvoma BitSets a upravuje najprv premenná s výsledkom. Podobne môžeme vykonať logiku xor na dvoch BitSets tiež:

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

Existujú aj iné metódy, ako napríklad andNot (BitSet) alebo alebo (BitSet),ktoré môžu vykonávať ďalšie logické operácie na dvoch BitSets.

4.8. Zmiešaný

Od verzie Java 8 existuje Prúd() metóda na streamovanie všetkých nastavených bitov a BitSet. Napríklad:

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

Toto vytlačí všetky nastavené bity do konzoly. Pretože toto vráti IntStream, môžeme vykonávať bežné numerické operácie ako súčet, priemer, počítanie atď. Napríklad tu počítame počet nastavených bitov:

assertThat (bitSet.stream (). count ()). isEqualTo (10);

Tiež the nextSetBit (fromIndex) metóda vráti ďalší nastavený bitový index začínajúci sa z odIndex:

assertThat (bitSet.nextSetBit (13)). isEqualTo (15);

The odIndex je do tohto výpočtu zahrnutá. Keď žiadne nie sú pravda trochu zostalo v BitSet, vráti -1:

assertThat (bitSet.nextSetBit (25)). isEqualTo (-1);

Podobne the nextClearBit (fromIndex) vráti nasledujúci jasný index začínajúci od odIndex:

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

Na druhej strane previousClearBit (fromIndex) vráti index najbližšieho jasného indexu v opačnom smere:

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

To isté platí pre previousSetBit (fromIndex):

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

Okrem toho môžeme previesť BitSet do a byte [] alebo a dlhé [] pomocou toByteArray () alebo toLongArray () metódy:

byte [] bytes = bitSet.toByteArray (); long [] longs = bitSet.toLongArray ();

5. Záver

V tomto tutoriáli sme videli, ako môžeme použiť BitSets predstavuje vektor bitov.

Spočiatku sme sa oboznámili s dôvodmi nepoužívania boolean [] reprezentovať vektor bitov. Potom sme videli, ako a BitSet funguje interne a ako vyzerá jeho API.

Ako obvykle sú všetky príklady dostupné na GitHub.