Структуры данных на практике. Глава 9: Двоичные деревья поиска

[vvbob]

Ну, в сущности ответ был понятен еще после прочтения первых строк, Теория это хорошо и правильно, но реальное железо вносит свои коррективы.

[SpiderEkb]

Слов много, слова правильные, но нет никакой новизны. Все очевидно. Двоичный поиск по отсортированному массиву - трудно (скорее даже невозможно) придумать что-то быстрее. Но все это пригодно только для "статических" (в смысле один раз заполнил, отсортировал, 100500 раз используешь - никаких добавлений и удалений) массивов. Т.е. хорошо для справочников которые формируются один раз при инициализации и потом многократно используются.

Когда же данные динамичны (массив постоянно меняется) затраты на поддержание его в отсортированном состоянии почти наверняка будут кратно превышать выигрыш в скорости поиска. И тут уже надо искать другие алгоритмы - деревья, скиплисты и т.п. - те, что проигрывая в скорости поиска будут выигрывать в скорости вставки и удаления без нарушения сортировки. Что в среднем даст выигрыш в общей скорости работы.

[Victor89]

Благодаря этому становятся эффективными запросы в диапазоне. Если нам нужны «все ключи от 100 до 200», то можно пропускать целые поддеревья, находящиеся вне этого диапазона.

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

Тут противоречие, тут как раз отсортированный массив отработает быстро и легко, потому что после того как мы нашли 100 нам нужно идти последовательно по массиву до 200, а это значит минимум промахов кэша и префетчинг отрабатывает хорошо.

[Victor89]

Шаг 1: проверка среднего элемента [40] @ 0x1020 → ПРОМАХ кэша (100 тактов) → CPU получает линию кэша, содержащую [30][40][50][60]Шаг 2: проверка [60] @ 0x1030 → ПОПАДАНИЕ в кэш (1 такт) — уже находится в линии кэша!Шаг 3: проверка [70] @ 0x1038 → ПОПАДАНИЕ в кэш (1 такт) — всё ещё в кэшеВсего: ~102 такта, 1 промах кэша

И тут в примере ошибка. На третьем шаге где мы ищем 70, сказано что мы попадаем в кэш - судя по примеру мы не попадаем в него потому что в первом шаге где мы этот кеш загружали числа 70 нет.

[Jijiki]

я заметил у вас 10-ая ссылка в вашей статье ведёт на edit - это редактирование статьи, а не в чтение.

у меня на расте например частички пока летят, перебирают для хвоста каметы текущий уровень, а уровень в bvh, в бвх браши выпуклые многогранники - обьемные, так вот получается на 1 кадр у меня ну положим 20 частиц на хвосте, там можно посчитать сколько кадром летит частица - снаряд до стены, кешгрнид показывает не то как у вас, и на массивах было намного хуже, но я билдил в --release + lto + level-optimisation, плюс сюда же добавляется коллизия игрока у меня на проверке точки, а не трассере было время я пока писал был массив брашев, тоже минус, так что, тут есть нюансы всё равно, ну да нужны айдишки, но бсп и бвх имеют смысл, как и точку пускать на сравнение с брашем так или трассировку делать, но у меня на уровне правда покачто всего ну 20 коробок, по каким-то я хожу, а какие-то из них стены.

еще есть грид как в майнкрафте например, там просто массив, вот походу ваш случай, и там только прыжки, и есть вставки и удаления, тоже можно было бы рассмотреть, ну я компилю этот случай с бесконечным миром тоже lto+lvl-optimisation--release. все соседние чанки у меня, например в 4к страницах (массив 4килобайта) - 108кб - это 3х3х3 чанков (16х16х16 х1 чанк блоков).