Упорядоченный двоичный поиск с сборкой | Рекурсивный против итеративного против библиотеки

Question

Что лучше?

Согласно Savich, каждая рекурсия сохраняется в стеке в виде кадра активации. Это накладные расходы. Однако для записи рекурсивной версии требуется несколько строк кода. Для интервью, которое лучше включить. Код для обоих приведен ниже.

#include <iostream> 

using namespace std; 
const int SIZE = 10; 
int array[ SIZE ] = { 0,1,2,3,4,5,6,7,8,9 }; 
int answer = NULL; 

void binary_search_recursive(int array[], int start, int end, int value, int& answer) 
{ 
    int mid = (start + end)/2; 

    if (array[ mid ] == value) 
    { 
     answer = mid; 
    } 
    else if (array[ mid ] < value) 
    { 
     binary_search_recursive(array, mid + 1, end, value, answer); 
    } 
    else 
    { 
     binary_search_recursive(array, start, mid - 1, value, answer); 
    } 
} 

void binary_search_iterative(int array[], int start, int end, int value, int& answer) 
{ 
    int mid = ((start + end)/2); 

    while(array[ mid ] != value ) 
    { 
     if (array[ mid ] < value) 
     { 
      start = mid; 
      mid = (((mid + 1) + end)/2); 
     } 
     else 
     { 
      end = mid; 
      mid = ((start + (mid - 1))/2); 
     } 
    } 
    answer = mid; 
} 

int main() 
{ 
    binary_search_iterative(array, 0, SIZE - 1, 4, answer); 
    cout << answer; 
    return 0; 
} 

Answer 1

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

Если у вас нет причины, в настоящем проекте я бы использовал std::binary_search от <algorithm> (http://www.sgi.com/tech/stl/binary_search.html).

Чтобы проиллюстрировать рекурсию хвоста, ваш алгоритм binary_search_recursive был изменен на сборку ниже на g++ -O4 -S. Примечания:

• , чтобы получить представление о коде, вы не должны понимать каждую строку, но следующие помогают:
  • movl являются заявлением перемещения (назначения) между регистрами и памятью (отстающий " л»для„длинных“отражает количество битов в местах регистров/память)
  • subl, shrl, sarl, cmpl являются вычитание, сдвиг вправо, арифметический сдвиг вправо, а сравнить инструкции, а главное, чтобы отметить, что в качестве побочного эффекта они устанавливают несколько флагов, таких как «равно», если они производят a 0 результат, с которым консультируется je (прыжок, если равен) и jge (прыжок, если больший или равный), jne прыжок, если не равен.
• Условие терминации answer = mid обрабатывается на L10, тогда как рекурсивные шаги обрабатываются кодом на L14 и L4 и могут возвращаться к L12.

Вот разборка вашей binary_search_recursive функции (имя искажается в C++ стиля) ...

__Z23binary_search_recursivePiiiiRi: 
    pushl %ebp 
    movl %esp, %ebp 
    pushl %edi 
    pushl %esi 
    pushl %ebx 
    subl $4, %esp 
    movl 24(%ebp), %eax 
    movl 8(%ebp), %edi 
    movl 12(%ebp), %ebx 
    movl 16(%ebp), %ecx 
    movl %eax, -16(%ebp) 
    movl 20(%ebp), %esi 
    .p2align 4,,15 
L12: 
    leal (%ebx,%ecx), %edx 
    movl %edx, %eax 
    shrl $31, %eax 
    leal (%edx,%eax), %eax 
    sarl %eax 
    cmpl %esi, (%edi,%eax,4) 
    je  L10 
L14: 
    jge  L4 
    leal 1(%eax), %ebx 
    leal (%ebx,%ecx), %edx 
    movl %edx, %eax 
    shrl $31, %eax 
    leal (%edx,%eax), %eax 
    sarl %eax 
    cmpl %esi, (%edi,%eax,4) 
    jne  L14 
L10: 
    movl -16(%ebp), %ecx 
    movl %eax, (%ecx) 
    popl %eax 
    popl %ebx 
    popl %esi 
    popl %edi 
    popl %ebp 
    ret 
    .p2align 4,,7 
L4: 
    leal -1(%eax), %ecx 
    jmp  L12 

Answer 2

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

Что касается алгоритма бинарного поиска, более быстрые реализации записываются как итеративные. Например, опубликованная версия бинарного поиска Джона Бентли является итеративной.

Answer 3

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

Answer 4

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

Я думаю, что наилучшим подходом к интервью было бы представить решение, которое называет lower_bound: оно показывает интервьюеру, что вы не только знаете какой-то синтаксис базового уровня и как кодировать алгоритм первокурсника, но и то, что вы делаете не теряя времени переписывая шаблонный код.