Bitové pole - Bit array

Bitové pole (také známý jako bitové mapy , nastavení bitu , bitového řetězce , nebo bitový vektor ) je datová struktura array že kompaktně ukládá bitů . Lze jej použít k implementaci jednoduché sady datových struktur . Bitové pole je efektivní při využívání paralelismu bitové úrovně v hardwaru k rychlému provádění operací. Typické bitové pole ukládá kw bitů, kde w je počet bitů v jednotce úložiště, například v bajtu nebo slově , a k je nějaké nezáporné celé číslo. Pokud w nerozdělí počet bitů, které mají být uloženy, dojde k plýtvání prostorem kvůli vnitřní fragmentaci .

Definice

Bitové pole je mapování z nějaké domény (téměř vždy celá řada celých čísel) na hodnoty v sadě {0, 1}. Hodnoty lze interpretovat jako tmavé/světlé, nepřítomné/přítomné, zamčené/odemčené, platné/neplatné atd. Jde o to, že existují pouze dvě možné hodnoty, takže je lze uložit do jednoho bitu. Stejně jako u jiných polí lze přístup k jednomu bitu spravovat použitím indexu na pole. Za předpokladu, že jeho velikost (nebo délka) bude n bitů, lze pole použít k určení podmnožiny domény (např. {0, 1, 2, ..., n −1}), kde 1 bit označuje přítomnost a 0-bit absence čísla v sadě. Tato nastavená datová struktura používá přibližně n / w slov prostoru, kde w je počet bitů v každém strojovém slovu . Zda nejméně významný bit (slova) nebo nejvýznamnější bit indikuje číslo s nejmenším indexem, je do značné míry irelevantní, ale první z nich má tendenci být upřednostňován (na strojích s malým endianem ).

Základní operace

Ačkoli většina strojů není schopna adresovat jednotlivé bity v paměti, ani nemá instrukce pro manipulaci s jednotlivými bity, každý bit ve slově lze vyčlenit a manipulovat pomocí bitových operací . Zejména:

NEBO lze nastavit bit na jednu: 11101010 NEBO 00000100 = 11101110
AND lze použít k nastavení bitu na nulu: 11101010 AND 11111101 = 11101000
AND společně s nulovým testováním lze použít k určení, zda je nastaven bit:

11101010 A 00000001 = 00000000 = 0

11101010 A 00000010 = 00000010 ≠ 0
XOR lze použít k invertování nebo přepínání bitů:

11101010 XOR 00000100 = 11101110

11101110 XOR 00000100 = 11101010
Nelze použít k invertování všech bitů.
NE 10110010 = 01001101

Abychom získali bitovou masku potřebnou pro tyto operace, můžeme pomocí operátoru bitového posunu posunout číslo 1 doleva o příslušný počet míst a v případě potřeby také bitovou negaci .

Vzhledem k tomu, že dvě bitová pole stejné velikosti představují sady, můžeme vypočítat jejich sjednocení , průnik a teoretický rozdíl množin pomocí n / w jednoduchých bitových operací (2 n / w pro rozdíl), stejně jako doplněk buď:

for i from 0 to n/w-1
    complement_a[i] := not a[i]
    union[i]        := a[i] or b[i]
    intersection[i] := a[i] and b[i]
    difference[i]   := a[i] and (not b[i])

Pokud chceme iterovat bity bitového pole, můžeme to udělat efektivně pomocí dvojitě vnořené smyčky, která prochází každým slovem, jeden po druhém. Jsou vyžadovány pouze přístupy k paměti n / w :

for i from 0 to n/w-1
    index := 0    // if needed
    word := a[i]
    for b from 0 to w-1
        value := word and 1 ≠ 0
        word := word shift right 1
        // do something with value
        index := index + 1    // if needed

Oba tyto ukázky kódu vykazují ideální referenční lokalitu , která následně získá velké zvýšení výkonu z mezipaměti dat. Pokud je řádek mezipaměti k slov, dojde pouze k n / wk vynechání mezipaměti.

Složitější operace

Stejně jako u řetězců znaků je jednoduché definovat délku , podřetězec , lexikografické srovnání , zřetězení , reverzní operace. Implementace některých z těchto operací je citlivá na endianness .

Hmotnost populace / Hamming

Chceme-li najít počet 1 bitů v bitovém poli, někdy nazývaném počet obyvatel nebo Hammingova váha, existují účinné algoritmy bez větví, které dokážou vypočítat počet bitů ve slově pomocí řady jednoduchých bitových operací. Jednoduše spustíme takový algoritmus pro každé slovo a udržujeme průběžný součet. Počítání nul je podobné. Příklady efektivní implementace najdete v článku Hammingova váha .

Inverze

Vertikální převrácení obrázku s bitem na pixel nebo některé algoritmy FFT vyžaduje převrácení bitů jednotlivých slov (tak se b31 b30 ... b0stane b0 ... b30 b31). Když tato operace není k dispozici na procesoru, je stále možné postupovat po sobě jdoucími průchody, v tomto případě na 32 bitů:

exchange two 16-bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

Najděte první

Operace find first set or find first one identifikuje index nebo pozici 1-bit s nejmenším indexem v poli a má rozsáhlou hardwarovou podporu (pro pole ne větší než slovo) a efektivní algoritmy pro její výpočet. Je -li fronta priorit uložena v bitovém poli, lze k identifikaci prvku s nejvyšší prioritou ve frontě použít funkci find first. Chcete-li rozšířit velikost slova najít první na delší pole, můžete najít první nenulové slovo a poté spustit najít první u tohoto slova. Související operace najít první nulu , počet počáteční nuly , počítat ty přední , počet koncových nul , počítat koncové ty , a log základnu 2 (viz zde první set ) může být také rozšířena na bitové pole v přímočaře.

Komprese

Bitové pole je nejhustší úložiště pro „náhodné“ bity, to znamená, že každý bit má stejnou pravděpodobnost 0 nebo 1 a každý je nezávislý. Většina dat ale není náhodná, takže je možné je uložit kompaktněji. Data typického faxového obrázku například nejsou náhodná a lze je komprimovat. Ke kompresi těchto dlouhých proudů se běžně používá kódování za běhu . Většina komprimovaných datových formátů však není tak snadno přístupná náhodně; také příliš agresivním komprimováním bitových polí riskujeme ztrátu výhod v důsledku paralelismu bitové úrovně ( vektorizace ). Místo komprimace bitových polí jako toků bitů je tedy můžeme komprimovat jako proudy bajtů nebo slov (viz Bitmapový index (komprese) ).

Výhody a nevýhody

Bitová pole mají navzdory své jednoduchosti oproti jiným datovým strukturám pro stejné problémy řadu výrazných výhod:

Jsou extrémně kompaktní; žádné jiné datové struktury nemohou ukládat n nezávislých částí dat do n / w slov.
Umožňují ukládat a manipulovat s malými poli bitů v registru nastaveném po dlouhou dobu bez přístupu do paměti.
Díky své schopnosti využívat paralelismus na úrovni bitů, omezovat přístup k paměti a maximálně využívat mezipaměť dat často překonávají mnoho jiných datových struktur v praktických sadách dat, dokonce i těch, které jsou asymptoticky efektivnější.

Bitová pole však nejsou řešením všeho. Zejména:

Bez komprese jsou to nehospodárné množinové datové struktury pro řídké množiny (ty s několika prvky ve srovnání s jejich rozsahem) v čase i prostoru. U takových aplikací by místo toho měla být zvážena komprimovaná bitová pole, Judyho pole , pokusy nebo dokonce Bloom filtry .
Přístup k jednotlivým prvkům může být v některých jazycích nákladný a obtížně vyjádřitelný. Pokud je náhodný přístup běžnější než sekvenční a pole je relativně malé, může být na počítači s adresou bajtů upřednostněno pole bajtů. Pole slov však pravděpodobně není oprávněné kvůli obrovské režii prostoru a dalším chybám mezipaměti, které způsobuje, pokud stroj nemá pouze adresování slov.

Aplikace

Díky své kompaktnosti mají bitová pole řadu aplikací v oblastech, kde je prostor nebo účinnost na špičkové úrovni. Nejčastěji se používají k reprezentaci jednoduché skupiny booleovských příznaků nebo uspořádané posloupnosti booleovských hodnot.

Bitová pole se používají pro prioritní fronty , kde je bit v indexu k nastaven právě tehdy, pokud je k ve frontě; tato datová struktura je používána například jádrem Linuxu a má velký prospěch z hardwarové operace find-first-zero.

Bitová pole lze použít k přidělení paměťových stránek , inodů , diskových sektorů atd. V takových případech může být použit termín bitmapa . Tento termín je však často používán k označení rastrových obrázků , které mohou používat více bitů na pixel .

Další aplikací bitových polí je filtr Bloom , což je pravděpodobnostní datová struktura sady, která může ukládat velké sady na malém prostoru výměnou za malou pravděpodobnost chyby. Je také možné vytvářet pravděpodobnostní hashovací tabulky založené na bitových polích, která přijímají buď falešně pozitivní, nebo falešně negativní.

Bitová pole a operace s nimi jsou také důležité pro konstrukci stručných datových struktur , které využívají téměř minimální možný prostor. V této souvislosti je operace, jako najít n th 1 bit nebo spočítáním 1 bitů do určité polohy stanou významnými.

Bitová pole jsou také užitečnou abstrakcí pro zkoumání proudů komprimovaných dat, která často obsahují prvky, které zabírají části bajtů nebo nejsou zarovnané na bajty. Například komprimovaná Huffmanova kódovací reprezentace jednoho 8bitového znaku může mít libovolnou délku od 1 do 255 bitů.

Při získávání informací jsou bitová pole dobrou reprezentací pro seznamy účtů velmi častých výrazů. Pokud vypočítáme mezery mezi sousedními hodnotami v seznamu přísně rostoucích celých čísel a zakódujeme je pomocí unárního kódování , výsledkem je bitové pole s 1 bitem na n -té pozici právě tehdy, když je n v seznamu. Implicitní pravděpodobnost mezery n je 1/2 ⁿ . Toto je také speciální případ Golombova kódování, kde parametr M je 1; tento parametr je normálně vybrán pouze v případě, že -log (2- p )/log (1- p ) ≤ 1, nebo zhruba termín se vyskytuje alespoň v 38% dokumentů.

Jazyková podpora

APL programovací jazyk plně podporuje přenosové matice libovolného tvaru a velikosti jako Boolean datový typ odlišný od čísel. Všechny hlavní implementace ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL atd.) Balí bity hustě do jakékoli velikosti strojového slova. K bitům lze přistupovat jednotlivě pomocí obvyklého indexačního zápisu (A [3]), jakož i prostřednictvím všech obvyklých primitivních funkcí a operátorů, kde jsou často provozovány pomocí algoritmu pro speciální případy, jako je sčítání bitů pomocí vyhledávání tabulek v bajtech .

V programovacím jazyku C ‚s bitových polí , pseudo-objekty nalezené v structs s velikostí rovná určitý počet bitů, jsou ve skutečnosti malý kousek pole; jsou omezeni tím, že nemohou překlenout slova. Ačkoli poskytují pohodlnou syntaxi, k bitům se na většině počítačů stále přistupuje pomocí bajtových operátorů a lze je definovat pouze staticky (jako statická pole C jsou jejich velikosti v době kompilace pevné). Pro C programátory je také běžným idiomem používat slova jako malá bitová pole a přistupovat k jejich bitům pomocí bitových operátorů. Široce dostupný soubor záhlaví obsažený v systému X11 , xtrapbits.h, je „přenosný způsob, jak systémy definují manipulaci s bitovými poli polí bitů“. Více vysvětlující popis výše uvedeného přístupu lze nalézt v comp.lang.c faq .

V C ++ , i když individuální bools typicky zaujímají stejný prostor jako bajtu nebo celé číslo, STL typ vector<bool>je částečný šablona obor , ve kterém jsou bity baleny jako optimalizace na prostor účinnosti. Vzhledem k tomu, bajtů (a ne bitů) jsou nejmenší adresovatelná jednotka v jazyce C ++, operátor [] se nebude vracet odkaz na prvek, ale místo toho vrátí proxy server reference . Může se to zdát jako nepodstatný bod, ale znamená to, že vector<bool>to není standardní kontejner STL, a proto se použití vector<bool>obecně nedoporučuje. Další jedinečná třída STL bitset, vytváří vektor bitů fixovaných v určité velikosti v době kompilace a svým rozhraním a syntaxí se více podobá idiomatickému používání slov jako bitových sad programátory C. Má také další výkon, například schopnost efektivně počítat počet bitů, které jsou nastaveny. Tyto * Zvyšuje C ++ knihovny poskytují dynamic_bitsettřídu, jejíž velikost je určena při spuštění.

D programovací jazyk poskytuje bitových polí ve standardní knihovně, Phobos, v std.bitmanip. Stejně jako v C ++ operátor [] nevrací odkaz, protože jednotlivé bity nejsou na většině hardwaru přímo adresovatelné, ale místo toho vrací a bool.

V Javě třída BitSetvytvoří bitové pole, se kterým se poté manipuluje s funkcemi pojmenovanými podle bitových operátorů známých programátorům C. Na rozdíl od bitsetC ++ BitSetnemá Java stav „size“ (má efektivně nekonečnou velikost, inicializovanou 0 bity); bit lze nastavit nebo vyzkoušet v libovolném indexu. Kromě toho existuje třída EnumSet, která představuje sadu hodnot výčtového typu interně jako bitový vektor, jako bezpečnější alternativu bitových polí.

Rozhraní .NET Framework poskytuje BitArraytřídu kolekce. Ukládá bity pomocí pole typu int(každý prvek v poli obvykle představuje 32 bitů). Třída podporuje náhodný přístup a bitové operátory, lze ji iterovat a její Lengthvlastnost lze změnit tak, aby rostla nebo byla zkrácena.

Ačkoli Standard ML nemá podporu pro bitová pole, Standard ML v New Jersey má BitArrayve své knihovně SML/NJ rozšíření, strukturu. Nemá pevnou velikost a podporuje nastavené operace a bitové operace, včetně neobvykle směnných operací.

Haskell také v současné době postrádá standardní podporu pro bitové operace, ale GHC i Hugs poskytují Data.Bitsmodul s různými bitovými funkcemi a operátory, včetně operací posunu a otočení a k modelování bitového pole lze použít pole „unboxed“ přes booleovské hodnoty, ačkoli toto postrádá podporu z bývalého modulu.

V Perlu lze řetězce použít jako rozšiřitelná bitová pole. Lze s nimi manipulovat pomocí obvyklých bitových operátorů ( ~ | & ^) a jednotlivé bity lze testovat a nastavovat pomocí funkce vec .

V Ruby můžete přistupovat (ale ne nastavit) ke kousku celého čísla ( Fixnumnebo Bignum) pomocí držáku operátor ( []), jako by to bylo pole bitů.

Knihovna Apple Core Foundation obsahuje struktury CFBitVector a CFMutableBitVector .

PL/I podporuje pole bitových řetězců libovolné délky, které mohou mít pevnou délku nebo se mohou lišit. Prvky pole mohou být zarovnány - každý prvek začíná na hranici bajtů nebo slov - nebo nezarovnané - prvky na sebe bezprostředně navazují bez odsazení.

PL/pgSQL a PostgreSQL SQL podporují bitové řetězce jako nativní typ. Existují dva typy bitů SQL: a , kde je kladné celé číslo. bit(n)bit varying(n)n

Jazyky popisu hardwaru, jako jsou VHDL , Verilog a SystemVerilog, nativně podporují bitové vektory, protože se používají k modelování úložných prvků, jako jsou klopné obvody , hardwarové sběrnice a hardwarové signály obecně. V jazycích ověřování hardwaru, jako jsou OpenVera , e a SystemVerilog , se bitové vektory používají k vzorkování hodnot z hardwarových modelů a k reprezentaci dat, která jsou během simulací přenášena na hardware.

Common Lisp poskytuje jednorozměrnou bit-vectorimplementaci jako speciální případ vestavěné funkce array, která funguje jako duální kapacita jako specifikátor třídy a typu. Jelikož je derivátem pole, spoléhá na obecnou make-arrayfunkci, která má být konfigurována s typem prvku bit, který případně umožňuje, aby bitový vektor byl označen jako dynamicky měnitelný. Rozsah bit-vectorvšak není nekonečný. Existuje omezenější simple-bit-vectortyp, který výslovně vylučuje dynamické charakteristiky. Bitové vektory jsou reprezentovány jako a mohou být konstruovány stručnějším způsobem pomocí čtecího makra . Kromě obecných funkcí platných pro všechna pole existují pro bitové vektory vyhrazené operace. Jednotlivé bity mohou být přístupné a měnit tlačítky a funkcí a je podporován rozsáhlý počet logických operací. #*bitsbitsbit

Languages

In other projects