Bitarray

En bitmatris (även känd som bitmask , bitmapp , bituppsättning , bitsträng eller bitvektor ) är en matrisdatastruktur som kompakt lagrar bitar . Den kan användas för att implementera en enkel uppsättning datastruktur . En bitarray är effektiv för att utnyttja bitnivåparallellism i hårdvara för att utföra operationer snabbt. En typisk bitmatris lagrar kw -bitar, där w är antalet bitar i lagringsenheten, såsom en byte eller ett ord , och k är något icke-negativt heltal. Om w inte delar antalet bitar som ska lagras, slösas en del utrymme på grund av intern fragmentering .

Definition

En bitarray är en mappning från någon domän (nästan alltid ett intervall av heltal) till värden i mängden {0, 1}. Värdena kan tolkas som mörkt/ljus, frånvarande/närvarande, låst/olåst, giltigt/ogiltigt, et cetera. Poängen är att det bara finns två möjliga värden, så de kan lagras i en bit. Som med andra arrayer kan åtkomsten till en enstaka bit hanteras genom att applicera ett index på arrayen. Om man antar att dess storlek (eller längd) är n bitar, kan matrisen användas för att specificera en delmängd av domänen (t.ex. {0, 1, 2, ..., n −1}), där en 1-bit anger närvaro och en 0-bit frånvaron av ett nummer i uppsättningen. Denna uppsättning datastruktur använder ungefär n / w ord av rymden, där w är antalet bitar i varje maskinord . Huruvida den minst signifikanta biten (av ordet) eller den mest signifikanta biten indikerar det minsta indextalet är i stort sett irrelevant, men den förra tenderar att vara att föredra (på maskiner med liten endian ).

Grundläggande operationer

Även om de flesta maskiner inte kan adressera enskilda bitar i minnet och inte heller har instruktioner för att manipulera enstaka bitar, kan varje bit i ett ord pekas ut och manipuleras med hjälp av bitvisa operationer . Särskilt:

  • ELLER för att ställa in en bit till ett: 11101010 ELLER 00000100 = 11101110
  • AND för att sätta en bit till noll: 11101010 OCH 11111101 = 11101000
  • OCH för att avgöra om en bit är satt, genom nolltestning:
    11101010 OCH 00000001 = 00000000 = 0
    11101010 OCH 00000010 = 00000010 ≠ 0
  • XOR för att invertera eller växla lite:
    11101010 XOR 00000100 = 11101110
    11101110 XOR 00000100 = 11101010
  • INTE för att invertera alla bitar.
    INTE 10110010 = 01001101

För att få den bitmask som behövs för dessa operationer kan vi använda en bitskiftsoperator för att flytta siffran 1 åt vänster med lämpligt antal platser, samt bitvis negation om det behövs.

Med tanke på två bitarrayer av samma storlek som representerar mängder, kan vi beräkna deras union , intersection och set-teoretiska skillnad med hjälp av n / w enkla bitoperationer vardera (2 n / w för skillnad), såväl som komplementet av antingen: 

 0  för  i  från  till  n/w-1 komplement_a[i] :=  inte  a[i] union[i] := a[i]  eller  b[i] skärningspunkt[i] := a[i]  och  b[i] skillnad[i] := a[i]  och  (  inte  b[i])

Om vi ​​vill iterera genom bitarna i en bitarray kan vi göra detta effektivt med hjälp av en dubbelt kapslad loop som loopar genom varje ord, ett i taget. Endast n / w minnesåtkomst krävs: 

 för  i  från  0 till n/w-1 index := 0 // vid behov ord := a[i]  för  b  från  0 till w-1 värde := ord  och  1 ≠ 0 ord := ordskift höger 1 // gör något med värdeindex := index + 1 // om det behövs

Båda dessa kodexempel uppvisar idealisk referenslokalitet , som sedan kommer att få en stor prestandaökning från en datacache. Om en cache-rad består av k ord kommer endast ca n / wk cachemissar att inträffa.

Mer komplexa operationer

Precis som med teckensträngar är det enkelt att definiera längd , delsträng , lexikografisk jämförelse , sammanlänkning , omvända operationer. Genomförandet av några av dessa operationer är känsligt för endianness .

Befolkning / Hamming vikt

Om vi ​​vill hitta antalet 1 bitar i en bitarray, ibland kallad populationsräkning eller Hamming-vikt, finns det effektiva grenfria algoritmer som kan beräkna antalet bitar i ett ord med hjälp av en serie enkla bitoperationer. Vi kör helt enkelt en sådan algoritm på varje ord och håller en löpande summa. Att räkna nollor är liknande. Se Hamming vikt -artikeln för exempel på en effektiv implementering.

Inversion

Vertikal vändning av en en-bit-per-pixel-bild, eller vissa FFT-algoritmer, kräver vändning av bitarna av enskilda ord (så att b31 b30 ... b0 blir b0 ... b30 b31 ). När den här operationen inte är tillgänglig på processorn är det fortfarande möjligt att fortsätta med successiva övergångar, i det här exemplet på 32 bitar: 

utbyta två 16-bitars halvord byte byte med par (0xddccbbaa -> 0xccddaabb) ... byta bitar med par byta bitar (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1) Den sista operationen kan skrivas ( (x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

Hitta den första

Operationen find first set eller find first one identifierar indexet eller positionen för 1-biten med det minsta indexet i en array, och har utbrett hårdvarustöd (för arrayer som inte är större än ett ord) och effektiva algoritmer för dess beräkning. När en prioritetskö är lagrad i en bitarray, kan find first one användas för att identifiera det högsta prioritetselementet i kön. För att expandera en ordstorlek, hitta först ett till längre arrayer, kan man hitta det första ordet som inte är noll och sedan köra hitta det första på det ordet. De relaterade operationerna hitta första noll , räkna inledande nollor , räkna inledande ettor , räkna efterföljande nollor , räkna efterföljande ettor och loggbas 2 (se hitta första uppsättningen ) kan också utökas till en bitarray på ett enkelt sätt.

Kompression

En bitarray är den mest täta lagringen för "slumpmässiga" bitar, det vill säga där varje bit är lika sannolikt att vara 0 eller 1, och var och en är oberoende. Men de flesta data är inte slumpmässiga, så det kan vara möjligt att lagra det mer kompakt. Till exempel är data från en typisk faxbild inte slumpmässig och kan komprimeras. Run-length-kodning används vanligtvis för att komprimera dessa långa strömmar. De flesta komprimerade dataformat är dock inte så lätta att komma åt slumpmässigt; också genom att komprimera bitarrayer för aggressivt riskerar vi att förlora fördelarna på grund av parallellitet på bitnivå ( vektorisering ). Istället för att komprimera bitmatriser som strömmar av bitar, kan vi alltså komprimera dem som strömmar av byte eller ord (se Bitmapindex (komprimering) ) .

Fördelar och nackdelar

Bitarrayer har, trots sin enkelhet, ett antal markanta fördelar jämfört med andra datastrukturer för samma problem:

  • De är extremt kompakta; inga andra datastrukturer kan lagra n oberoende bitar av data i n / w ord.
  • De tillåter små uppsättningar av bitar att lagras och manipuleras i registeruppsättningen under långa tidsperioder utan minnesåtkomst.
  • På grund av deras förmåga att utnyttja parallellitet på bitnivå, begränsa minnesåtkomst och maximalt använda datacache, överträffar de ofta många andra datastrukturer på praktiska datamängder, även de som är mer asymptotiskt effektiva.

Bitarrayer är dock inte lösningen på allt. Särskilt:

  • Utan komprimering är de slösaktiga uppsättningsdatastrukturer för glesa uppsättningar (de med få element jämfört med deras räckvidd) i både tid och rum. För sådana applikationer bör komprimerade bitarrayer, Judy-arrayer , försök eller till och med Bloom-filter övervägas istället.
  • Att komma åt enskilda element kan vara dyrt och svårt att uttrycka på vissa språk. Om slumpmässig åtkomst är vanligare än sekventiell och arrayen är relativt liten, kan en byte-array vara att föredra på en maskin med byte-adressering. En ordmatris är dock troligen inte motiverad på grund av det enorma utrymmet och ytterligare cachemissar som det orsakar, om inte maskinen bara har ordadressering.

Ansökningar

På grund av sin kompakthet har bitarrayer ett antal applikationer i områden där utrymme eller effektivitet är i högsta grad. Oftast används de för att representera en enkel grupp av booleska flaggor eller en ordnad sekvens av booleska värden.

Bitmatriser används för prioritetsköer , där biten vid index k sätts om och endast om k finns i kön; denna datastruktur används till exempel av Linux-kärnan och drar stor nytta av en hitta-först-noll-operation i hårdvara.

Bitmatriser kan användas för allokering av minnessidor , inoder , disksektorer, etc. I sådana fall kan termen bitmapp användas. Den här termen används dock ofta för att referera till rasterbilder , som kan använda flera bitar per pixel .

En annan tillämpning av bitmatriser är Bloom-filtret , en probabilistisk datastruktur som kan lagra stora uppsättningar i ett litet utrymme i utbyte mot en liten sannolikhet för fel. Det är också möjligt att bygga probabilistiska hashtabeller baserade på bitarrayer som accepterar antingen falska positiva eller falska negativa.

Bitarrayer och operationerna på dem är också viktiga för att konstruera kortfattade datastrukturer , som använder nära minsta möjliga utrymme. I detta sammanhang blir operationer som att hitta den n: te 1 biten eller att räkna antalet 1 bitar upp till en viss position viktiga.

Bitarrayer är också en användbar abstraktion för att undersöka strömmar av komprimerad data, som ofta innehåller element som upptar delar av byte eller inte är bytejusterade. Till exempel kan den komprimerade Huffman- kodningsrepresentationen av ett enda 8-bitars tecken vara allt från 1 till 255 bitar lång.

Vid informationshämtning är bitarrayer en bra representation för postningslistor med mycket frekventa termer. Om vi ​​beräknar gapen mellan intilliggande värden i en lista med strikt ökande heltal och kodar dem med hjälp av unär kodning , blir resultatet en bitarray med en 1 bit i den n :te positionen om och endast om n finns i listan. Den implicita sannolikheten för ett gap på n är 1/2 n . Detta är också specialfallet med Golomb-kodning där parametern M är 1; denna parameter väljs normalt endast när −log(2 − p ) / log(1 − p ) ≤ 1 , eller ungefär termen förekommer i minst 38 % av dokumenten.

Språkstöd

APL -programmeringsspråket stöder fullt ut bitarrayer av godtycklig form och storlek som en boolesk datatyp skild från heltal. Alla större implementeringar ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL , etc.) packar bitarna tätt i vilken storlek maskinordet än har. Bitar kan nås individuellt via den vanliga indexeringsnotationen (A[3]) såväl som genom alla vanliga primitiva funktioner och operatorer där de ofta hanteras med hjälp av en specialfallsalgoritm som att summera bitarna via en tabelluppslagning av bytes .

C- programmeringsspråkets bitfält , pseudoobjekt som finns i strukturer med storlek lika med ett visst antal bitar, är i själva verket små bitarrayer ; de är begränsade genom att de inte kan sträcka sig över ord. Även om de ger en bekväm syntax, nås bitarna fortfarande med hjälp av bytevisa operatorer på de flesta maskiner, och de kan bara definieras statiskt (liksom C:s statiska arrayer, deras storlekar är fixerade vid kompilering). Det är också ett vanligt idiom för C-programmerare att använda ord som små bitarrayer och komma åt bitar av dem med hjälp av bitoperatorer. En allmänt tillgänglig header-fil som ingår i X11 -systemet, xtrapbits.h, är "ett portabelt sätt för system att definiera bitfältsmanipulation av matriser av bitar." En mer förklarande beskrivning av ovannämnda tillvägagångssätt finns i comp.lang.c faq .

I C++ , även om individuella booler vanligtvis upptar samma utrymme som en byte eller ett heltal, är vektorn <bool> av STL - typ en partiell mallspecialisering där bitar packas som en optimering av utrymmeseffektivitet. Eftersom bytes (och inte bitar) är den minsta adresserbara enheten i C++ , returnerar operatorn [] inte en referens till ett element utan istället en proxyreferens . Detta kan tyckas vara en liten punkt, men det betyder att vektor<bool> inte är en standard STL-behållare, varför användningen av vektor<bool> generellt avråds. En annan unik STL-klass, bitset , skapar en vektor av bitar som är fixerade vid en viss storlek vid kompilering och liknar i sitt gränssnitt och syntax mer den idiomatiska användningen av ord som bituppsättningar av C-programmerare. Den har också en viss extra kraft, såsom möjligheten att effektivt räkna antalet bitar som är inställda. Boost C++-biblioteken tillhandahåller en dynamic_bitset -klass vars storlek anges vid körning.

Programmeringsspråket D tillhandahåller bitarrayer i sitt standardbibliotek, Phobos, i std.bitmanip . Som i C++, returnerar operatorn [] inte en referens, eftersom enskilda bitar inte är direkt adresserbara på de flesta hårdvara, utan istället returnerar en bool .

I Java skapar klassen BitSet en bitarray som sedan manipuleras med funktioner uppkallade efter bitvisa operatorer som är bekanta för C-programmerare. Till skillnad från bituppsättningen i C++ har Java BitSet inte ett "storlek"-tillstånd (det har en i praktiken oändlig storlek, initialiserad med 0 bitar); en bit kan ställas in eller testas på vilket index som helst. Dessutom finns det en klass EnumSet , som representerar en uppsättning värden av en uppräknad typ internt som en bitvektor, som ett säkrare alternativ till bitfält.

.NET Framework tillhandahåller en BitArray- samlingsklass. Den lagrar bitar med hjälp av en array av typen int (varje element i arrayen representerar vanligtvis 32 bitar). Klassen stöder random access och bitvisa operatorer, kan itereras över, och dess Length -egenskap kan ändras för att växa eller trunkeras.

Även om Standard ML inte har något stöd för bitmatriser, har Standard ML i New Jersey en förlängning, BitArray -strukturen, i sitt SML/NJ-bibliotek. Den är inte fast i storlek och stöder setoperationer och bitoperationer, inklusive, ovanligt, skiftoperationer.

Haskell saknar för närvarande standardstöd för bitvisa operationer, men både GHC och Hugs tillhandahåller en Data.Bits- modul med diverse bitvisa funktioner och operatorer, inklusive skift- och rotationsoperationer och en "unboxed" array över booleska värden kan användas för att modellera en Bit-array , även om detta saknar stöd från den tidigare modulen.

I Perl kan strängar användas som expanderbara bitarrayer. De kan manipuleras med de vanliga bitvisa operatorerna ( ~ | & ^ ), och individuella bitar kan testas och ställas in med vec -funktionen.

I Ruby kan du komma åt (men inte ställa in) en bit av ett heltal ( Fixnum eller Bignum ) med hakparentesoperatorn ( [] ), som om det vore en array av bitar.

Apples Core Foundation- bibliotek innehåller CFBitVector- och CFMutableBitVector -strukturer.

PL/I stöder arrayer av bitsträngar av godtycklig längd, som antingen kan ha fast längd eller varierande. Arrayelementen kan vara justerade - varje element börjar på en byte eller ordgräns - eller ojusterade - element följer omedelbart efter varandra utan utfyllnad.

PL/pgSQL och PostgreSQL:s SQL stödjer bitsträngar som inbyggd typ. Det finns två SQL-bittyper: bit( n ) och bitvarierande( n ) , där n är ett positivt heltal.

Hårdvarubeskrivningsspråk som VHDL , Verilog och SystemVerilog stöder naturligt bitvektorer eftersom dessa används för att modellera lagringselement som flip-flops , hårdvarubussar och hårdvarusignaler i allmänhet. I hårdvaruverifieringsspråk som OpenVera , e och SystemVerilog används bitvektorer för att sampla värden från hårdvarumodellerna och för att representera data som överförs till hårdvara under simuleringar.

Common Lisp tillhandahåller en endimensionell bitvektorimplementering som ett specialfall av den inbyggda arrayen , som fungerar i en dubbel kapacitet som en klass- och en typspecifikator. Eftersom den är en derivata av arrayen, förlitar den sig på att den allmänna make-array- funktionen konfigureras med en elementtyp av bit , som valfritt tillåter att bitvektorn betecknas som dynamiskt storleksändringsbar. Bitvektorn är emellertid inte oändlig i omfattning . En mer begränsad enkel-bit-vektortyp existerar, som uttryckligen utesluter de dynamiska egenskaperna. Bitvektorer representeras som och kan konstrueras på ett mer kortfattat sätt av läsarmakrot # * bitar . Förutom de allmänna funktionerna som är tillämpliga på alla arrayer finns dedikerade operationer för bitvektorer. Enstaka bitar kan nås och modifieras med hjälp av bit- och sbit -funktionerna och ett omfattande antal logiska operationer stöds.

Se även

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Bit_array&oldid=1138069551 "