Коллегам есть что сказать: Как эффективно считать количество 1 в Bitmap

Redis

Сегодня мои веселые и милые коллеги радостно обсуждают в группе вопрос: Как эффективно считать количество единиц в Bitmap? Итак, вопрос в том, что такое Bitmap?

Bitmap

A Bitmap or bitset is an array of zeros and ones. A bit in a bitset can be set to either 0 or 1, and each position in the array is referred to as an offset. Operations such as logical AND, OR, XOR, etc. and other bitwise operations are fair game for Bitmaps.

Выше взято из статьиREDIS BITMAPS — БЫСТРЫЕ, ПРОСТЫЕ ПОКАЗАТЕЛИ В РЕАЛЬНОМ ВРЕМЕНИ, обнаружил, что это еще хорошее понимание оригинала (какого хрена я перевел), по сути, это бинарный массив, элементы массива могут быть только 0 или 1, можно выполнять логические И, ИЛИ, XOR и другие биты в растровой операции.

Итак, по сути, мы можем упростить задачу:

Как эффективно подсчитать количество единиц в двоичном числе

Это проще понять, я сразу устрою. Как говорится, «Если у вас нет хороших идей, ломайте их напрямую», поэтому есть первое решение:

public static int count(int n) {
    int count = 0;
    while (n > 0) {
        if ((n&1) == 1) { // 计算最低位是不是为1
            count++;
        }
        n >>>= 1; // 无符号右移1位，把最低位挤出去
    }
    return count;
}

Это простое и грубое решение с временной сложностью O(N), где N — длина двоичного числа, такого как двоичное число.100100, N равно 6. Таким образом, проблема возникает снова, если длина двоичного числа очень велика, например, 10000, но число 1 равно только 10, используя первое решение, нам нужно выполнить цикл 10000 раз, но на самом деле выполнить операцию count++ Есть только 10 раз, а остальные 9990 раз кажутся немного расточительным Можем ли мы сделать столько циклов, сколько есть 1? Так появилось второе решение:

public static int count1(int n) {
    int count = 0;
    // 每次将二进制数的最低位 1 变为 0，直到该二进制数变到 0 为止
    while (n > 0) {
        count++;
        n &= n-1;
    }
    return count;
}

На самом деле, n&(n-1) можно использовать для удаления младшей 1 (до 0), конкретное объяснение можно увидеть на картинке ниже, я не знаю источник картинки, она сохранена в группе , изображение захвачено и удалено...По сравнению с первым решением, эффективность этого решения была повышена, так как каждый момент времени равен n&(n-1), достаточно выполнить цикл несколько раз, когда n имеет несколько единиц в начале. Но проблема возникает, если длина двоичного числа очень велика, а число 1 очень велико, например10111......1110Если 1 миллион 1 опущен в середине, то, согласно решению 2, его все равно придется прокручивать более миллиона раз, это невыносимо, так что есть ли лучшее решение?

Если Redis знакомы детская обувь, вы можете подумать, что Redis также предоставляет структуру данных растровых данных, что обеспечивает функцию под названиемbitcountКоманду можно использовать для получения количества битов от начального байта до конечного байта строки со значением бита 1 (базовая структура Bitmap Redis — это строка, то есть структура sds. Если вы интересно, рекомендую к прочтениюRedis 5设计与源码分析Глава 2 и эта от Лао ЦяняТонкая внутренняя структура строк RedisЭто тоже стоит посмотреть.Статью о Redis Bitmap можно много погуглить.Вы можете прочитать эту статью.Волшебное использование Bitmap в Redis), так как же Redis вычисляет количество битов 1 в растровом изображении?

Redis bitcountЗаказ

Здесь нам нужно сначала представить алгоритм swar с переменной точностью. Этот раздел правильныйRedis 5 设计与源码分析Организация главы 11.5.4 «Команда подсчета битов» в первой книге, я действительно рекомендую вам перейти к книге и прочитать ее напрямую.

алгоритм сварки с переменной точностью

шестигранник бинарный Примечание
0x55555555 0101 0101 0101 0101 0101 0101 0101 0101 Нечетные биты равны 1, четные биты равны 0
0x33333333 0011 0011 0011 0011 0011 0011 0011 0011 Каждая цифра 1, каждая цифра 0
0x0F0F0F0F 0000 1111 0000 1111 0000 1111 0000 1111 Младшие 4 бита каждого байта равны 1, а старшие 4 бита равны 0.
0x01010101 0000 0001 0000 0001 0000 0001 0000 0001 Последний бит каждого байта равен 1

Обратите внимание на несколько чисел в приведенной выше таблице и используйте эти числа в качестве масок для участия в расчете:

int swar(uint32_t i) {
	// 第一步：计算每2位二进制数中1的个数
    i = (i & 0x55555555) + ((i>>1) & 0x55555555);
    // 第二步：计算每4位二进制数中1的个数
     i = (i & 0x33333333) + ((i>>2) & 0x33333333);
     // 第三步：计算每8位二进制数中1的个数
     i = (i & 0x0F0F0F0F) + ((i>>4) & 0x0F0F0F0F);
     // 第四步：将每8位当做一个int8的整数，然后相加求和
     i = (i * 0x01010101) >> 24;
     return i;
}

Изначально я хотел попытаться объяснить принцип этого алгоритма, но чувствую, что его не так легко понять, как объяснение чужого бога.How does this algorithm to count the number of set bits in a 32-bit integer work?Я рекомендую всем внимательно прочитать этот ответ. Его идея состоит в том, чтобы разделять и властвовать, и, наконец, объединять и суммировать, что чем-то похоже на идею сортировки слиянием.

реализация исходного кода

Портал исходного кода:GitHub.com/Redis/Redis…

bitcountРеализация команды использует для расчета комбинацию метода справочной таблицы и алгоритма swar. Так называемый «метод справочной таблицы» заключается в определении массива, и каждый элемент массива представляет собой число 1, содержащееся в десятичной дроби от 0 до 255, которое определяется следующим образом:

static const unsigned char bitsinbyte[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, ......}

Кроме того, ЦП может считывать из памяти значение 8 байт за раз, поскольку алгоритм swar обрабатывает содержимое 4 байтов за раз, поэтому байты, не являющиеся целыми кратными 4 байтам, должны быть специально обработаны в первую очередь. метод заключается в следующем:

while ((unsigned long) p & 3 && count) { // CPU一次性读取8字节，如果4字节跨了两个8字节，需要读取两次才可以读取，所以考虑4字节对齐，只需读取一次就可以读取4字节数据。
	bits += bitsinbyte[*p++]; // 查表法直接获取当前值中1的数量，有没有让你联想到java的Integer类有个类似的缓存机制
    count--;  // 待处理字节数--
}

Если вас интересует концепция «выравнивания байтов», вот статья, которую стоит прочитать.Подробное объяснение проблемы выравнивания байтов языка C.

После обработки первых до 3 возможных байтов алгоритм swar используется для получения количества единиц:

p4 = (uint32_t*) p; // 4字节
while (count>=28) { // 每次处理28个字节
	uint32_t aux1, aux2, aux3, aux4, aux5, aux6, aux7;
    
    aux1 = *p4++; // 一次读取4字节
    aux2 = *p4++; // 一次读取4字节
    ...
    aux7 = *p4++;
    count -= 28; // 当前共处理了 4*7=28 个字节，所以总长度需要减28字节
    
    aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
    aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
    aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
    aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
    aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
    aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
    aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
    aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
    aux5 = aux5 - ((aux5 >> 1) & 0x55555555);
    aux5 = (aux5 & 0x33333333) + ((aux5 >> 2) & 0x33333333);
    aux6 = aux6 - ((aux6 >> 1) & 0x55555555);
    aux6 = (aux6 & 0x33333333) + ((aux6 >> 2) & 0x33333333);
    aux7 = aux7 - ((aux7 >> 1) & 0x55555555);
    aux7 = (aux7 & 0x33333333) + ((aux7 >> 2) & 0x33333333);
    bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) +
                ((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) +
                ((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) +
                ((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) +
                ((aux5 + (aux5 >> 4)) & 0x0F0F0F0F) +
                ((aux6 + (aux6 >> 4)) & 0x0F0F0F0F) +
                ((aux7 + (aux7 >> 4)) & 0x0F0F0F0F))* 0x01010101) >> 24;
}

Когда число счетчиков меньше 28, можно использовать метод поиска по таблице для вычисления количества оставшихся двоичных единиц.

p = (unsigned char*)p4;
while(count--) bits += bitsinbyte[*p++];
return bits;

постскриптум

После анализа я закинул резюме в групповой чат, а коллеги назвали меня экспертами, и не могли не поставить лайк 🐶

Вот некоторые ресурсы для справки:

Категории