Pytanie Wyodrębnij sekwencje bitów o dowolnej długości z tablicy bajtów [] wydajnie


Szukam najbardziej efektywnego sposobu wyodrębniania (unsigned) sekwencji bitów o dowolnej długości (0 <= length <= 16) w dowolnej pozycji. Klasa szkieletu pokazuje, jak moja obecna implementacja w zasadzie radzi sobie z problemem:

public abstract class BitArray {

byte[] bytes = new byte[2048];
int bitGet;

public BitArray() {
}

public void readNextBlock(int initialBitGet, int count) {
    // substitute for reading from an input stream 
    for (int i=(initialBitGet>>3); i<=count; ++i) {
        bytes[i] = (byte) i;
    }
    prepareBitGet(initialBitGet, count);
}

public abstract void prepareBitGet(int initialBitGet, int count);

public abstract int getBits(int count);

static class Version0 extends BitArray {
    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
    }

    public int getBits(int len) {
        // intentionally gives meaningless result
        bitGet += len;
        return 0;
    }
}

static class Version1 extends BitArray {
    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet - 1;
    }

    public int getBits(int len) {
        int byteIndex = bitGet;
        bitGet = byteIndex + len;
        int shift = 23 - (byteIndex & 7) - len;
        int mask = (1 << len) - 1;
        byteIndex >>= 3;
        return (((bytes[byteIndex] << 16) | 
               ((bytes[++byteIndex] & 0xFF) <<  8) |
                (bytes[++byteIndex] & 0xFF)) >> shift) & mask;
    }
}

static class Version2 extends BitArray {
    static final int[] mask = { 0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF,
                0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
    }

    public int getBits(int len) {
        int offset = bitGet;
        bitGet = offset + len;
        int byteIndex = offset >> 3; // originally used /8
        int bitIndex = offset & 7;   // originally used %8
        if ((bitIndex + len) > 16) {
            return ((bytes[byteIndex] << 16 |
                    (bytes[byteIndex + 1] & 0xFF) << 8 |
                    (bytes[byteIndex + 2] & 0xFF)) >> (24 - bitIndex - len)) & mask[len];
        } else if ((offset + len) > 8) {
            return ((bytes[byteIndex] << 8 |
                    (bytes[byteIndex + 1] & 0xFF)) >> (16 - bitIndex - len)) & mask[len];
        } else {
            return (bytes[byteIndex] >> (8 - offset - len)) & mask[len];
        }
    }
}

static class Version3 extends BitArray {
    int[] ints = new int[2048];

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
        int put_i = (initialBitGet >> 3) - 1;
        int get_i = put_i;
        int buf;
        buf = ((bytes[++get_i] & 0xFF) << 16) |
              ((bytes[++get_i] & 0xFF) <<  8) |
               (bytes[++get_i] & 0xFF);
        do {
            buf = (buf << 8) | (bytes[++get_i] & 0xFF);
            ints[++put_i] = buf;
        } while (get_i < count);
    }

    public int getBits(int len) {
        int bit_idx = bitGet;
        bitGet = bit_idx + len;
        int shift = 32 - (bit_idx & 7) - len;
        int mask = (1 << len) - 1;
        int int_idx = bit_idx >> 3;
        return (ints[int_idx] >> shift) & mask;
    }
}

static class Version4 extends BitArray {
    int[] ints = new int[1024];

    public void prepareBitGet(int initialBitGet, int count) {
        bitGet = initialBitGet;
        int g = initialBitGet >> 3;
        int p = (initialBitGet >> 4) - 1;
        final byte[] b = bytes;
        int t = (b[g]  <<  8) | (b[++g] & 0xFF);
        final int[] i = ints;
        do {
            i[++p] = (t = (t << 16) | ((b[++g] & 0xFF) <<8) | (b[++g] & 0xFF));
        } while (g < count);
    }

    public int getBits(final int len) {
        final int i;
        bitGet = (i = bitGet) + len;
        return (ints[i >> 4] >> (32 - len - (i & 15))) & ((1 << len) - 1);
    }
}

public void benchmark(String label) {
    int checksum = 0;
    readNextBlock(32, 1927);
    long time = System.nanoTime();
    for (int pass=1<<18; pass>0; --pass) {
        prepareBitGet(32, 1927);
        for (int i=2047; i>=0; --i) {
            checksum += getBits(i & 15);
        }
    }
    time = System.nanoTime() - time;
    System.out.println(label+" took "+Math.round(time/1E6D)+" ms, checksum="+checksum);
    try { // avoid having the console interfere with our next measurement
        Thread.sleep(369);
    } catch (InterruptedException e) {}
}

public static void main(String[] argv) {
    BitArray test;
    // for the sake of getting a little less influence from the OS for stable measurement
    Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
    while (true) {
        test = new Version0();
        test.benchmark("no implementaion");
        test = new Version1();
        test.benchmark("Durandal's (original)");
        test = new Version2();
        test.benchmark("blitzpasta's (adapted)");
        test = new Version3();
        test.benchmark("MSN's (posted)");
        test = new Version4();
        test.benchmark("MSN's (half-buffer modification)");
        System.out.println("--- next pass ---");
    }
}
}

To działa, ale szukam bardziej wydajne rozwiązanie (pod względem wydajności). Gwarantuje się, że tablica bajtów będzie stosunkowo niewielka, od kilku bajtów do maksymalnie 1800 bajtów. Tablica jest odczytywana dokładnie raz (całkowicie) między każdym wywołaniem metody odczytu. Nie ma potrzeby sprawdzania błędów w getBits (), takich jak przekroczenie tablicy itp.


Wygląda na to, że moje pierwsze pytanie powyżej nie jest wystarczająco jasne. "Bitowa sekwencja" bitów N tworzy liczbę całkowitą N bitów i muszę wyodrębnić te liczby całkowite z minimalnym narzutem. Nie używam ciągów, ponieważ wartości są albo używane jako indeksy odnośników, albo bezpośrednio do niektórych obliczeń. Zasadniczo szkielet pokazany powyżej jest klasą prawdziwą, a sygnatura getBits () pokazuje, jak reszta kodu wchodzi w interakcje z nią.


Rozszerz kod przykładowy do mikrodźwięku, w tym rozwiązanie Blitzpasta (poprawiono brakujące maskowanie bajtów). Na moim starym pudełku AMD okazuje się ~ 11400ms vs. ~ 38000ms. FYI: to dzielenie i operacje modulo, które zabijają wydajność. Jeśli zastąpisz / 8 z >> 3 i % 8 z & 7oba rozwiązania są dość blisko siebie (jdk1.7.0ea104).


Wydawało się, że jest trochę zamieszania w kwestii tego, jak i nad czym pracować. Pierwszy, oryginalny wpis przykładowego kodu zawierał metodę read (), aby wskazać miejsce i czas wypełnienia bufora bajtowego. Zostało to utracone, gdy kod został przekształcony w mikrobancz. Ponownie wprowadziłem go, aby uczynić to nieco jaśniejszym. Pomysł polega na pokonaniu wszystkich istniejących wersji poprzez dodanie innej podklasy BitArray, która wymaga implementacji funkcji getBits () i prepareBitGet (), która może być pusta. Nie zmieniaj benchmarkingu, aby dać Twojemu rozwiązaniu przewagę, to samo można zrobić dla wszystkich istniejących rozwiązań, czyniąc to całkowicie optymalną! (naprawdę!!)

Dodałem wersję0, która nic nie robi, ale zwiększa stan bitGet. Zawsze zwraca 0, aby zorientować się, jak duży jest narzut związany z benchmarkiem. Jest tam tylko dla porównania.

Dodano także adaptację do pomysłu MSN (wersja 3). Aby zachować uczciwość i porównywalność dla wszystkich konkurentów, wypełnianie tablic bajtowych jest teraz częścią testu porównawczego, a także etapem przygotowawczym (patrz wyżej). Pierwotnie rozwiązanie MSN nie działało tak dobrze, było dużo kosztów związanych z przygotowaniem bufora int []. Wolałem nieco zoptymalizować krok, co zmieniło go w zaciekłego konkurenta :) Możesz również zauważyć, że trochę rozwikłałem twój kod. Twoje getBit () może być skondensowane do 3-liniowej, prawdopodobnie goląc jeden lub dwa procent. Celowo zrobiłem to, aby kod był czytelny, a także dlatego, że inne wersje nie są tak skondensowane, jak to tylko możliwe (ponownie dla czytelności).


Wniosek (Podaj przykład kodu powyżej aktualizacji, aby uwzględnić wersje oparte na wszystkich odpowiednich składkach). Na moim starym pudełku AMD (Sun JRE 1.6.0_21), wychodzą one jako:

V0 nie wykonano żadnej implementacji 5384 ms
V1 Durandal (oryginalny) wziął 10283 ms
V2 Blitzpasta zaadaptował się 12212 ms
V3 MSN (wysłany) wziął 11030 ms
Dokonano V4 MSN (modyfikacja pół-bufora) 9700 ms

Uwagi: W tym benchmarku pobiera się średnio 7,5 bitów na każde połączenie do getBits (), a każdy bit jest czytany tylko raz. Ponieważ V3 / V4 muszą ponosić wysokie koszty inicjalizacji, mają tendencję do wykazywania lepszych zachowań w czasie wykonywania z większą ilością krótszych pobrań (a co za tym idzie, im mniej, im mniej niż 16, osiąga średni rozmiar pobierania). Mimo to, V4 pozostaje nieznacznie wyprzedza wszystkie inne wszystko scenariusze. W rzeczywistej aplikacji należy wziąć pod uwagę rywalizację o pamięć podręczną, ponieważ dodatkowa przestrzeń potrzebna dla V3 / v4 może zwiększyć liczbę braków w pamięci podręcznej do punktu, w którym V0 byłby lepszym wyborem. Jeśli tablica ma być przeszukiwana więcej niż jeden raz, V4 powinno być faworyzowane, ponieważ pobiera się szybciej niż każda inna, a kosztowna inicjalizacja jest amortyzowana po przejściu pierwszej pięści.


12
2017-10-02 17:08


pochodzenie


Fajnie, nie wiedziałem, że / 8 i% 8 jest znacznie wolniejsze niż >> 3 i & 7. Teraz ja robię. - blizpasta
Zaskoczyło to również mnie, więc zbadałem sprawę. W przypadku modulo JIT nie może wiedzieć, że mamy tylko wartości dodatnie, a wyniki% 8 i 7 różnią się wartościami ujemnymi. Dla dzielenia liczby całkowitej, jest to podobne. Przesunięcie jest wyłączone o jedną dla prawie wszystkich wartości (z wyjątkiem tych, które mają 0 w ostatnich czterech bitach). Tak więc, podczas gdy można intuicyjnie założyć, że JIT zoptymalizuje to, nie może, ponieważ mogłoby to potencjalnie zmienić wyniki. - Durandal
"najbardziej efektywny sposób" w kosmosie? lub w czasie obliczeń? Jeśli masz przestrzeń, możesz wykupić przestrzeń przez procesor, obliczając odpowiedzi z wyprzedzeniem w tablicach, a następnie pobieraj tylko wartości tablicowe. - mschonaker
Najbardziej wydajne = liczba zużytych cykli procesora i pozwala wybierać losowo: nie więcej niż 500% przykładowego zużycia pamięci. Jeśli pomogły Ci bufory pośrednie, wyrzuć się - ale pamiętaj o ograniczeniach z pierwotnego pytania (odczytanie sekwencyjne raz). - Durandal
Tylko węzeł boczny: zanim porównasz szybkość różnych implementacji, upewnij się, że dają wynik, który naprawdę chcesz. Po zainicjowaniu programu Version1 i poprosił o 8 bitów, odpowiedział 1. Ponieważ tablica bajtów zaczyna się od a 0, Bym się tego spodziewał. - Roland Illig


Odpowiedzi:


Cóż, w zależności od tego, jak daleko zajdzie Ci czas w porównaniu do pamięci, możesz przydzielić tabelę boczną na każde 32-bitowe miejsce w każdym 16-bitowym przesunięciu, a następnie zrobić maskę i przesunąć w oparciu o 16-bitowe offsetowy:

byte[] bytes = new byte[2048];   
int bitGet;   
unsigned int dwords[] = new unsigned int[2046];

public BitArray() {   
    for (int i=0; i<bytes.length; ++i) {   
        bytes[i] = (byte) i;   
    }   

    for (int i= 0; i<dwords.length; ++i) {
        dwords[i]= 
            (bytes[i    ] << 24) | 
            (bytes[i + 1] << 16) | 
            (bytes[i + 2] <<  8) | 
            (bytes[i + 3]);
    }
}   

int getBits(int len)
{
    int offset= bitGet;
    int offset_index= offset>>4;
    int offset_offset= offset & 15;

    return (dwords[offset_index] >> offset_offset) & ((1 << len) - 1);
}

Unikasz rozgałęzień (kosztem czterokrotnego wzrostu śladu pamięciowego). I patrzy w górę na maskę naprawdę znacznie szybciej niż (1 << len) - 1?


2
2017-10-07 23:55



Początkowo miałem pewne problemy z uruchomieniem tego, kilka błędów w getBits (), ale nadal ten pomysł wygląda dobrze (patrz edytowany microbench). Nie jestem pewien, w jaki sposób zamierzasz obliczyć wartość przesunięcia (offset_offset = offset & 15) - Musiałem uciekać się do bardziej skomplikowanego wyrażenia, aby go uruchomić. - Durandal
Szukanie maski ze stołu wydaje się być trochę wolniej niż (1 << len) - 1. Zastąpienie szukania w rozwiązaniu Blitzpastas przyspiesza o ~ 3%. Grałem też trochę z twoim kodem. Okazuje się, że możesz wydostać o połowę mniej dodatkowego bufora (ponieważ getBits jest ograniczony, aby uzyskać maksymalnie 16 bitów). Dla każdego nieparzystego dwójnika w buforze można zastąpić nawet dword i po prostu przesunąć o 8 bitów mniej. Wymaga tylko niewielkiej modyfikacji przygotowania bufora i różnych wartości przesunięcia / maski w getBits, więc działa z niemal dokładnie taką samą prędkością. - Durandal


Jeśli chcesz tylko niepodpisaną sekwencję bitów jako int.

static final int[] lookup = {0x0, 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

/*
 * bytes: byte array, with the bits indexed from 0 (MSB) to (bytes.length * 8 - 1) (LSB)
 * offset: index of the MSB of the bit sequence.
 * len: length of bit sequence, must from range [0,16].
 * Not checked for overflow
 */
static int getBitSeqAsInt(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int val;

    if ((bitIndex + len) > 16) {
        val = ((bytes[byteIndex] << 16 | bytes[byteIndex + 1] << 8 | bytes[byteIndex + 2]) >> (24 - bitIndex - len)) & lookup[len];
    } else if ((offset + len) > 8) {
        val = ((bytes[byteIndex] << 8 | bytes[byteIndex + 1]) >> (16 - bitIndex - len)) & lookup[len];
    } else {
        val = (bytes[byteIndex] >> (8 - offset - len)) & lookup[len];
    }

    return val;
}

Jeśli chcesz go jako ciąg (modyfikacja odpowiedzi Margusa).

static String getBitSequence(byte[] bytes, int offset, int len){

    int byteIndex = offset / 8;
    int bitIndex = offset % 8;
    int count = 0;
    StringBuilder result = new StringBuilder();        

    outer:
    for(int i = byteIndex; i < bytes.length; ++i) {
        for(int j = (1 << (7 - bitIndex)); j > 0; j >>= 1) {
            if(count == len) {
                break outer;
            }                
            if((bytes[byteIndex] & j) == 0) {
                result.append('0');
            } else {
                result.append('1');
            }
            ++count;
        }
        bitIndex = 0;
    }
    return  result.toString();
}   

3
2017-10-02 21:03



Twoje rozwiązanie wygląda bardzo podobnie do mojego, tylko otrzymujesz maskę dla części przydzielonej w int z tabeli odnośników, a ja buduję ją w locie "(1 << count) - 1". O ile mogę powiedzieć, że optymalizacja, aby sprawdzić, czy sekwencja obejmuje 1, 2 lub 3 bajty, faktycznie spowalnia kod, usuwając praktycznie równy temu kodowi. - Durandal
Włączyłem twoją wersję do mojego microbenchmark (było brakujące maskowanie bajtów, które wziąłem na wolność dodawania). Różnice w wydajności są ... zdumiewające. - Durandal


Zastanawiam się, dlaczego nie możesz tego użyć java.util.BitSet; 

Zasadniczo możesz zrobić, to odczytać wszystkie dane jako byte[], zamień go na plik binarny w string formatuj i używaj narzędzi łańcuchowych takich jak .substring() do wykonania pracy. To również zadziała bit sequences > 16.

Powiedzmy, że masz 3 bajty: 1, 2, 3 i chcesz wyodrębnić sekwencję bitów z 5 na 16 bit.

Liczba Binarna

1      00000001
2      00000010
3      00000011

Przykład kodu:

public static String getRealBinary(byte[] input){
    StringBuilder sb = new StringBuilder();

    for (byte c : input) {
        for (int n =  128; n > 0; n >>= 1){
            if ((c & n) == 0)
                sb.append('0');
            else sb.append('1');
        }
    }

    return sb.toString();
}
public static void main(String[] args) {
    byte bytes[] = new byte[]{1,2,3};
    String sbytes = getRealBinary(bytes);
    System.out.println(sbytes);
    System.out.println(sbytes.substring(5,16));
}

Wydajność:

000000010000001000000011
00100000010

Prędkość:

Zrobiłem testrun dla 1m razy i na moim komputerze zajęło to 0,995s, więc jego rozsądnie bardzo szybko:

Kod, aby samemu powtórzyć test:

public static void main(String[] args) {
    Random r = new Random();
    byte bytes[] = new byte[4];
    long start, time, total=0;

    for (int i = 0; i < 1000000; i++) {
        r.nextBytes(bytes);
        start = System.currentTimeMillis();
        getRealBinary(bytes).substring(5,16);
        time = System.currentTimeMillis() - start;
        total+=time;
    }
    System.out.println("It took " +total + "ms");
}

1
2017-10-02 17:17



BitSet nie oferuje metody uzyskiwania kolejnych bitów jako int, nadal musiałbym implementować własny getBits (), nadal zarządzając własnym indeksem bitGet i wywołując BitSet.get (indeks) dla każdego bitu - co jest sprzeczne z moim definicja skutecznego. Interesuje mnie szybkość, a nie elastyczność. - Durandal
Zaktualizowałem mój przykład. - Margus
Przepraszam, jeśli moje pytanie nie było wystarczająco jasne, staram się wyodrębnić w liczbach całkowitych, żadnych innych wymyślnych transformacji. - Durandal


Potrzebujesz maksymalnie 16 bitów, zaczerpniętych z tablicy bajtów. 16 bitów może zajmować maksymalnie 3 bajty. Oto możliwe rozwiązanie:

    int GetBits(int bit_index, int bit_length) {
          int byte_offset = bit_index >> 3;
          return ((((((byte_array[byte_offset]<<8)
                    +byte_array[byte_offset+1])<<8)
                    +byte_array[byte_offset+2]))
                   >>(24-(bit_index&7)+bit_length))))
                  &((1<<bit_length)-1);
         }

[Nie przetestowane]

Jeśli wywołasz to dużo, powinieneś wstępnie obliczyć 24-bitowe wartości dla 3 połączonych bajtów i zapisać je w tablicy int.

Zauważyłem, że jeśli kodujesz to w C na x86, nie musisz nawet wstępnie obliczać 24-bitowej tablicy; po prostu uzyskaj dostęp do tablicy te przy pożądanym przesunięciu jako wartość 32-bitowa. X86 wykona niepoprawne pobieranie. [komentujący zauważył, że to endianizm zafałszowuje to, więc to nie jest odpowiedź, OK, wykonaj wersję 24-bitową.]


0
2017-10-09 21:00



Wydaje się, że przegapiłeś tag Javy :) Jeśli się nie mylę, pobranie zwykłego dword na x86 nie byłoby wcale takie proste, ponieważ jest to mała architektura endian. W kodzie są dwa literówki (pierwsza zmiana powinna wynosić 16, a trzeci dostęp do tablicy brakuje +2 do indeksu). Dodając, że to tylko kondensacja tego, co w pytaniu w wersji 1. Aha, w bajtach Java są podpisane i cicho promowane do int, więc drugi i trzeci bajt muszą być maskowane za pomocą 0xFF. - Durandal
Pierwsza zmiana to 8 bitów, potem 2 bajty dodane, a ta para zostaje przesunięta w lewo 8. Jeśli twoja maszyna ma zmieniacz lufy, nie ma to znaczenia, ale jeśli przesuwa się na krótkich dystansach szybciej niż długo to ma znaczenie. Tak, spadł +2, edytowany, aby poprawić. Jeśli bajty są promowane jako podpisane (głupia Java), zawsze możesz po prostu skopiować je do "ints", zanim zaczniesz unikać śmieci znakujących maskę, co powinno uczynić je konkurencyjnymi. Teraz, gdy przewinąłem wersję 1 w prawo kilkaset znaków (nie było łatwo tam, gdzie był pasek przewijania) widzę, że robiłeś to samo. 7 liniowa odpowiedź zaginęła w twoim ogromnym przykładzie: - { - Ira Baxter
+1 za przypomnienie, że odległość zmiany może mieć wpływ na niektóre maszyny. Przykład był kiedyś mały, ale sposób, w jaki rzeczy się rozwinęły ... no cóż, skończyło się to w ten sposób. Niestety Java nie może wykonać każdy niepodpisane rzuty na szerszy typ, które pozostawiają nam gości z Javy, bez możliwości wyboru, oprócz maskowania :( - Durandal
Java może wymagać podpisanych rzutów, ale jeśli masz wartość 8-bitową zapisaną w int (może masz to maskowanie!), Nie musisz maskować wartości pobranej z int. Uważam jednak, że prekomputer 24-bitowy jest zdecydowanie najlepszym rozwiązaniem. - Ira Baxter


Od wersji Java 7 BitSet zawiera toLongArray Metoda, która, jak sądzę, zrobi dokładnie to, o co pyta:

int subBits = (int) bitSet.get(lowBit, highBit).toLongArray()[0];

Ma to tę zaletę, że działa z sekwencjami większymi niż ints lub longs. Ma wadę wydajności, że nowy BitSet obiekt musi zostać przydzielony, a nowy obiekt tablicy do przechowywania wyniku.

Byłoby naprawdę interesujące zobaczyć, jak to się porównuje z innymi metodami w benchmarku.


0
2018-02-01 09:22