Структуры данных на практике. Глава 10: B-деревья и деревья, эффективно использующие кэш

[AVaTar123]

Действительно двоичный поиск в отсортировАнном массиве

int find_key(btree_node_t *node, int key) {
    // Двоичный поиск в отсортировнном массиве (удобный для кэша!)
    int left = 0, right = node->num_keys - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (node->keys[mid] == key) return mid;
        if (key < node->keys[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;  // Не найдено
}

Читаем далее в другом месте

...
        // Двоичный поиск в узле (удобный для кэша)
        int i = 0;
        while (i < node->num_keys && key > node->keys[i]) {
            i++;
        }
...

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

[zzzzzzerg]

Идея в том, что "последовательный поиск в отсортированном массиве" идет по значениям "двоичного дерева" для определенного уровня. Поэтому это можно в данном контексте назвать двоичным поиском.

В статье выше есть пример

                [40|80]
               /   |   \
         [10|20] [50|60] [90|100]

Вот для этого примера последовательный поиск идет сначала для значений 40, 80. Потом на уровень ниже и т.д.

[AVaTar123]

Всё равно комментарий некорректный, и его следовало бы изменить или переместить в другое место.

[aamonster]

Любопытно ещё, почему в рассматриваемой задаче не подошли хэш-мапы (в идеале так же, как вывод этой статьи – с границами применимости).

[XViivi]

не знаю как в конкретном случае, но всё же у упорядоченных ассоциативных массивов область применения время от времени да нередко находится, разве не так?

[tenzink]

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

Был опыт, когда замена одной хеш-мапы на сортированный вектор пар с бинарным поиском экономило на уровне всей очень тяжёлой операции порядка 25% CPU + 30% RAM. Подозреваю, что B-дерево в том случае помогло бы ещё больше.

[aamonster]

Почему и говорю – с границами применимости. Делимся опытом.

[Mike-M]

Сдается мне, этот цикл статей станет призером Технотекста )

[spovst]

Извините, случайно вам минус поставил.

[Mike-M]

Ничего страшного, со всеми бывает. Я в таких случаях компенсирую плюсом в карму ;-)