Ускорить двоичный поиск на 60 процентов? Легко!

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

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

Как с этим бороться? Очень просто. Пусть n -- размер массива. Разобьем массив на $\text{[math]}$ блоков длины $\text{[math]}$ . Образуем массив B из первых элементов блоков. Теперь, чтобы сделать двоичный поиск в исходном массиве, достаточно сначала поискать элемент в B, а потом в соответствующем отрезке длины $\text{[math]}$ в исходном массиве. Таким образом, количество промахов существенно уменьшится.

Абсолютно аналогичная конструкция возможна для любого числа уровней.

Для эксперимента я сравнил std::lower_bound и оптимизированную версию двоичного поиска (трехуровневую) на случайном массиве 32-битных целых чисел размера 2²⁷. Количество запросов равно 10⁷. Машинка: 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 секунд

Код можно посмотреть тут.

Комментарии (35)

Написать комментарий?

Scalar

14 лет назад, # |

Интересно было бы сравнить также с бинпоиском, написанным вручную.

→ Ответить

ilyaraz

14 лет назад, # ^ |

Практика показывает, что у lower_bound не выиграешь. STL писали не индусы, к счастью.

Connector

А Вы покажите результаты бинпоиска написанного вручную.

ilyakor

Смотря как написанного ;) Ходят слухи, что на новом g++ он сильно проигрывает lower_bound'у.

yeputons

Это смотря что. deque<> и queue<> писали как раз индусы, потому как 10⁵ деков из одного int'а жрут 70 метров памяти.

maksay

Хм...удвительно. Я уже давно пишу бфс исключительно с queue, в том числе на графах размера 100k, никогда МЛов не возникало. Везло, наверное...

Один дек работает хорошо. А когда деков сто тысяч, начинаются проблемы.

=======================

Пардон, невнимательно прочитал. Да, выходит что-то около 150 байт сторонней информации. Порядочно.

Alchemist

Скорее всего, это не сторонняя информация, а зарезервированная под новые элементы память.

Я всегда полагал, что память резервируется из расчета x2-x3 к использованному размеру ( если не использована функция reserve). Разве нет?

Это в типичных реализациях вектора (а тут дек), да и то нигде не гарантируется, если не ошибаюсь.

2222	14 лет назад, # ^ \| +5 А когда деков сто тысяч?? Мне, к примеру, всегда хватало одного дека... → Ответить

Была какая-то задача у нас на тренировке. Там были какие-то объекты и требовалось по очереди брать объекты разных типов.

daftcoder

Мне почему-то вспомнилась история, как один человек в летней школе (не ЛКШ) пытался отладить программу с 40 вложенными циклами for...

========================

FedyuninV

Вспомнилась первая задача параллели В в ЛКШ июле, деки на 5 мегабайтах....

Мне сразу вспомнилась всесибирская олимпиада, на которой Дима Егоров получил ОК за 13-мерную динамику.
В программе была строка длиной 723 символа.

zendo

кинь линк на задачу, пожалуйста.
Хочу глянуть на динамику от 13 параметров :)

JKeeJ1e30

Плохо только что придется использовать память(ну куда же ускорение по времени без увеличения памяти?). Хотя, конечно, с таким поиском можно будет что-нибудь и попихать:)

Памяти там используется очень мало. Для двухуровневой конструкции $\text{[math]}$ , для трехуровневой конструкции -- O(n^2 / 3), и т. д.

← Rev. 2 →

Это-то понятно:) Хотя, с другой стороны, если мы будем пытаться решить задачу чисто за логарифм, то и памяти ~~будет выделяться ровно на логарифм.~~ вообще за корень, так что на задачах где чистый бинпоиск неприменимо.

Ну, обычно все-таки у нас сначала предобработка массива, а потом куча запросов. Для такого применения этот подход вполне неплох.

Интересный вопрос, куда разумно выкладывать код, когда есть несколько файлов. Всякие pastebin'ы в этом случае не подходят, публичный репозиторий ради такого дела кажется overkill'ом, а вариант "выложить на narod.ru", применённый в этом посте, ещё хуже, т.к. там капча и приставания от яндекс-бара.

skywalker

+16

gist.github.com

Подсветка там, конечно, так себе.

NKolotey

А не проще ли было запихать данные в B-дерево и по нему искать?

Это более-менее и есть статическая версия B-дерева.

freopen

+10

Что вы имеете в виду, используя слово "проще"?

Справедливое замечание. Оказалось, что не проще, равнозначно по сложности реализации, просто пилить на фрагменты нужной длины как-то привычнее чтоли.

I_love_natalia

Интересно, попробуйте еще один специфический вариант для 32-битных чисел:
Для каждого числа вида 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)

Но что, если мы хотим найти наименьшее число не меньшее данного? Что делать, если соответствующая корзинка пуста? Видимо, все-таки придется два поиска делать.

Я правильно понимаю, что вопрос что делать, если l == r?
Если да, то т.к. lower_bound монотонно, ответ l == r.

l == r, а мы хотим найти наименьшее число, которое не меньше заданного. Придется как-то искать наименьшую непустую корзинку.

Я же еще не совсем сплю, номер наименьшего числа, не меньшего заданного - lower_bound?

Если да, то: заметим, что 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]

Блог пользователя ilyaraz