Почему сортировка вставками с использованием двоичного поиска выполняется медленнее, чем сортировка вставками с использованием линейного поиска?

Почему сортировка вставками с использованием двоичного поиска выполняется медленнее, чем сортировка вставками с использованием линейного поиска?

Код для сортировки вставками с использованием линейного поиска:

void InsertionSort(int data[], int size)
{
    int i=0, j=0, temp=0;

    for(i=1; i<size; i++)
    {
     temp = data[i];
     for (j=i-1; j>=0; j--)
         {
             if(data[j]>temp)
             data[j+1]=data[j];
             else  
                 break;
         }
     data[j+1] = temp;       
    }        
}

Код для сортировки вставками с использованием линейного поиска:

void InsertionSort (int A[], int n)
{
    int i, temp;
    for (i = 1; i < n; i++)
    {
        temp = A[i];

        /* Binary Search */

        int low = 0, high = i, k;

        while (low<high)
        {
            int mid = (high + low) / 2;


            if (temp <= A[mid]) 
                high = mid;

            else 
                low = mid+1;
        }

        for (k = i; k > high; k--)
            A[k] = A[k - 1];


        A[high] = temp;
    }
 }

Хотя количество сравнений с использованием двоичного поиска = O(nlogn) и количество сравнений с использованием линейного поиска = O(n^2) для среднего случая.

введите здесь описание изображения

Где исходная сортировка вставки — это сортировка с линейным поиском, а модифицированная сортировка вставки — с двоичным поиском.


performance algorithm insertion-sort
person Ammar Alyousfi    schedule 10.11.2013    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Потому что в первом случае поиск и перемещение совмещаются, а во втором поиск — это просто лишняя работа.

Сравнение целых чисел дешево по сравнению с перемещением целых чисел. Учитывайте деления, накладные расходы цикла, принятые условные переходы в каждой итерации цикла по сравнению с неиспользованными переходами cond и т. д.

PS. Действительно, в версии с линейным поиском внутренний цикл обычно выглядит так:

.L5:
    leaq    -1(%rcx), %rsi
    movl    4(%rdi,%rsi,4), %eax
    cmpl    %eax, %r9d
    jge .L3
    movq    %rcx, %r8
    movq    %rsi, %rcx
    subl    $1, %edx
    movl    %eax, 4(%rdi,%r8,4)
    cmpl    $-1, %edx
    jne .L5
    movq    $-1, %rcx
.L3:

где jge .L3 выполняется только один раз, и можно разумно ожидать, что эта ветвь будет предсказана невыполненной и не окажет вредного влияния на конвейер.

Что касается внутреннего цикла в другой версии, я не хочу на него смотреть :)

PS. Кстати, линейный поиск также имеет несколько лучшую локальность, тогда как бинарный поиск прыгает повсюду.

person chill    schedule 10.11.2013
comment
И в лучшем случае: сортировка вставками с использованием двоичного поиска выполняется быстрее, чем сортировка вставками с использованием линейного поиска, поскольку время выполнения сортировки вставками с использованием двоичного поиска = O(nlogn), а время выполнения сортировки вставками с использованием линейного поиска = O(n). Верно? - person Ammar Alyousfi; 10.11.2013
comment
Нет, оба O (n ^ 2). Вы можете делать асимптотически меньше сравнений при использовании бинарного поиска, но все же вы делаете что-то вроде 1 + 2 + 3 + ... + n-1 ходов всего в худшем случае, массив отсортирован в обратном порядке. - person chill; 10.11.2013
comment
Ой, извините, я не заметил, что вы написали лучший вариант. - person chill; 10.11.2013
comment
Но я вижу, что даже поиск и перемещение данных не совмещаются во втором случае, происходит одинаковое количество перемещений данных!. Я смущен. - person Ammar Alyousfi; 10.11.2013
comment
Количество перемещений данных такое же, но количество обращений к данным выше для версии бинарного поиска. Кроме того, сортировка вставками выполняется во время ожидания памяти, поэтому сравнение практически бесплатно. Часть вставки бинарного поиска ничего не делает во время ожидания памяти, поэтому вы выбрасываете циклы. - person Raymond Chen; 10.11.2013