Быстрое среднее без деления

Question

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

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

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

Существует ли алгоритм с немного изменчивым значением, чтобы заменить mid = (low + high) / 2 чем-то намного более быстрым?

Редактировать: язык - C #, но эквивалентная битовая операция действительна на любом языке (хотя это может не иметь никакого преимущества в производительности), поэтому я оставил тег C # выключенным.

Answer 1

Вот средняя версия, которая не страдает от проблемы переполнения:

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}

Answer 2

int mid = (low + high) >>> 1;

Имейте в виду, что использование "(low + high) / 2" для вычислений средней точки не будет работать правильно , когда целочисленное переполнение становится проблемой.

Answer 3

Вы можете использовать битовое смещение, а также преодолеть возможную проблему переполнения:

low + ((high-low) >> 1)

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

Answer 4

Чтобы еще больше расширить ответ Нильса Ричард Шропепель изобрел это.

http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

ПУНКТ 23 (Schroeppel):

(A И B) + (A ИЛИ B) = A + B = (A XOR B) + 2 (A И B).

(A + B)/2 = ((A XOR B) + 2(A AND B))/2
          =  (A XOR B)/2  + (A AND B)
          =  (A XOR B)>>1 + (A AND B)


avg(x,y){return((x^y)>>1)+(x&y);}

(A AND B) + (A OR B) = A + B, поскольку A AND B дает сумму общих (между A и B) степеней двух, A OR B дает и те общие, и те, которые нет, следовательно:

(A AND B) + (A OR B) = 
   (sum of shared powers of two) + 
   ((sum of shared powers of two) + (sum of unshared powers of two)) = 
     (sum of shared powers of two) + 
     ((sum of shared powers of two) + (sum of powers of two of A only) + 
     (sum of powers of two of B only)) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B. 

A XOR B дает карту тех битов, которые отличаются между A и B. Следовательно,

A XOR B = (sum of powers of two of A only) + (sum of powers of two of B only). 

И, таким образом:

2(A AND B) + (A XOR B) = 
       ((sum of shared powers of two) + (sum of powers of two of A only)) + 
       ((sum of shared powers of two) + (sum of powers of two of B only)) 
= A + B.

Answer 5

Попробуйте низкий + ((высокий - низкий) / 2)). Это должно работать, потому что вы берете в среднем только два числа. Это уменьшит количество времени, которое занимает алгоритм, если список двоичного поиска достаточно велик, поскольку high - low намного меньше, чем high + low.

Answer 6

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

Я не могу вспомнить точные детали, но я помню, как слушал в лекции 6 из серии алгоритмов MIT на iTunes.