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

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

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;
}
10.12.2008 17:42:23
Вы можете потерять два варианта продолжения, используя else if и else. Оптимизатор, вероятно, сделает это за вас. Вы также можете переместить объявление cmpValue в цикл; это не повлияет на производительность, но приведёт в порядок код.
Jonathan Leffler 10.12.2008 19:19:09
9 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

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

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

4
11.12.2008 20:19:44

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

4
10.12.2008 17:45:30
Я думаю, что эта функция максимально оптимизирована.
Georg Schölly 10.12.2008 17:55:33
Однако обратите внимание, что стоимость передачи функции (и т. Д.) Может перевесить выгоды от оптимизированного поиска, так же, как qsort C часто медленнее, чем std :: sort C ++.
ShreevatsaR 11.12.2008 11:11:23

Единственная потенциальная оптимизация, о которой я могу подумать, - это использовать что-то похожее на золотое сечение при расчете, 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;
        }
0
11.12.2008 10:26:44
Золотое сечение не будет делиться равным половине. (Низ + верх) / 2 только поделит ровно половину. Золотое деление требуется, когда набор имеет естественный прирост, такой как ежемесячный подсчет лепестков, клеток бактерий и т. Д.
lakshmanaraj 11.12.2008 10:44:39

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

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

0
11.12.2008 10:59:00
Любой полуприличный компилятор сделает это автоматически. Сдвиг следует использовать только тогда, когда вы имеете в виду смещение, т. Е. При работе с битами, как в масках и т. Д. Когда вы имеете в виду «сделать это число наполовину большим», просто разделите и дайте компилятору разобраться с этим.
unwind 11.12.2008 11:08:24
Общее правило таких микрооптимизаций: если ваш компилятор все равно их не делает, это снижает производительность до такой степени, что микрооптимизации не помогут.
David Thornley 11.12.2008 19:54:07

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

0
11.12.2008 11:13:27
Я полагаю, что современные компиляторы могут объединять такой дублированный код автоматически
dmityugov 11.12.2008 12:50:05

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

2
11.12.2008 11:20:19

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

1
11.12.2008 19:37:40

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

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

1
11.12.2008 19:52:41

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

Я посмотрел выход 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. Приятное прикосновение.

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

0
11.12.2008 20:36:12