Уровень реализации

Binary search, locality

Материал из Алговики
Версия от 16:22, 18 июля 2022; ASA (обсуждение | вклад) (Новая страница: «{{level-i}} Основные авторы описания: А. В. Чупин. = Ссылки = = Локальность данных и...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску


Основные авторы описания: А. В. Чупин.

1 Ссылки

2 Локальность данных и вычислений

Пространственная локальность достаточно плохая — начальные обращения в память гарантированно далеки друг от друга. Однако расстояние с номером итерации экспоненциально уменьшается и в конце есть надежда на использование преимуществ локальности обращений.

Временная локальность ещё хуже — один и тот же элемент массива никогда не требуется дважды.

2.1 Локальность реализации алгоритма

2.1.1 Структура обращений в память и качественная оценка локальности

Рисунок 1. Реализация двоичного поиска. Общий профиль обращений в память.

На рис. 1 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.

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

2.1.2 Количественная оценка локальности

3 Масштабируемость алгоритма и его реализации

3.1 Масштабируемость алгоритма

3.2 Масштабируемость реализации алгоритма

4 Динамические характеристики и эффективность реализации алгоритма

5 Результаты прогонов