Какой самый быстрый способ (ы) перебирать большой фрагмент данных в разбивке по битам
https://stackoverflow.com/questions/418266
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я просматриваю блок памяти с двоичными данными по байтам.
В настоящее время я делаю что-то вроде этого:
for (i = 0; i < data->Count; i++)
{
byte = &data->Data[i];
((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}
Где находится Masks:
for (i = 0; i < 8; i++)
{
Masks[i] = 1 << i;
}
(Мне почему-то не удалось сделать это так быстро в цикле или во встроенной функции, поэтому я записал это.)
Есть ли у кого-нибудь какие-либо предложения о том, как улучшить этот первый цикл?Я довольно неопытен в том, чтобы разбираться по частям.
Это может показаться глупым поступком.Но я нахожусь в процессе реализации алгоритма сжатия.Я просто хочу, чтобы часть доступа к биту была расположена справа.
Спасибо!
PS:Это находится в компиляторе Visual Studio 2008.Так что было бы неплохо, если бы предложения применялись к этому компилятору.
ППС:Я только что понял, что мне не нужно увеличивать два счета.Одного было бы достаточно.Затем вычислите разницу с общим количеством битов в конце.Но это было бы специфично только для подсчета голосов.Что я действительно хочу сделать быстро, так это извлечение бита.
Редактировать:Идея таблицы подстановки, которая была выдвинута, хороша.Однако я понимаю, что неправильно поставил вопрос в названии.Потому что, в конце концов, то, что я хочу сделать, это не считать биты, а получить доступ к каждому биту как можно быстрее.
ЕЩЕ ОДНА ПРАВКА:Возможно ли продвинуть указатель всего на один бит в данных?
ЕЩЕ ОДНА ПРАВКА:Спасибо вам за все ваши ответы на данный момент.
То, что я хочу реализовать на следующих шагах, - это несложный двоичный арифметический кодер, который не анализирует контекст.Так что пока меня интересуют только отдельные биты.В конце концов это станет контекстно-адаптивным BAC, но я оставлю это на потом.
Одним из вариантов может быть обработка 4 байт вместо 1 байта.Но цикл более 32 бит также является дорогостоящим, не так ли?
Решение
Я действительно не понял, что вы пытаетесь сделать.Но если вы просто хотите получить доступ к фрагментам растрового изображения, вы можете использовать эти (непроверенные!!!) функции:
#include <stddef.h>
_Bool isbitset(unsigned char * bitmap, size_t idx)
{
return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}
void setbit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] |= (1 << (idx % 8));
}
void unsetbit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] &= ~(1 << (idx % 8));
}
void togglebit(unsigned char * bitmap, size_t idx)
{
bitmap[idx / 8] ^= (1 << (idx % 8));
}
Редактировать: Хорошо, я подумай Я понимаю, что ты хочешь сделать:Быстрая итерация по последовательности битов.Поэтому мы не хотим использовать функции произвольного доступа, описанные выше, а читаем сразу целое слово данных.
Вы можете использовать любой целочисленный тип без знака, который вам нравится, но вы должны выбрать тот, который, вероятно, будет соответствовать размеру слова вашей архитектуры.Я пойду с uint_fast32_t От stdint.h:
uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
uint_fast32_t mask = 1;
uint_fast32_t current = *data;
for(; mask; mask <<= 1)
{
if(current & mask)
{
// bit is set
}
else
{
// bit is not set
}
}
}
Из внутреннего цикла вы можете установить бит с помощью
*data |= mask;
сбросьте бит с помощью
*data &= ~mask;
и переключите бит с помощью
*data ^= mask;
Предупреждение: Код может вести себя неожиданно на архитектурах с большим расширением!
Другие советы
Вероятно, самый быстрый способ - это построить таблицу подстановки байтовых значений в зависимости от количества битов, установленных в этом байте.По крайней мере, таков был ответ, когда я брал интервью в Google.
Смотрите следующую ссылку для получения десятка материалов, связанных с bit: Немного Подкручивающие Хаки
Используйте таблицу, которая сопоставляет значение каждого байта (256) с числом единиц в нем.(Число 0 - это всего лишь (8 - число 1 -х)).Затем выполните итерацию по байтам и выполните один поиск для каждого байта вместо нескольких поисков и сравнений.Например:
int onesCount = 0;
for (i = 0; i < data->Count; i++)
{
byte = &data->Data[i];
onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;
Вы могли бы использовать предварительно вычисленную таблицу подстановки, т.е.:
static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */
...
for( ... )
byte = ...
Stats.FreqOf1 += bitcount_lookup[byte];
Вот метод, как подсчитать 1 бит 32-битного целого числа (основанный на Java Integer.bitCount(i) способ):
unsigned bitCount(unsigned i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
Таким образом, вы можете преобразовать свои данные в int и продвигаться вперед с шагом в 4 байта.
Вот простой вариант, который я придумал всего для одного 32-битного значения, но вы можете видеть, что адаптировать его к любому количеству битов не составит труда....
int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
if((x & 0x1) == 0x1) ones++;
x = (x >> 1);
}
printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);
Обратите внимание, однако, что это изменяет значение в процессе.Если вы делаете это с данными, которые вам нужно сохранить, то сначала вам нужно сделать их копию.
Выполнение этого в __asm, вероятно, было бы лучшим, возможно, более быстрым способом, но трудно сказать, насколько хорошо компилятор может оптимизировать...
С каждым решением, которое вы рассматриваете, у каждого из них будут недостатки.Таблица подстановки или битовый сдвиг (как у меня), у обоих есть недостатки.
Ларри
ttobiass - Имейте в виду, что ваши встроенные функции важны в приложениях, о которых вы говорите, но есть вещи, которые вам нужно иметь в виду.Ты МОЖЕТ получите максимальную производительность от встроенного кода, просто запомните пару вещей.
- встроенный в режиме отладки не существует.(Если вы не заставите это сделать силой)
- компилятор будет встроять функции так, как он считает нужным.Часто, если вы прикажете ему встроить функцию, он может вообще этого не делать.Даже если вы используете __forceinline.Проверьте MSDN для получения дополнительной информации о встраивании.
- Только определенные функции могут быть даже встроены.Например, вы не можете встроить рекурсивную функцию.
Вы получите максимальную производительность благодаря настройкам вашего проекта для языка C / C ++ и тому, как вы создаете свой код.На этом этапе важно понимать, что куча противОперации со стеком, соглашения о вызовах, выравнивание памяти и т.д.
Я знаю, что это не совсем ответ на ваш вопрос, но вы упомянули производительность и как добиться наилучшей производительности, и эти вещи являются ключевыми.
Чтобы присоединиться к link wagon:подсчет битов
Если это не случай преждевременной оптимизации и вам действительно нужно выжимать каждую последнюю фемтосекунду, то вам, вероятно, лучше использовать статический массив из 256 элементов, который вы заполняете один раз количеством битов каждого байтового значения, тогда
Статистика.FreqOf1 += количество битов[байт]
и когда цикл будет завершен:
Статистика.FreqOf0 = ((данные-> Количество * 8) - Статистика.FreqOf1)
В книге есть целая глава, посвященная различным техникам для этого Красивый Код.Вы можете прочитать (большую часть) его в Google books начиная с этого.
Более быстрый способ извлечения битов - это использовать:
bitmask= data->Data[i];
while (bitmask)
{
bit_set_as_power_of_two= bitmask & -bitmask;
bitmask&= bitmask - 1;
}
Если вы просто хотите посчитать установленные биты, вычисление LUT в кэше per было бы быстрым, но вы также можете делать это за постоянное время с помощью метода подсчета чередующихся битов в ссылка в этом ответе.
