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

Автор ilyaraz, 13 лет назад, По-русски

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

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

Как с этим бороться? Очень просто. Пусть 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 секунд
Код можно посмотреть тут.
  • Проголосовать: нравится
  • +83
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно было бы сравнить также с бинпоиском, написанным вручную.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Практика показывает, что у lower_bound не выиграешь. STL писали не индусы, к счастью.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      А Вы покажите результаты бинпоиска написанного вручную.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Смотря как написанного ;) Ходят слухи, что на новом g++ он сильно проигрывает lower_bound'у.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это смотря что. deque<> и queue<> писали как раз индусы, потому как 105 деков из одного int'а жрут 70 метров памяти.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хм...удвительно. Я уже давно пишу бфс исключительно с queue, в том числе на графах размера 100k, никогда МЛов не возникало. Везло, наверное...
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Один дек работает хорошо. А когда деков сто тысяч, начинаются проблемы.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            =======================
            Пардон, невнимательно прочитал. Да, выходит что-то около 150 байт сторонней информации. Порядочно.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Скорее всего, это не сторонняя информация, а зарезервированная под новые элементы память.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Я всегда полагал, что память резервируется из расчета x2-x3 к использованному размеру ( если не использована функция reserve). Разве нет?
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Это в типичных реализациях вектора (а тут дек), да и то нигде не гарантируется, если не ошибаюсь.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            А когда деков сто тысяч?? 
            Мне, к примеру, всегда хватало одного дека...
            • 13 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Была какая-то задача у нас на тренировке. Там были какие-то объекты и требовалось по очереди брать объекты разных типов.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +2 Проголосовать: не нравится
                Мне почему-то вспомнилась история, как один человек в летней школе (не ЛКШ) пытался отладить программу с 40 вложенными циклами for...

                ========================
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится
                  Вспомнилась первая задача параллели В в ЛКШ июле, деки на 5 мегабайтах....
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится
                  Мне сразу вспомнилась всесибирская олимпиада, на которой Дима Егоров получил ОК за 13-мерную динамику.
                  В программе была строка длиной 723 символа.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    кинь линк на задачу, пожалуйста.
                    Хочу глянуть на динамику от 13 параметров :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Плохо только что придется использовать память(ну куда же ускорение по времени без увеличения памяти?). Хотя, конечно, с таким поиском можно будет что-нибудь и попихать:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Памяти там используется очень мало. Для двухуровневой конструкции , для трехуровневой конструкции -- O(n2 / 3), и т. д.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Это-то понятно:) Хотя, с другой стороны, если мы будем пытаться решить задачу чисто за логарифм, то и памяти будет выделяться ровно на логарифм. вообще за корень, так что на задачах где чистый бинпоиск неприменимо. 
      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        Ну, обычно все-таки у нас сначала предобработка массива, а потом куча запросов. Для такого применения этот подход вполне неплох.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересный вопрос, куда разумно выкладывать код, когда есть несколько файлов. Всякие pastebin'ы в этом случае не подходят, публичный репозиторий ради такого дела кажется overkill'ом, а вариант "выложить на narod.ru", применённый в этом посте, ещё хуже, т.к. там капча и приставания от яндекс-бара.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А не проще ли было запихать данные в B-дерево и по нему искать?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это более-менее и есть статическая версия B-дерева.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Что вы имеете в виду, используя слово "проще"?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Справедливое замечание. Оказалось, что не проще, равнозначно по сложности реализации, просто пилить на фрагменты нужной длины как-то привычнее чтоли.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, попробуйте еще один специфический вариант для 32-битных чисел:
Для каждого числа вида i << 16 закешируем результат бинпоиска. После этого будем сразу проводить бинпоиск на соответствующем участке.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Думаю, что для случайных тестов это даст такой же результат, как и предлагаемая двухуровневая схема, а для произвольных тестов может работать даже хуже (если все плохо распределится).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Для произвольных тестов - да, хуже. Для случайных выглядит лучше, т.к. это будет двухуровневая схема, только с одним бинпоиском.

      Имеется ввиду нечто вроде

      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)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Но что, если мы хотим найти наименьшее число не меньшее данного? Что делать, если соответствующая корзинка пуста? Видимо, все-таки придется два поиска делать.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Я правильно понимаю, что вопрос что делать, если l == r?
          Если да, то т.к. lower_bound монотонно, ответ l == r.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            l == r, а мы хотим найти наименьшее число, которое не меньше заданного. Придется как-то искать наименьшую непустую корзинку.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Я же еще не совсем сплю, номер наименьшего числа, не меньшего заданного - 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]