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

StackOverflow https://stackoverflow.com/questions/356928

  •  21-08-2019
  •  | 
  •  

Вопрос

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

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;
}
Это было полезно?

Решение

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

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

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

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

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

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

Другие советы

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

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

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

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

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

Единственная потенциальная оптимизация, о которой я могу думать, — это использовать что-то похожее на золотое сечение при расчете. 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;
        }

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

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

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

Хотя я ожидал, что достойный оптимизатор сделает это за вас, я бы поместил Map->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.Приятное прикосновение.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top