Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Cache oblivious sorted arrays

                    1
0 1 2         =>   / \    => 1 0 2
                  0   2

                    3
                  /   \
0 1 2 3 4 5 6 => 1     5  => 3 1 5 0 2 4 6
                / \   / \
               0   2 4   6
Я тут "изобрёл" способ делать двоичный поиск в массиве так, чтобы не было полупустых строк кеша. Он как-то называется?

Общая идея что если у нас есть массив ключей, в котором надо делать двоичный поиск, и мы можем ускорить поиск, поместив один любой ключ в кеш проца - то какой ключ помещать? Очевидно что находящийся в середине массива, т.к. он будет фетчиться из памяти в 100% поисков.

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

Теперь представьте, что у нас кеш состоит из строк по 2 элемента. При доступе в середину массива в кеш попадёт не только середина, но и соседний ключ, который в дереве поиска находится на последнем уровне и который поэтому кешировать неоптимально, если только в кеш не поместится вообще всё.

В связи с этим я изобрёл порядок, при котором дерево поиска пакуется в массив не в порядке обхода в глубину, а в порядке обхода в ширину. В таком массиве по-прежнему можно делать двоичный поиск: начинаем не с середины, с начала. Ну и при обращении к началу в кеш попадает как раз первый ключ второго уровня.
Tags: programming, я знаю кунг-фу
Subscribe

Posts from This Journal “programming” Tag

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 52 comments

Posts from This Journal “programming” Tag