Я ищу наиболее эффективный способ извлечения (беззнаковых) битовых последовательностей произвольной длины (0 <= длина <= 16) в произвольной позиции. Скелетный класс показывает, как моя текущая реализация по существу решает проблему: </p>
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 ---");
}
}
}
Это работает, но я ищу более эффективное решение (с точки зрения производительности) . Массив байтов гарантированно будет относительно небольшим, от нескольких байтов до макс. ~ 1800 байтов. Массив читается ровно один раз (полностью) между каждым вызовом метода read. Нет необходимости в какой-либо проверке ошибок в getBits (), например, превышении массива и т. Д.
Кажется, мой начальный вопрос выше не достаточно ясен. «Битовая последовательность» из N битов образует целое число из N битов, и мне нужно извлечь эти целые числа с минимальными издержками. Я не использую строки, так как значения либо используются в качестве индексов поиска, либо напрямую вводятся в некоторые вычисления. Таким образом, скелет, показанный выше, является реальным классом, а сигнатура getBits () показывает, как с ним взаимодействует остальная часть кода.
Расширение кода примера в микробенчмарк, включая решение блицпасты (исправлено маскирование пропущенных байтов). На моей старой коробке AMD получается ~ 11400мс против ~ 38000мс. К вашему сведению: именно операции деления и деления по модулю убивают производительность. Если вы замените / 8 на >> 3 и % 8 на & 7 , оба решения будут довольно близки друг к другу (jdk1. 7.0ea104).
Казалось, было немного путаницы в том, как и над чем работать. Первая, оригинальная запись примера кода включала метод read (), чтобы указать, где и когда был заполнен байтовый буфер. Это было потеряно, когда код был превращен в микробук. Я повторно ввел это, чтобы сделать это немного яснее.
Идея состоит в том, чтобы превзойти все существующие версии, добавив еще один подкласс BitArray, который должен реализовывать getBits () и prepareBitGet (), последний может быть пустым. Не изменяйте эталонный тест, чтобы дать вашему решению преимущество, то же самое можно было бы сделать для всех существующих решений, что делает его полностью спорным для оптимизации! (На самом деле !!)
Я добавил Version0, которая ничего не делает, кроме как увеличивает состояние bitGet. Он всегда возвращает 0, чтобы получить приблизительное представление о том, насколько велики накладные расходы. Это только для сравнения.
Также была добавлена адаптация идеи MSN (Версия 3). Чтобы сохранить справедливость и сопоставимость для всех конкурентов, заполнение байтового массива теперь является частью теста, а также подготовительным этапом (см. Выше). Первоначально решение MSN не очень хорошо работало, было много накладных расходов при подготовке буфера int []. Я позволил себе немного оптимизировать шаг, что превратило его в сильного конкурента :)
Вы также можете обнаружить, что я немного деформировал ваш код. Ваш getBit () может быть сжат в 3 строки, вероятно, сбрасывая один или два процента. Я намеренно сделал это, чтобы сохранить читабельность кода, а также потому, что другие версии также не настолько сжаты, насколько это возможно (опять же для удобства чтения).
Заключение (пример кода выше обновлен, чтобы включать версии, основанные на всех применимых вкладах). На моей старой коробке AMD (Sun JRE 1.6.0_21) они выглядят так:
V0 реализация не заняла 5384 мс
V1 Durandal's (оригинал) занял 10283 мс
V2 блицпаста (адаптированный) занял 12212 мс
V3 MSN (опубликовано) заняло 11030 мс
VN MSN (модификация с половинным буфером) заняла 9700 мс
Примечания. В этом тесте для каждого вызова getBits () выбирается в среднем 7,5 битов, и каждый бит читается только один раз. Поскольку V3 / V4 должны платить высокую стоимость инициализации, они, как правило, демонстрируют лучшее поведение во время выполнения с более короткими выборками (и, следовательно, чем хуже, тем ближе к максимальному значению, равному 16, средний размер выборки). Тем не менее, V4 остается немного впереди всех остальных в всех сценариях.В реальном приложении необходимо учитывать конфликт в кеше, так как дополнительное пространство, необходимое для V3 / v4, может увеличить пропуски кеша до точки, где V0 будет лучшим выбором. Если массив должен быть пройден более одного раза, V4 следует отдать предпочтение, так как он выбирается быстрее, чем любой другой, и дорогая инициализация амортизируется после первого прохода.