Хотелось бы написать про хак, который может помочь ускорить двоичный поиск на очень больших массивах.
Дело в том, что обычный двоичный поиск весьма неэффективен с точки зрения кэша: вначале, пока границы поиска далеко друг от друга, запросы к массиву будут далеки друг от друга, что породит много кэш-промахов.
Как с этим бороться? Очень просто. Пусть n -- размер массива. Разобьем массив на 
блоков длины . Образуем массив B из первых элементов блоков. Теперь, чтобы сделать двоичный поиск в исходном массиве, достаточно сначала поискать элемент в B, а потом в соответствующем отрезке длины в исходном массиве. Таким образом, количество промахов существенно уменьшится.
Абсолютно аналогичная конструкция возможна для любого числа уровней.
Для эксперимента я сравнил std::lower_bound и оптимизированную версию двоичного поиска (трехуровневую) на случайном массиве 32-битных целых чисел размера 227. Количество запросов равно 107. Машинка: Intel(R) Core(TM) i5 CPU M 430 @ 2.27GHz, 32k/256k/4m cache, 1066 MHz RAM. Система: GNU/Linux 2.6.35, g++ 4.4.5.
Результат:
- std::lower_bound -- 16.6 секунд
- оптимизированный поиск -- 6.6 секунд
========================
В программе была строка длиной 723 символа.
Хочу глянуть на динамику от 13 параметров :)
будет выделяться ровно на логарифм.вообще за корень, так что на задачах где чистый бинпоиск неприменимо.Для каждого числа вида i << 16 закешируем результат бинпоиска. После этого будем сразу проводить бинпоиск на соответствующем участке.
Имеется ввиду нечто вроде
const int cache_len_log = 16;
const int cache_len_log_add = 32 - cache_len_log;
const int cache_size = 1 << (cache_len_log);
vector<int> cache(cache_size + 1);
for (int i=0; i<cache_size; ++i)
cache[i] = static_cast<int>(std::lower_bound(data.begin(), data.end(), (i << cache_len_log_add) + 0x80000000) - data.begin());
cache[cache_size] = static_cast<int>(data.size());
//for each query
int pos = (static_cast<unsigned int> (query + 0x80000000) ) >> cache_len_log_add;
int l = cache[pos];
int r = cache[pos + 1];
//use lower_bound on [l;r)
Если да, то т.к. lower_bound монотонно, ответ l == r.
Если да, то: заметим, что x == (pos << cache_len_log_add) <= query <= ((pos + 1) << cache_len_log_add) == y, и cache[pos] == lower_bound(x) <= lower_bound(query) <= lower_bound(y) == cache[pos+1]