Оптимизировать алгоритм двоичного поиска - PullRequest
4 голосов
/ 23 марта 2009

В бинарном поиске у нас есть два сравнения: одно больше, а другое меньше. чем его среднее значение. Как бы вы оптимизировали, чтобы мы проверяли только один раз?

bool binSearch(int array[], int key, int left, int right)
{

    mid = left + (right-left)/2;
    if (key < array[mid])
        return binSearch(array, key, left, mid-1);
    else if (key > array[mid])
        return binSearch(array, key, mid+1, right);
    else if (key == array[mid])
        return TRUE; // Found

    return FALSE; // Not Found
}

Ответы [ 12 ]

17 голосов
/ 23 марта 2009

Сначала я бы попробовал стандартную функцию bsearch () . Скорее всего, он работает лучше, чем ваш подход.

8 голосов
/ 23 марта 2009

Не рекомендуется пытаться оптимизировать так, как вы описываете. Из статьи Алгоритм двоичного поиска в Википедии :

Примерно в половине случаев первый тест будет истинным, так что будет только одно сравнение a и b, но в другой половине времени он будет ложным, а второе сравнение будет принудительным. Это настолько печально, что некоторые версии переделываются так, чтобы вообще не проводить второго теста, не определяя равенство до тех пор, пока интервал не будет уменьшен до нуля, и тем самым исключая возможность досрочного завершения - помните, что примерно половина времени поиска будет произойдет с совпадающим значением на одну итерацию ниже предела.

Довольно просто сделать эту проблему еще хуже (например, как в 3 ), используя такой порядок, как

if a = b then action3
 else if a > b then action2
  else action1;

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

Некоторые языки, такие как Fortran, имеют трехстороннее сравнение, которое позволяет выполнить этот шаг с одним сравнением, которое ветвится на три разных раздела (см. Десятую строку Пример трехстороннего сравнения ) , Если ваш язык не поддерживает трехсторонний тест (большинство языков не поддерживают его), то лучше всего сделать два сравнения.

Я бы посоветовал бы вам проверить итеративную реализацию из той же статьи.

5 голосов
/ 05 октября 2009

Я попытался восстановить шаги оптимизации алгоритма двоичного поиска. Я начинаю с этой итеративной версии:

int binsearch_1( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  int found=0;
  while( size > 0 ){
    size_t w=size/2;
         if( p[w] <  key  ){ p+=w+1; size-=w+1; }
    else if( p[w] >  key  ){         size =w;   }
    else  /* p[w] == key */{ p+=w; found=1; break; }
  }
  *index=p-array; return found;
}

Исключение сравнений из цикла:

int binsearch_2( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 0 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else size =w;
  }
  *index=p-array; return p[0]==key;
}

Развертывание небольших размеров из петли:

int binsearch_3( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }
  if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
  *index=p-array; return p[0]==key;
}

Изменение порядка операторов if, перемещение особых случаев [size == pow (2, N) -1] в конец:

int binsearch_4( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }

  if( size==7 ){ if( p[4] <=  key ){ p+=4; size=3; } else size=3; }
  if( size==3 ){ if( p[2] <=  key ){ p+=2; size=1; } else size=1; }
  if( size==1 ){ if( p[1] <=  key ){ p+=1;         }              }
  *index=p-array; return p[0]==key;
}

Изменение операторов if на оператор switch:

int binsearch_5( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  while( size > 8 ){
    size_t w=size/2;
    if( p[w+1] <= key ){ p+=w+1; size-=w+1; } else  size =w;
  }
  if( size==8 ){ if( p[5] <=  key ){ p+=5; size=3; } else size=4; }
  if( size==6 ){ if( p[4] <=  key ){ p+=4; size=2; } else size=3; }
  if( size==5 ){ if( p[3] <=  key ){ p+=3; size=2; } else size=2; }
  if( size==4 ){ if( p[3] <=  key ){ p+=3; size=1; } else size=2; }
  if( size==2 ){ if( p[2] <=  key ){ p+=2; size=0; } else size=1; }

  switch(size){
    case 7: if( p[4] <= key ) p+=4;
    case 3: if( p[2] <= key ) p+=2;
    case 1: if( p[1] <= key ) p+=1;
  }
  *index=p-array; return p[0]==key;
}

Расширение оператора switch для обработки всех особых случаев:

int binsearch_6( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  switch( size ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1); 
#if SIZE_MAX == UINT64_MAX 
                                              C(63) C(62) C(61)
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif 
                                                          C(31)
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
    C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C 
      break;
    default:
      while( size > 0 ){
        size_t w=size/2;
        if( p[w] < key ){ p+=w+1; size-=w+1; } else size=w;
      }
  }
  *index=p-array; return p[0]==key;
}

Исключение обработки общего случая из кода: [w - наименьшее число: w == pow (2, N) -1; размер <= 2 * (ш + 1)] </p>

int binsearch_7( arr_t array[], size_t size, arr_t key, size_t *index ){
  if( !array || !size ) return 0;
  arr_t *p=array;
  size_t w=(size-1)>>1; w|=w>>1; w|=w>>2; w|=w>>4; w|=w>>8; w|=w>>16;
#if SIZE_MAX == UINT64_MAX
  w|=w>>32;
#endif
  if( p[w]<key ) p+=size-w-1;
  switch( w ){
#define C(n) case ((size_t)1<<n)-1: if( p[1<<(n-1)]<=key ) p+=1<<(n-1);
#if SIZE_MAX == UINT64_MAX
                                              C(63) C(62) C(61)
    C(60) C(59) C(58) C(57) C(56) C(55) C(54) C(53) C(52) C(51)
    C(50) C(49) C(48) C(47) C(46) C(45) C(44) C(43) C(42) C(41)
    C(40) C(39) C(38) C(37) C(36) C(35) C(34) C(33) C(32)
#endif
                                                          C(31)
    C(30) C(29) C(28) C(27) C(26) C(25) C(24) C(23) C(22) C(21)
    C(20) C(19) C(18) C(17) C(16) C(15) C(14) C(13) C(12) C(11)
    C(10) C( 9) C( 8) C( 7) C( 6) C( 5) C( 4) C( 3) C( 2) C( 1)
#undef C
  }
  *index=p-array; return p[0]==key;
}

Последний шаг, который я сделал, - это упрощение меток кейсов [с: '((size_t) 1 << n) -1' до: 'n'], но я обнаружил, что модифицированный код медленнее на моем старом ПК, чем предыдущая версия. </p>

4 голосов
/ 23 марта 2009

В размещенном вами коде вы можете удалить последнее сравнение. То есть, если key не меньше array[mid] или больше array[mid], то по определению оно равно. Таким образом, ваш код становится:

mid = left + (right-left)/2;
if (key < array[mid])
    return binSearch(array, key, left, mid-1);
else if (key > array[mid])
    return binSearch(array, key, mid+1, right);
else 
    return TRUE; // Found

Также обратите внимание, что я удалил последнюю строку. В вашем исходном коде невозможно выполнить return FALSE;. Я бы предположил, что у вас есть чек в начале вашего binSearch, который проверяет, есть ли left <= <code>right.

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

4 голосов
/ 23 марта 2009

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

Дайте мне знать, если вам нужно больше деталей.

2 голосов
/ 07 марта 2010
// Optimized Binary Search Implementation
int binsearch(int* data, int size, int val)
{
    int result = -1;
    int start, mid, end;
    start = 0;
    end = size - 1;
    mid = (start + end) >> 1;
    while (start <= end && data[mid] != val)
    {
        if (data[mid] > val)
            end = mid - 1;
        else
            start = mid + 1;
        mid = (start + end) >> 1;
    }
    if (val == data[mid])
        result = mid;
    return result;
}
2 голосов
/ 23 марта 2009

Для целых чисел это не имеет значения, не делайте этого.

Для более дорогих сравнений используйте -1, 0, 1 для <, =,> как в функции библиотеки C strcmp или Java's CompareTo ().

1 голос
/ 29 мая 2010

Вопрос во втором издании K & R.

While(low <= high && arr[mid]!=num)
{
    if(arr[mid] > num)
    {
       low = mid+1;
    }
    else
    {
       high = mid-1;
    }
    mid = (low+high)/2;
}

if(arr[mid] == num)
{
    printf("found the ugly number");
    return mid;
}
1 голос
/ 05 октября 2009

Ганеш М - Если ключ не существует в массиве, то ваша функция застрянет внутри бесконечного цикла. Он никогда не вернет FALSE.

Каков оптимальный способ найти точку вставки, если ключ не существует?

Условный «если каскад», учитывающий <, == и>, только вернет ИСТИНА или продолжит вычислять вечно.

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

Я знаю, что это замедлит поиск, но я хочу замедлить его на наименьшую сумму.

играть с log (N) / log (2) кажется хорошей идеей, но когда N не является степенью 2, все может пойти не так.

Возможно, мне следует выбрать массив с размером степени 2 и использовать простой цикл while?

ли проверка средней точки == к одной из границ увеличивает количество сравнений слишком сильно?

0 голосов
/ 08 марта 2019
using System;

namespace BinarySearchFast
{
    public class BinarySearchFast
    {
        // csharp version, assuming compiler removes the inner branch, there should be almost no branching impact    
        // if index not found, returns ~(index of element to insert sorted) at.
        public static int BinarySearchFast<T>(T[] array, T value) where T : IComparable<T>
        {
            if (array == null || array.Length == 0 || value == null)
            {
                return -1;
            }
            int start;
            int mid;
            int end;
            int cmp = -1;
            start = 0;
            end = array.Length - 1;
            mid = (start + end) / 2;
            while (start <= end && (cmp = array[mid].CompareTo(value)) != 0)
            {
                // I *think* any good compiler will optimize this to avoid the branch by using a lerp based on cmp > 0 for end and start
                // something like:
                // end = lerp(end, mid - 1, cmp > 0);
                // start = lerp(mid + 1, start, cmp > 0);
                // but if not, the lerp could be inserted instead for C/C++, C# does not allow easy conversion of bool to int outside of System.Convert or an if statement.
                if (cmp > 0)
                {
                    end = mid - 1;
                }
                else
                {
                    start = mid + 1;
                }
                mid = (start + end) >> 1;
            }
            // could also replace with return lerp(~(++mid), mid, (cmp == 0));
            return (cmp == 0 ? mid : ~(++mid));
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...