Что быстрее: логарифм или таблица поиска? [Дубликат]

Это довольно распространенная проблема для шахматных программ, которые используют 64 бита для представления позиций (то есть один 64-разрядный номер для хранения, где все белые пешки, другой для всех черных и т. д.).

При таком представлении иногда требуется найти индекс 0 ... 63 первого или последнего бита набора и существует несколько возможных подходов:

1. Просто выполняя цикл как и вы
2. Используя дихотомический поиск (т. е. если x & 0x00000000ffffffffULL равен нулю, нет необходимости проверять низкие 32 бита)
3. Используя специальную инструкцию, если она доступна на процессоре (например, bsf и bsr на x86)
4. Использование таблиц поиска (конечно, не для всего 64-битного значения, а для 8 или 16 бит)

Что такое быстрее, однако действительно зависит от вашего оборудования и от реальных случаев использования. Только для 8-битных процессоров и для современного процессора я считаю, что лучше всего найти таблицу поиска с 256 записями ...

Но вы действительно уверены, что это узкое место в вашем алгоритме?

Таблица поиска достаточно проста, и вы можете уменьшить ее размер, если набор значений разрежен. Попробуем использовать 11 элементов вместо 128:

unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5};
unsigned char pos = expt2mod11_bits[b%11];
assert(pos < 8);
assert(1<<pos == b);

Конечно, это не обязательно более эффективно, особенно для 8 бит, но тот же трюк можно использовать для больших размеров, где полная таблица поиска будет ужасно большой. Давайте посмотрим:

unsigned int w; 
....
unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9};
unsigned char pos = expt2mod19_bits[w%19];
assert(pos < 16);
assert(1<<pos == w);

Таблица поиска быстро и просто, когда CHAR_BIT == 8, но в некоторых системах CHAR_BIT == 16 или 32, и таблица поиска становится безумно громоздкой. Если вы рассматриваете таблицу поиска, я бы предложил ее обернуть; сделайте его «функцией таблицы поиска», вместо этого, чтобы вы могли поменять логику, когда вам нужно оптимизировать.

Использование divide и conquer путем выполнения двоичного поиска в отсортированном массиве предполагает сравнение на основе log2 CHAR_BIT. Этот код более сложный, включая инициализацию массива unsigned char для использования в качестве таблицы поиска для начала. После инициализации такого массива вы можете использовать bsearch для поиска, например:

#include <stdio.h>
#include <stdlib.h>
void uchar_bit_init(unsigned char *table) {
    for (size_t x = 0; x < CHAR_BIT; x++) {
        table[x] = 1U << x;
    }
}
int uchar_compare(void const *x, void const *y) {
    char const *X = x, *Y = y;
    return (*X > *Y) - (*X < *Y);
}
size_t uchar_bit_lookup(unsigned char *table, unsigned char value) {
    unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare);
    return position ? position - table + 1 : 0;
}
int main(void) {
    unsigned char lookup[CHAR_BIT];
    uchar_bit_init(lookup);
    for (;;) {
        int c = getchar();
        if (c == EOF) { break; }
        printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c));
    }
}

P.S. Это звучит как микро-оптимизация. Получите свое решение (абстрагирование операций, требуемых для этих функций), а затем подумайте об оптимизации на основе профилирования. Убедитесь, что профилирование нацелено на систему, над которой будет работать ваше решение, если вы собираетесь сосредоточиться на микрооптимизации, поскольку эффективность микрооптимизации сильно различается, поскольку аппаратное обеспечение отличается даже немного ... Обычно лучше купить более быстрый ПК;)

Самое простое - создать таблицу поиска.

Этот комментарий здесь технически избегает итерации, но кто мы шутим, он по-прежнему делает такое же количество проверок: Как написать базу данных (2) в c / c ++

Закрытая форма будет log2 () , a la, log2() + 1 Но я не уверен, насколько эффективен это - возможно, у процессора есть инструкция для приема логарифмов базы 2?

Основываясь на вычислении log2 в Найдите базу данных 2 целочисленного N-бита в операциях O (lg (N)) :

int getSetBitLocation(unsigned char c) {
  // c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7}
  return (((c & 0xAA) != 0) |
          (((c & 0xCC) != 0) << 1) |
          (((c & 0xF0) != 0) << 2));
}

unsigned getSetBitLocation(unsigned char b) {
  unsigned pos=0;
  pos = (b & 0xf0) ? 4 : 0; b |= b >>4;
  pos += (b & 0xc) ? 2 : 0; b |= b >>2;
  pos += (b & 0x2) ? 1 : 0; 
  return pos; 
}

Было бы трудно сделать это без прыжка. Может быть, с последовательностями Брюина?

, если вы определяете

const char bytes[]={1,2,4,8,16,32,64,128}

и используете

struct byte{
char data;
int pos;
}
void assign(struct byte b,int i){

b.data=bytes[i];
b.pos=i
}

, вам не нужно определять позицию установленного бита