https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?action=history&feed=atom&title=Binary_search%2C_locality 2026-10-22T18:04:59Z История изменений этой страницы в вики MediaWiki 1.43.5 https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Binary_search,_locality&diff=29163&oldid=prev 2022-07-18T13:22:14Z

<p>Новая страница: «{{level-i}} Основные авторы описания: <a href="/ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:AntonChupin" title="Участник:AntonChupin">А. В. Чупин</a>. = Ссылки = = Локальность данных и...»</p> <p><b>Новая страница</b></p><div>{{level-i}}<br /> <br /> Основные авторы описания: [[User:AntonChupin|А. В. Чупин]].<br /> <br /> = Ссылки =<br /> <br /> = Локальность данных и вычислений =<br /> <br /> [[Глоссарий#Пространственная локальность|Пространственная локальность]] достаточно плохая — начальные обращения в память гарантированно далеки друг от друга. Однако расстояние с номером итерации экспоненциально уменьшается и в конце есть надежда на использование преимуществ локальности обращений.<br /> <br /> [[Глоссарий#Временная локальность|Временная локальность]] ещё хуже — один и тот же элемент массива никогда не требуется дважды.<br /> <br /> == Локальность реализации алгоритма ==<br /> === Структура обращений в память и качественная оценка локальности ===<br /> <br /> [[Файл:binary search memory access.png|500px|Рисунок 1. Реализация двоичного поиска. Общий профиль обращений в память.|thumb|center]]<br /> На рис. 1 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.<br /> <br /> Видно, что на каждой итерации используется одна ячейка памяти, при этом адреса располагаются достаточно хаотично. Пространственная локальность от очень плохой постепенно улучшается до идеальной, когда идут обращения только в близкие ячейки памяти. Данные из массива никогда не используются повторно, поэтому временная локальность плохая.<br /> <br /> === Количественная оценка локальности ===<br /> = Масштабируемость алгоритма и его реализации =<br /> == Масштабируемость алгоритма ==<br /> == Масштабируемость реализации алгоритма ==<br /> = Динамические характеристики и эффективность реализации алгоритма =<br /> = Результаты прогонов =<br /> <br /> [[Категория:Статьи в работе]]<br /> <br /> [[En:Binary search, locality]]</div>

ASA