Бинарные поисковая оптимизация: Керниган & Ритчи 3-1


Проблему я пытаюсь решить можно охарактеризовать как взять binarysearch0 и переписать его как binarysearch1 такие, что binarysearch1 использует один тест внутри петли вместо двух. Код, который я использовал для этого рассматривается ниже. Пожалуйста, дайте мне знать, если вы думаете, что я справился с этой задачей, и что я могу сделать лучше.

#include <stdlib.h>
#include <stdio.h>

void printdata(int *v, int n)
{
    int i = 0;
    for (i = 0; i < n; ++i) {
        printf("%3d", v[i]);
    }
    putchar('\n');
}

int binarysearch0(int x, int *v, int n)
{
    int 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;
}

int binarysearch1(int x, int *v, int n)
{
    int low, high, mid;

    low = 0;
    high = n - 1;
    while (low <= high && v[(mid = (low + high) / 2)] != x ) {
        mid = (low + high) / 2;
        if ( x < v[mid])
            high = mid -1;
        else
            low = mid + 1;
    }
    return (v[mid] == x) ? mid : -1;
}

int main(int argc, char *argv[])
{
    int v[10][10] = { { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
                      {10,11,12,13,14,15,16,17,18,19},
                      {20,21,22,23,24,25,26,27,28,29},
                      {30,31,32,33,34,35,36,37,38,39},
                      {40,41,42,43,44,45,46,47,48,49},
                      {50,51,52,53,54,55,56,57,58,59},
                      {60,61,62,63,64,65,66,67,68,69},
                      {70,71,72,73,74,75,76,77,78,79},
                      {80,81,82,83,84,85,86,87,88,89},
                      {90,91,92,93,94,95,96,97,97,99}
                    };

    int i = 0;
    for (i = 0; i < 10; ++i) {
        int search = 0;
        (i == 0) ? (search = 1000) : (search = v[i][0] + rand()%10);
        if(binarysearch1(search, v[i], 10) > -1) {
            printf("%d was found in the data: %14s", search, " ");
            printdata(v[i], 10);
        } else {

            printf("%d was NOT found in the data: %10s", search, " ");
            printdata(v[i], 10);
        }
        putchar('\n');
    }
    return 0;
}


2109
3
задан 19 ноября 2011 в 08:11 Источник Поделиться
Комментарии
3 ответа

Вы действительно не меняется количество сравнений внутри цикла здесь: все, что вы сделали, переместить его из тела цикла условие выхода. Обратите внимание, что во многих ситуациях, сравнения на элементы массива (которые могут быть строками или более сложные объекты) много дороже, чем сравнения показателей.

Вы можете найти несколько решений этого упражнения на КГО-Вики. Я думаю, что один из них (Павел Гриффита) не попадает в точку (это почти так же как у тебя); я хочу показать объяснить мотивы Андрея Tesker и решения Колин Баркер.

В исходной функции binsearch, внутри цикла, существуют три возможные ситуации: х, х==в[середине] и Х>в[середине]. Иногда, функция сравнения имеет три исхода: меньше, равна или больше; в таких случаях подход к первоначальной функции, является лучшим. Например, если мы были сравнения строк strcmp стандарта:

    int cmp = strcmp(x, v[mid]);
if (cmp < 0) high = mid - 1;
else if (cmp > 0) low = mid + 1;
else return mid;

В других случаях только примитивные у вас меньше или меньше или равно, а для проверки на равенство требует второго сравнения. Таким образом, метод, представленный в K&R требует двух вызовов функции сравнения в каждой итерации через петлю. Это более эффективно, требует одного сравнения. Теперь нам нужно обязательно различать между "меньше" и "больше чем" дело, значит, мы не сможем заниматься делом равенства внутри цикла. Поэтому мы будем продолжать идти вверх или вниз в случае равенства. Так как мы не проверяли значение в[середине] в одном из случаев, мы должны держать его внутри пространства поиска.

    if (x < v[mid]) high = mid - 1;
else low = mid;

Что происходит с прекращением цикла? Теперь, мы можем застрять с низким == высокий и Х >= в[низкая]. Однако, это легко решается путем прекращения цикла при низком == высокий.

while (low < high) {
mid = (low + high + 1) / 2;
if (x < v[mid]) high = mid - 1;
else low = mid;
}

Обратите внимание, что я поставил средний к низкий + высокий + 1. В случае, когда минимум + 1 == высокое, (минимум + максимум) / 2 - это минимум, а если Х все равно слишком мало, мы сидели в середине к низким и бесконечный цикл (благодаря Elyasin заметила, что мой оригинальный ответ был такой баг). В этом случае мы организуем для середины должен быть установлен на максимум. Если низкий <= высокая выходим из цикла в любом случае, и в других случаях мы будем продолжать цикл, и это изменение приводит к тому, что посередине должно быть округлено вверх, а не вниз.

На выходе из петли, если есть соответствующий элемент в массиве, затем в[низкая] равна ей. Поэтому мы выполняем итоговый тест равенства:

return x == v[low] ? low : -1;

Число элементов сравнения, выполняемые оригинальная версия где-то от 1 до 2*Сэл(log₂(Н)+1), где n-количество элементов в массиве. Количество элементов сравнения в версии с один сравнении в цикле всегда цежь(log₂(н))+2. Это меньше максимальной, но не обязательно приобрести, потому что оригинальная версия будет завершить раньше, если он находит элемент. Оригинальная версия предпочтительнее, когда есть хороший шанс, что элементов будет в массиве. Модифицированный вариант более предпочтителен, когда элемент встречается редко.

8
ответ дан 19 ноября 2011 в 10:11 Источник Поделиться

В binarysearch1, вы заменили один тест в петле тело с одного теста в цикле условие. Это не уменьшить количество тестов, и я согласен с Жилем, binarysearch0 понятнее. Я бы рекомендовал хранить, что. Однако, в обоих поисковых запросов, расчет среднего = (минимум + максимум) / 2 может переполниться, если вы ищете большой. Использовать переполнение-безопасный расчет вместо. Читаемый один средний = низкий + (максимум - минимум) / 2 (Если вы можете гарантировать, что низкое и высокое не отрицательной, из INT_MAX - INT_MIN , например, переполнения).

3
ответ дан 19 ноября 2011 в 10:11 Источник Поделиться

Я бы не стал тратить время беспокоясь о факторинге от одного из двух сравнений, потому что хороший компилятор должен быть в состоянии так или иначе оптимизировать их в один. (Может быть, во Керниган и Ричи составители времени были не настолько умен, чтобы провернуть такие фокусы, так что, возможно, этот вопрос был значимым, но поверьте, они прошли очень долгий путь с тех пор!)

Компилятор знает, что Х и в[середине] (или результат вызова функции сравнения) не изменяется , если заявление, поэтому он выдает код, который сравнивает эти два операнда только один раз. Результаты сравнения будут храниться в Неси (С) и ноль (з) биты флагов реестр x86 процессора, следующим образом: если Z, то это означает, что оба операнда сравнения были равны; в противном случае, если c имеет значение, то второй операнд больше, чем первое; в противном случае (оба флага понятно,) второй операнд меньше, чем первое. Так что, если компилятор умный вообще, после сравнения инструкция он будет излучать два последовательных условный переход по инструкции, которая будет филиал на низкий = середина + 1 часть если результат сравнения был 'больше чем', (з=0, С=0,) и немедленно вслед за этим будет филиал на высокий уровень = средний - 1 часть, если результат сравнения "меньше, чем". (З=0, С=1.) Прыжок инструкции никогда не изменяет флагов - регистр процессора, поэтому после первого прыжка инструкцию изучила флаги, и решил не на ветку, флаги сохранятся для второй прыжок инструкций и ознакомления с ними. И если вторая инструкция прыжок решает не филиал либо, то центральный процессор будет падать в код, который будет обрабатывать последний оставшийся случай, когда операнды равны.

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

1
ответ дан 28 ноября 2011 в 11:11 Источник Поделиться