Comments 4
Ну, в сущности ответ был понятен еще после прочтения первых строк, Теория это хорошо и правильно, но реальное железо вносит свои коррективы.
Слов много, слова правильные, но нет никакой новизны. Все очевидно. Двоичный поиск по отсортированному массиву - трудно (скорее даже невозможно) придумать что-то быстрее. Но все это пригодно только для "статических" (в смысле один раз заполнил, отсортировал, 100500 раз используешь - никаких добавлений и удалений) массивов. Т.е. хорошо для справочников которые формируются один раз при инициализации и потом многократно используются.
Когда же данные динамичны (массив постоянно меняется) затраты на поддержание его в отсортированном состоянии почти наверняка будут кратно превышать выигрыш в скорости поиска. И тут уже надо искать другие алгоритмы - деревья, скиплисты и т.п. - те, что проигрывая в скорости поиска будут выигрывать в скорости вставки и удаления без нарушения сортировки. Что в среднем даст выигрыш в общей скорости работы.
Благодаря этому становятся эффективными запросы в диапазоне. Если нам нужны «все ключи от 100 до 200», то можно пропускать целые поддеревья, находящиеся вне этого диапазона.
В случае отсортированного массива мы находим 100 при помощи двоичного поиска, а затем выполняем линейное сканирование до 200. Если диапазон большой, это происходит медленнее.
Тут противоречие, тут как раз отсортированный массив отработает быстро и легко, потому что после того как мы нашли 100 нам нужно идти последовательно по массиву до 200, а это значит минимум промахов кэша и префетчинг отрабатывает хорошо.
Шаг 1: проверка среднего элемента [40] @ 0x1020 → ПРОМАХ кэша (100 тактов) → CPU получает линию кэша, содержащую [30][40][50][60]Шаг 2: проверка [60] @ 0x1030 → ПОПАДАНИЕ в кэш (1 такт) — уже находится в линии кэша!Шаг 3: проверка [70] @ 0x1038 → ПОПАДАНИЕ в кэш (1 такт) — всё ещё в кэшеВсего: ~102 такта, 1 промах кэша
И тут в примере ошибка. На третьем шаге где мы ищем 70, сказано что мы попадаем в кэш - судя по примеру мы не попадаем в него потому что в первом шаге где мы этот кеш загружали числа 70 нет.
Структуры данных на практике. Глава 9: Двоичные деревья поиска