Подтвердить что ты не робот

Извлечение битовых последовательностей произвольной длины из массива byte [] эффективно

Я ищу наиболее эффективный способ извлечения (беззнаковых) битовых последовательностей произвольной длины (0 <= length <= 16) в произвольной позиции. Класс скелета показывает, как моя текущая реализация по существу справляется с проблемой:

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 (original)");
        test = new Version2();
        test.benchmark("blitzpasta (adapted)");
        test = new Version3();
        test.benchmark("MSN (posted)");
        test = new Version4();
        test.benchmark("MSN (half-buffer modification)");
        System.out.println("--- next pass ---");
    }
}
}

Это работает, но я ищу более эффективное решение . Массив байтов гарантированно будет относительно небольшим, от нескольких байтов до макс. ~ 1800 байт. Массив читается ровно один раз (полностью) между каждым вызовом на метод чтения. Нет необходимости в проверке ошибок в getBits(), например, превышении массива и т.д.

Кажется, мой первоначальный вопрос выше не достаточно ясен. "Битовая последовательность" из N бит образует целое число из N бит, и мне нужно извлечь эти целые числа с минимальными накладными расходами. Я не могу использовать строки, поскольку значения либо используются в качестве индексов поиска, либо непосредственно передаются в некоторые вычисления. Таким образом, скелет, показанный выше, является реальным классом, а getBits() показывает, как взаимодействует с ним остальная часть кода.

Расширьте примерный код в микрообъекте, включив в него решение blitzpasta (фиксированное маскирование отсутствующих байтов). На моей старой коробке AMD получается ~ 11400 мс против ~ 38000 мс. FYI: это деление и модульные операции, которые убивают производительность. Если вы замените /8 на → 3 и % 8 с помощью & 7, оба решения довольно близки (jdk1.7.0ea104).

Казалось, было немного путаницы в том, как и над чем работать. Первая, оригинальная запись примерного кода включала метод read(), указывающий, где и когда был заполнен буфер байта. Это потерялось, когда код был превращен в микрофон. Я снова представил его, чтобы сделать это немного яснее. Идея состоит в том, чтобы превзойти все существующие версии, добавив еще один подкласс BitArray, который должен реализовать getBits() и prepareBitGet(), последний может быть пустым. <Б > Не изменяйте бенчмаркинг, чтобы дать ваше решение преимущество, то же самое можно было бы сделать для всех существующих решений, делая это совершенно спорный вопрос оптимизации! (На самом деле!!)

Я добавил версию0, которая ничего не делает, кроме как увеличивать состояние битGet. Он всегда возвращает 0, чтобы получить приблизительное представление о том, насколько велики накладные расходы. Его только там для сравнения.

Также была добавлена ​​адаптация к идее MSN (версия 3). Чтобы все было справедливо и сопоставимо для всех конкурентов, заполнение массива байтов теперь является частью эталона, а также подготовительным этапом (см. Выше). Первоначально решение MSN не так хорошо, было много накладных расходов при подготовке буфера int []. Я позволил немного оптимизировать шаг, который превратил его в ожесточенного конкурента:) Вы также можете обнаружить, что я немного исказил ваш код. Ваш getBit() может быть сконденсирован в 3-лайнер, возможно, сбрасывая один или два процента. Я намеренно сделал это, чтобы прочитать код, и потому, что другие версии не настолько сжаты, насколько это возможно (снова для удобства чтения).

Заключение (пример кода выше, чтобы включить версии на основе всех применимых вкладов). На моей старой коробке AMD (Sun JRE 1.6.0_21) они выглядят как:

V0 не выполнено 5384 ms
V1 Durandal (оригинал) взял 10283 ms
V2 blitzpasta (адаптированный) взял 12212 ms
V3 MSN (отправлено) взял 11030 ms
V4 MSN (модификация с половинным буфером) заняла 9700 ms

Примечания. В этом тесте среднее значение 7,5 бит выбирается за вызов getBits(), и каждый бит считывается только один раз. Поскольку V3/V4 должны заплатить высокую стоимость инициализации, они, как правило, показывают лучшее поведение во время работы с более короткими выборками (и, следовательно, хуже, чем ближе максимум к 16, получается средний размер выборки). Тем не менее, V4 остается немного впереди всех остальных во всех сценариях. В реальном приложении должны учитываться конфликты кеша, поскольку дополнительное пространство, необходимое для V3/v4, может увеличить промахи в кэше до точки, где V0 будет лучшим выбором. Если массив должен быть пройден более одного раза, V4 следует отдать предпочтение, поскольку он извлекается быстрее, чем каждый другой, и дорогостоящая инициализация амортизируется после прохождения кулака.

4b9b3361

ОТВЕТЫ

Ответ 1

Хорошо, в зависимости от того, как далеко вы хотите перейти вниз по времени по сравнению с памятью, вы можете выделить боковую таблицу каждые 32 бита при каждом 16-битном смещении, а затем сделать маску и сдвиг на основе 16-битное смещение:

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);
}

Вы избегаете ветвления (за счет увеличения объема памяти в четыре раза). И ищет маску действительно намного быстрее, чем (1 < len) - 1?

Ответ 2

Если вам просто нужна последовательность без знака в виде 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;
}

Если вы хотите, чтобы это было как строка (изменение ответа Маргуса).

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

Просто интересно, почему вы не можете использовать java.util.BitSet;

В основном вы можете прочитать все данные как byte[], преобразовать их в двоичный формат string и использовать служебные программы, такие как .substring(), для выполнения этой работы. Это также будет работать bit sequences > 16.

Предположим, что у вас есть 3 байта: 1, 2, 3, и вы хотите извлечь последовательность бит с 5-го по 16-й бит.

Число двоичных

1      00000001
2      00000010
3      00000011

Пример кода:

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));
}

Вывод:

000000010000001000000011
00100000010

Скорость:

Я сделал testrun для 1 м раз, а на моем компьютере потребовалось 0.995s, поэтому его разумно очень быстро:

Код для повторного тестирования:

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");
}

Ответ 4

Вы хотите не более 16 бит, взятых из массива байтов. 16 бит могут занимать не более 3 байтов. Здесь возможно решение:

    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);
         }

[Непроверенные]

Если вы вызываете это много, вы должны предварительно скопировать 24-битные значения для 3-х конкатенированных байтов и сохранить их в массиве int.

Я буду наблюдать, что если вы кодируете это в C на x86, вам даже не нужно предварительно компилировать 24-битный массив; просто получить доступ к массиву by te по смещению желания как 32-битное значение. X86 будет делать нестандартные выборки просто отлично. [commenter отметил, что endianess mucks this up, так что это не ответ, ОК, выполните 24-битную версию.]

Ответ 5

Так как Java 7 BitSet имеет метод toLongArray, который, я считаю, будет делать именно то, что задает вопрос:

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

Это имеет то преимущество, что оно работает с последовательностями, большими, чем ints или longs. Недостаток производительности заключается в том, что должен быть выделен новый объект BitSet и новый объект массива для хранения результата.

Было бы действительно интересно посмотреть, как это сравнивается с другими методами в тесте.