streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megnézzük, hogyan használhatjuk BitSets a bitek vektorának képviseletére.

Először azzal kezdjük, hogy miért nem használjuk a logikai []. Majd miután megismerte a BitSet belsőleg, közelebbről megvizsgáljuk az API-ját.

2. Bit tömb

A bittömbök tárolására és kezelésére azt lehet mondani, hogy használnunk kell logikai [] mint az adatstruktúránk. Első pillantásra ez ésszerű javaslatnak tűnhet.

Mindazonáltal logikai tag a logikai [] általában csak egy bit helyett egy bájtot fogyaszt. Tehát, ha szűk memóriaigényünk van, vagy csak a memóriaterület csökkentésére törekszünk, logikai [] messze nem ideálisak.

A dolgok konkrétabbá tétele érdekében nézzük meg, mennyi hely van a logikai [] 1024 elemmel fogyaszt:

logikai [] bitek = új logikai [1024]; System.out.println (ClassLayout.parseInstance (bits) .toPrintable ());

Ideális esetben 1024 bites memóriaméretet várunk ettől a tömbtől. A Java Object Layout (JOL) azonban egy teljesen más valóságot tár fel:

[Z objektum belső részei: OFFSET MÉRET TÍPUS LEÍRÁS ÉRTÉK 0 4 (objektum fejléc) 01 00 00 00 (00000001 00000000 00000000 00000000) (1) 4 4 (objektum fejléc) 00 00 00 00 (00000000 00000000 00000000 00000000) (0) 8 4 (objektum fejléc) 7b 12 07 00 (01111011 00010010 00000111 00000000) (463483) 12 4 (objektum fejléc) 00 04 00 00 (00000000 00000100 00000000 00000000) (1024) 16 1024 logikai érték [Z. N / A Példányméret: 1040 bájt

Ha figyelmen kívül hagyjuk az objektum fejlécének fejlécét, a tömb elemek 1024 bájtot fogyasztanak a várt 1024 bit helyett. Ez 700% -kal több memóriát jelent, mint amire számítottunk.

Aa címezhetőség kérdése és a szószakadás a legfőbb oka annak logikais nem csak egyetlen bit.

A probléma megoldásához numerikus adattípusok kombinációját használhatjuk (például hosszú) és bitenkénti műveletek. Ott a BitSet bejön.

3. Hogyan BitSet Művek

Amint azt korábban említettük, a zászlónkénti egy bit eléréséhez a BitSet Az API az alapvető numerikus adattípusok és a bitenkénti műveletek kombinációját használja.

Tegyük fel, hogy az egyszerűség kedvéért nyolc zászlót fogunk képviselni byte. Eleinte inicializáljuk a kislemez összes bitjét byte nullával:

Most, ha a bitet a harmadik pozícióba akarjuk állítani igaz, először az első számot kell balra tolnunk hárommal:

És akkor vagy eredménye az árammal byte érték:

Ugyanez történik, ha úgy dönt, hogy a bitet a hét indexbe állítja:

Amint a fentiekből látható, bal bit eltolást hajtunk végre hét bittel, és az eredményt kombináljuk az előzővel byte érték a vagy operátor.

3.1. Bit index megszerzése

Annak ellenőrzése, hogy egy adott bit index értéke-e igaz vagy sem, használjuk a és operátor. Például a következőképpen ellenőrizzük, hogy a három index be van-e állítva:

1. Hajtsa végre a bal eltolást három bittel az első értéken
2. Anding az eredmény az árammal byte érték
3. Ha az eredmény nagyobb, mint nulla, akkor találtunk egyezést, és ez a bit index valóban be van állítva. Ellenkező esetben a kért index egyértelmű vagy egyenlő hamis

A fenti ábra a get index művelet lépéseit mutatja a harmadik indexhez. Ha egyértelmű indexről érdeklődünk, akkor az eredmény más lesz:

Mivel a és az eredmény nulla, a négy mutató egyértelmű.

3.2. A tároló termesztése

Jelenleg csak 8 bites vektort tárolhatunk. Ezen a korláton túllépve, csak egy tömböt kell használnunk bytes, egyetlen helyett byte, ez az!

Most, amikor egy adott indexet kell beállítanunk, megszereznünk vagy törölnünk kell, először meg kell találnunk a megfelelő tömb elemet. Tegyük fel például, hogy a 14. indexet állítjuk be:

Amint a fenti ábra mutatja, miután megtaláltuk a megfelelő tömb elemet, beállítottuk a megfelelő indexet.

Továbbá, ha itt 15-nél nagyobb indexet akarunk beállítani, akkor a BitSet először belső tömbjét bővíti. Csak a tömb kibővítése és az elemek másolása után állítja be a kért bitet. Ez némileg hasonlít ahhoz, hogy hogyan Tömb lista belsőleg működik.

Eddig a byte adattípus az egyszerűség kedvéért. A BitSet Az API azonban egy tömböt használ hosszú értékeket belsőleg.

4. A BitSet API

Most, hogy eleget tudunk az elméletről, itt az ideje, hogy lássuk, mi az BitSet Az API úgy néz ki.

Kezdőként hasonlítsuk össze a memória lábnyomát BitSet például 1024 bitrel a logikai [] láttuk korábban:

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

Ezzel kinyomtatja a BitSet példány és a belső tömb mérete:

[e-mail védett] objektum külsők: CÍM MÉRET TÍPUS PATH VALUE 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]

A fentiek szerint a hosszú[] 16 elemmel (16 * 64 bit = 1024 bit) belülről. Egyébként is, ez a példány összesen 168 bájtot használ, míg a logikai [] 1024 bájtot használtak.

Minél több bitünk van, annál jobban nő a lábnyomkülönbség. Például 1024 * 1024 bit tárolásához a logikai [] 1 MB-ot fogyaszt, és a BitSet példány körülbelül 130 KB-ot fogyaszt.

4.1. Konstrukció BitSets

A legegyszerűbb módszer a BitSet Például a no-arg konstruktort kell használni:

BitSet bitSet = new BitSet ();

Ez létrehozza a BitSet például egy hosszú[] egy méretű. Természetesen automatikusan növelheti ezt a tömböt, ha szükséges.

Lehetőség van a BitSet kezdeti bitszámmal:

BitSet bitSet = új BitSet (100_000);

Itt a belső tömbben elegendő elem lesz 100 000 bit tárolására. Ez a konstruktor akkor hasznos, ha már van ésszerű becslésünk a tárolandó bitek számáról. Ilyen használati esetekben megakadályozhatja vagy csökkentheti a tömb elemek felesleges másolását, miközben növekszik.

Még lehetséges a BitSet egy létezőtől hosszú[], byte[], LongBuffer, és ByteBuffer. Például itt létrehozunk egy BitSet egy adott példány hosszú[]:

BitSet bitSet = BitSet.valueOf (új hosszú [] {42, 12});

A programnak még három túlterhelt változata van értéke() statikus gyári módszer a többi említett típus támogatására.

4.2. Bitek beállítása

Beállíthatjuk egy adott index értékét igaz használni a készlet (index) módszer:

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

Az indexek szokás szerint nulla alapúak. Még egy bit tartományt is beállíthat igaz használni a készlet (fromInclusive, toExclusive) módszer:

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

Amint a metódus aláírásából kitűnik, a kezdő index inkluzív, a vége pedig exkluzív.

Amikor azt mondjuk, hogy indexet állítunk be, akkor általában azt értjük, hogy azt állítsuk be igaz. E terminológia ellenére beállíthatunk egy adott bit indexet hamis használni a készlet (index, logikai érték) módszer:

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

Ez a verzió támogatja az értéktartomány beállítását is:

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

4.3. Bit törlése

Ahelyett, hogy egy adott bit indexet állítana hamis, egyszerűen törölhetjük a tiszta (index) módszer:

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

Sőt, a bitekkel egy sor bitet is törölhetünk tiszta (fromInclusive, toExclusive) túlterhelt verzió:

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

Érdekes módon, ha argumentum nélkül adjuk meg ezt a módszert, akkor az összes beállított bitet törli:

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

A fentiek szerint, miután felhívtuk a egyértelmű() módszerrel az összes bit nullára van állítva.

4.4. Bitek megszerzése

Eddig a get (index) módszer elég széles körben. Ha a kért bit index be van állítva, akkor ez a módszer visszatér igaz. Ellenkező esetben visszatér hamis:

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

Hasonló készlet és egyértelmű, a bit használatával számos indexet kaphatunk get (fromInclusive, toExclusive) módszer:

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

Amint az fent látható, ez a módszer egy másikat ad vissza BitSet a jelenlegi [20, 30) tartományában. Vagyis a bitSet változó egyenlő a newBitSet változó.

4.5. Megfordított bitek

Az aktuális bitindex-érték tagadására használhatjuk a flip (index) módszer. Vagyis megfordul igaz értékeket hamis és fordítva:

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

Hasonlóképpen elérhetjük ugyanazt az értéktartományra a flip (fromInclusive, toExclusive) módszer:

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

4.6. Hossz

Három hossz-szerű módszer létezik a BitSet. A méret() metódus adja vissza a belső tömb által képviselt bitek számát. Például, mivel a no-arg konstruktor lefoglal egy hosszú[] tömb egy elemmel, majd a méret() 64-et ad vissza érte:

BitSet defaultBitSet = new BitSet (); assertThat (alapértelmezettBitSet.size ()). isEqualTo (64);

Egy 64 bites számmal csak 64 bitet tudunk képviselni. Természetesen ez megváltozik, ha kifejezetten átadjuk a bitek számát:

BitSet bitSet = új BitSet (1024); assertThat (bitSet.size ()). isEqualTo (1024);

Sőt, a kardinalitás () metódus az a-ban megadott bitek számát jelenti BitSet:

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

Eleinte ez a módszer nullát ad vissza, mint minden bit hamis. Miután beállította a [10, 30) tartományt igaz, aztán a kardinalitás () metódus hívás 20

Továbbá a hossz() metódus az utolsó beállított bit indexe utáni egy indexet adja vissza:

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

Eleinte az utolsó beállított index 29, tehát ez a módszer 30-at ad vissza. Amikor a 100 indexet igazra állítjuk, akkor a hossz() metódus 101-et ad vissza. Érdemes megemlíteni azt is, hogy ez a módszer nullát ad vissza, ha minden bit tiszta.

Végül a üres() metódus visszatér hamis amikor legalább egy beállított bit van a BitSet. Ellenkező esetben visszatér igaz:

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

4.7. Kombinálás másokkal BitSets

A metszi (BitSet) A módszer egy másikat igényel BitSet és visszatér igaz amikor kettő BitSetvan valami közös. Vagyis legalább egy készlet bit van ugyanabban az indexben:

BitSet first = új BitSet (); első.halmaz (5, 10); BitSet second = új BitSet (); második készlet (7, 15); assertThat (első. közbeiktatja (második)). igaz ();

A [7, 9] tartomány mindkettőben be van állítva BitSets, így ez a módszer visszatér igaz.

Lehetséges a logikai műveletek végrehajtása is és kettőn végzett művelet BitSets:

első.és (második); assertThat (first.get (7)). isTrue (); assertThat (first.get (8)). isTrue (); assertThat (first.get (9)). isTrue (); assertThat (first.get (10)). isFalse ();

Ez logikusan fog végrehajtani és a kettő között BitSets módosítja a első változó az eredménnyel. Hasonlóképpen elvégezhetünk egy logikai műveletet is xor kettőn BitSets is:

első.tiszta (); első.halmaz (5, 10); első.xor (második); mert (int i = 5; i <7; i ++) {assertThat (first.get (i)). is True (); } for (int i = 10; i <15; i ++) {assertThat (first.get (i)). isTrue (); }

Vannak más módszerek is, például a andNot (BitSet) vagy a vagy (BitSet),amely kettőn más logikai műveletet is képes végrehajtani BitSets.

4.8. Vegyes

A Java 8-tól kezdve van egy folyam() módszer az a BitSet. Például:

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

Ez kinyomtatja az összes beállított bitet a konzolra. Mivel ez egy IntStream, elvégezhetünk olyan általános numerikus műveleteket, mint az összegzés, az átlag, a számlálás stb. Például itt számoljuk a beállított bitek számát:

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

Is, a nextSetBit (fromIndex) metódus a következő beállított bit indexet adja vissza a fromIndex:

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

A fromIndex maga is benne van ebben a számításban. Amikor nincs igaz kicsit maradt a BitSet, -1-re tér vissza:

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

Hasonlóképpen, a nextClearBit (fromIndex) a következő tiszta indexet adja vissza a fromIndex:

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

Másrészt a előzőClearBit (fromIndex) a legközelebbi tiszta index indexét adja vissza az ellenkező irányba:

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

Ugyanez vonatkozik előzőSetBit (fromIndex):

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

Sőt, átalakíthatjuk a BitSet a byte[] vagy a hosszú[] használni a toByteArray () vagy toLongArray () módszerek, ill.

bájt [] bájt = bitSet.toByteArray (); long [] longs = bitSet.toLongArray ();

5. Következtetés

Ebben az oktatóanyagban láttuk, hogyan használhatjuk BitSets a bitek vektorának képviseletére.

Eleinte megismertük a nem használat indokait logikai [] bitek vektorának képviseletére. Aztán láttuk, hogy a BitSet belül működik, és hogyan néz ki az API.

Szokás szerint az összes példa elérhető a GitHubon.