4

Читаю книгу "Язык программирования Си" Брайана Кернигана. В разделе про условные операторы наткнулся на реализацию бинарного поиска, представленную в коде ниже, а далее шло интересное упражнение, где указывалось, что можно написать бинарный поиск с меньшим количеством проверок внутри цикла. И предлагалось подумать над тем, какой же из них будет быстрее. Я, логично, предположил, что выиграет реализация с меньшим количеством условных операторов, но эксперименты показали интересный обратный результат. Я использовал модуль time.h для измерения времени выполнения программы. Помогите разобраться почему же так выходит.

Команда для компиляции gcc binarysearch.c -o binarysearch.exe

    //Task 3.1
    #include <stdio.h>
    #include <time.h>

    #define ML 100000u //Размер массива
    #define BETTER_BIN_SEARCH

    int binsearch(int x, int v[], int n); 

    int main(){
        int v[ML];//Массив в котором ведется поиск
        int i = 0;
        for(i = 0; i < ML; ++i){//Инициализация элементов
            v[i] = i;
        }

        //printf("CLOCKS_PER_SEC = %d\n", CLOCKS_PER_SEC);//Выдает 1000
    #ifdef BETTER_BIN_SEARCH
        printf("My search\n");
    #else
        printf("Book's search\n");
    #endif
        //Многократное выполнение поиска
        clock_t st = clock(); //StartTime
        for(int j = 0; j < 2000; ++j)
            for(i = 0; i < ML; ++i){
                binsearch(i, v, ML);
            }
        clock_t oat = clock() - st;//OverAllTime
        printf("Over all time = %d\n", oat);

        return 0;
    }

    #ifdef BETTER_BIN_SEARCH
    //Моя версия поиска
    //В среднем время выполнения 20200-20300
    int binsearch(int x, int v[], int n){
        unsigned low, mid, high;
        low = 0;
        high = n-1;
        while(low < high){
            mid = (low + high) / 2;
            if(v[mid] < x){
                low = mid + 1;
            }
            else{
                high = mid;
            }
        }
        if(x == v[low])
            return low;
        return -1;
    }
    #else
    //Реализация из книги
    //В среднем время выполнения 18700-19100
    int binsearch(int x, int v[], int n){
        unsigned low, high, mid;
        low = 0;
        high = n - 1 ;
        while (low <= high) {
            mid = (low + high) / 2;
            if (x < v[mid])
                high = mid - 1;
            else if (x > v[mid])
                low = mid + 1 ;
            else /* совпадение найдено */
                return mid;
         }
         return -1; /* совпадения нет */

    }
    #endif
4
  • 4
    Прежде чем делать какие либо выводы о произволительности, необходимо включить оптимизацию gcc -O3 binarysearch.c -o binarysearch.exe. Код не читал
    – extrn
    21 авг 2020 в 2:41
  • 3
    В вашей версии не учитывается быстро найденный элемент. И цикл идёт до максимальной сложности, со сложностью Log[N]. А в книге быстро найденный сразу выдаёт индекс и выходит из цикла. По теории вероятности у него время Log[N]-1.
    – AlexGlebe
    21 авг 2020 в 8:11
  • Оптимизатор компилятора в книжной версии два сравнения x < v[mid] и x > v[mid] превратит в одно. Ассемблер просто выставит флаги (больше/меньше).
    – AlexGlebe
    21 авг 2020 в 9:37
  • @AlexGlebe, я попробовал компиляцию с оптимизацией -O3 и моя версия оказалась быстрее, как я и предполагал. Дело в том что, несмотря на отсутствие проверки на быстро найденный элемент, в общем случае этот алгоритм работает на ~10% быстрее(узнал на прогонах), так как в цикле происходит меньшее количество проверок.
    – Cheeba
    21 авг 2020 в 19:20

1 ответ 1

4

Ключевое наблюдение не совсем верно: на самом деле для маленьких массивов «книжная» версия действительно быстрее, а для больших (N>220 ~ 224) быстрее оказывается «твоя».

У такого поведение две основные причины:

  • Во-первых, «твоя» версия в среднем даёт одну лишнюю итерацию цикла. Это заложено алгоритмом, а т.к. итераций в цикле не много (~log2N), то это оказывает эффект замедления.

  • Во-вторых, сравнения не равнозначны по скорости.
    На практике компилятор почти наверняка преобразует «книжную версию» в нечто подобное (ассеблеро-подобный псевдокод):

    loop_iteration:
      cmp low, high
      jle exit
    
      cmp x, v[mid] ; сравнить x и v[mid]
      jl less       ; jump if less,    перейти на less, если (x - v[mid]) < 0
      jg more       ; jump if greater, перейти на more, если (x - v[mid]) > 0
      ; если ни один из переходов не произошёл, то вернуть 0
      ret x
    
    less:
      eval  high := mid - 1
      jmp loop_iteration ; Переход на следующую итерацию цикла
    more:
      eval  low  := mid + 1
      jmp loop_iteration ; Переход на следующую итерацию цикла
    
    exit:
      ret -1
    

    Для современных процессоров значительное влияние на скорость вычислений оказывает то, насколько точно они могут предугадать, когда будет совершён условный переход (jg и jl), а когда нет.

    Так вот, в фрагменте выше предсказать, будет ли совершён jl или нет — практически невозможно, его вероятность близка к 50%, поэтому в половине случаев блок предсказаний ошибается и это «сравнение» оказывается довольно дорогим.

    Переход по jg, напротив, стохастически, намного чаще происходит, чем нет: ведь элемент намного чаще оказывается меньшеше искомого, чем в точности равным ему. Поэтому блок предсказаний делает вывод, что он обычно происходит и часто оказывается прав, так что в большинстве случаев это «сравнение» оказывается дешёвым.

    В случае же с «твоей» реализацией сравнение действительно одно и оно в половине случаев оказывается «дорогим», как и jl в «книжном» варианте.

Так вот, для малых N одно такое «дорогое сравнение» из-за лишний итерации оказывается медленнее, чем много «дешёвых». Но с ростом размера массива эта ситуация изменяется в обратную сторону.


Другие замечания

  • Как уже заметили в комментариях, при проверках на производительность стоит компилировать с оптимизацией (ключ -ON для gcc, где N одно из 1, 2, 3, S). Хотя в данном случае это не должно было оказать серьёзного эффекта.
  • С методикой тестирования также есть проблемы: последовательный поиск всех элементов массива также может внести свои искажения. Следовало бы заменить это на поиск [псевдо]случайных значений.
  • «Твоя» реализация бинарного поиска имеет важную особенность — она находит наименьший индекс. По сути это поиск нижней грани в упорядоченной последовательности.
  • У «Книжной» реализации есть проблема — она выходит за границы, если ищется элемент меньше минимального.
0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.