Оптимизация бинарного поиска в c?

Question

Я пишу запись ключа, посмотрите, где у меня есть индекс между ключом и номером записи. Это отсортировано по ключу. Можно ли сделать это лучше, чем то, что у меня есть для оптимизации скорости?

typedef struct
{
    char key[MAX_KEYLEN];
    int  rec;
} KeyRecPair;

typedef struct
{
    KeyRecPair *map;
    int         numRecs;
} KeyRecMap;

int GetRecFromKey(char *key, KeyRecMap *theMap)
{
    int cmpValue, bottom = 0;
    int half = theMap->numRecs / 2;
    int top = theMap->numRecs - 1;

    while (bottom != top)
    {
        cmpValue = strncmp(key, theMap->map[half].key, MAX_KEY_LEN); 

        if (cmpValue > 0)
        {
            /*top stays*/
            bottom = half + 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        if (cmpValue < 0)
        {
            /*bottom stays*/
            top = half - 1;
            half  = bottom + (top - bottom) / 2;
            continue;
        }
        return theMap->map[half].rec;
    }

    if (0 == strncmp(key, theMap->map[half].key, MAX_KEY_LEN))
        return theMap->map[half].rec;
    return 0;
}

Answer 1

Хорошая часть вашего времени будет потрачена в strncmp.

Я предлагаю установить значение встраиваемым или переписать его встроенным, чтобы избежать вызова функции из-за накладных расходов.

Если вы чувствуете себя смелым, возможно, развернет цикл один или два раза и увидит прирост производительности.

Если ваша строка на самом деле имела фиксированную длину массива char, вы могли бы сделать ее кратной 4 и сравнивать 4 байта за раз с int без знака, вместо 1 байта за раз.

Если у вас нет профилировщика , вы должны его получить. Профилировщики позволяют легко увидеть, какова относительная стоимость различных реализаций.

Другой вариант - выбрать другой способ организации ваших данных. Проверьте AVL деревья для вдохновения. Выбор какой-либо функции хеширования , как и другие упомянутые, может быть приемлемым вариантом

Answer 2

Библиотечная функция bsearch выполняет двоичный поиск по массиву с учетом подходящей функции сравнения, которую вы реализуете. Будучи библиотечной функцией, она хорошо оптимизирована и (надеюсь) не содержит ошибок.

Answer 3

Вместо использования бинарного поиска для определения местоположения может быть более подходящей хеш-карта, поскольку она имеет O (1) характеристики поиска. Однако это может быть медленно с нагрузкой столкновений с наивным подходом. Однако в этой статье описан способ создания дерева хеш-карт, которое имеет время доступа O (log (n) / log (32)), которое обычно превосходит обычные реализации хэш-карт. (Исправлена ​​реализация связанного списка aray +).

Answer 4

Есть ли причина желать оптимизировать это? Запустили ли вы программу с профилировщиком и определили, что поиск занимает значительную часть общего времени выполнения? Вам просто интересно, как быстро вы можете получить это? (Либо, на мой взгляд, веские причины.) Если вы просто случайно оптимизируете это, не надо.

Кроме того, не забудьте оценить. Трудно сказать, какая из двух версий функции быстрее в современной системе (на моем Z80 это было проще). Сколько пропусков в кеше может быть или не быть более важным, чем количество ошибочно предсказанных ветвей.

Answer 5

Есть ли шанс, что вы могли бы использовать ключ, который не является строкой? или хотя бы самые короткие строки? (что является значением MAX_KEYLEN), что strcmp на каждой итерации цикла, вероятно, является одной из более медленных частей поиска.

Answer 6

Хотя я и ожидал, что достойный оптимизатор сделает это за вас, я бы поместил карту -> карту в локальную систему, чтобы у нее была половина шансов попасть в регистр, а не разыменовывать ее при каждом доступе. Опять же, я ожидаю, что оптимизатор сделает это за вас, поэтому вы также можете проверить вывод сборки.

Я посмотрел выход Visual Studio 2008 в выпуске, и он неплохо справился с кодом. Например, код сравнения выглядит так:

; 30   :         if (cmpValue > 0)
test    eax, eax
jle SHORT $LN11@GetRecFrom
; 31   :         {
; omitted inner block for > case.
$LN11@GetRecFrom:
; 37   :         if (cmpValue < 0)
jge SHORT $LN2@GetRecFrom

В основном это ветвление без повторного тестирования cmpValue. Приятное прикосновение.

Есть небольшая выгода от размещения карты -> локальная карта, но она крошечная. Если MAX_KEY_LEN не является хорошим кратным 4, и структуры не дополняются, вы должны обязательно поставить int первым в своей структуре.

Answer 7

Поскольку вам придется вычислять half один раз за цикл, почему бы просто не сделать это один раз, непосредственно перед его использованием? Это сократит две сложные (по крайней мере, условно говоря) строки кода.

Answer 8

Вместо деления на 2 U можно использовать оператор сдвига битов.

=> для / 2 вы можете использовать >> 1

Answer 9

Единственная потенциальная оптимизация, о которой я могу подумать, - это использовать что-то похожее на золотое сечение при расчете half вместо деления оставшегося подмножества на две половины с равным количеством элементов, то есть

        if (cmpValue > 0)
        {
                /*top stays*/
                bottom = half + 1;
                half = bottom + (top - bottom) * 3 / 5;
                continue;
        }
        if (cmpValue < 0)
        {
                /*bottom stays*/
                top = half - 1;
                half = bottom + (top - bottom) * 2 / 5;
                continue;
        }