Двоичный поиск - История изменений

ASA в 13:45, 18 июля 2022

2022-07-18T13:45:46Z

← Предыдущая версия		Версия от 13:45, 18 июля 2022
Строка 143:		Строка 143:

	Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.		Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.

	~~=== Локальность данных и вычислений ===~~
	[[Глоссарий#Пространственная локальность\|Пространственная локальность]] достаточно плохая — начальные обращения в память гарантированно далеки друг от друга. Однако расстояние с номером итерации экспоненциально уменьшается и в конце есть надежда на использование преимуществ локальности обращений.

	[[Глоссарий#Временная локальность\|Временная локальность]] ещё хуже — один и тот же элемент массива никогда не требуется дважды.

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

	~~===== Структура обращений в память и качественная оценка локальности =====~~
	~~[[Файл:binary search memory access.png\|500px\|Рисунок 3. Реализация двоичного поиска. Общий профиль обращений в память.\|thumb\|center]]~~
	На рис. 3 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.

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

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

	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
Строка 164:		Строка 149:
	Однако при этом потребуется предусмотреть обмен результатами сравнения своей точки деления на каждом процессоре для определения искомого интервала для следующей итерации. Это потребует минимум одной коллективной операции обмена, что ставит под сомнение эффективность распараллеливания.		Однако при этом потребуется предусмотреть обмен результатами сравнения своей точки деления на каждом процессоре для определения искомого интервала для следующей итерации. Это потребует минимум одной коллективной операции обмена, что ставит под сомнение эффективность распараллеливания.

	=== ~~Масштабируемость алгоритма и его реализации ===~~		=== Результаты прогонов ===

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

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

	~~=== Динамические характеристики и эффективность реализации алгоритма~~ ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	Использовать алгоритм в любой реализации для архитектур с разделённой памятью смысла не имеет — из-за нелокального доступа к исходным данным и малого количества вычислительных операций даже в параллельной модификации выигрыш будет съедаться коммуникациями.		Использовать алгоритм в любой реализации для архитектур с разделённой памятью смысла не имеет — из-за нелокального доступа к исходным данным и малого количества вычислительных операций даже в параллельной модификации выигрыш будет съедаться коммуникациями.
Строка 178:		Строка 157:
	# Статическое создание нитей один раз в начале работы программы.		# Статическое создание нитей один раз в начале работы программы.
	# Выигрыш будет получен только в результате многократного поиска в этом массиве (по общему правилу: число операций внутри параллельной секции должно быть не меньше 1000, чтобы получить ускорение от параллельного вычисления. Это соответствует, например, ~30 поискам в массиве из миллиарда элементов).		# Выигрыш будет получен только в результате многократного поиска в этом массиве (по общему правилу: число операций внутри параллельной секции должно быть не меньше 1000, чтобы получить ускорение от параллельного вычисления. Это соответствует, например, ~30 поискам в массиве из миллиарда элементов).

	~~=== Существующие реализации алгоритма ===~~
	# В стандартной библиотеке языка C есть функция <code>bsearch()</code>, которая обычно реализована с помощью бинарного поиска (однако стандарт не гарантирует этого)<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html «bsearch — binary search a sorted table».] The Open Group Base Specifications (7th ed.). The Open Group. 2013</ref>
	# Встроенные в C++ функции: <code>std::lower_bound</code> находит первое вхождение <math>A</math>, <code>std::upper_bound</code> возвращает индекс элемента за всеми <math>A</math>. Есть также <code>std::binary_search()</code> и <code>std::equal_range()</code>.<ref>Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2. § 32.6.1 («Binary Search»)</ref>
	# В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
	# Microsoft’s .NET Framework 2.0 предлагает статические функции-дженерики двоичного поиска в своей коллекции базовых классов. Например, метод класса System.Array’s <code>BinarySearch<T>(T[] array, T value)</code>.<ref>[https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx «List<T>.BinarySearch Method (T)»]. Microsoft Developer Network.</ref>
	# В Python есть модуль <code>bisect</code><ref>[https://docs.python.org/2/library/bisect.html#module-bisect «8.5. bisect — Array bisection algorithm»]. The Python Standard Library. Python Software Foundation</ref>

	== См. также ==		== См. также ==
Строка 206:		Строка 178:

	== Ссылки ==		== Ссылки ==
	* [[ru-wikipedia:Двоичный_поиск\|Метод двоичного поиска]] в Википедии		* [[ru-wikipedia:Двоичный_поиск\|Метод двоичного поиска]] в Википедии.
	* [http://algolist.manual.ru/search/bin_search.php Алгоритм] в библиотеке алгоритмов Algolist.		* [http://algolist.manual.ru/search/bin_search.php Алгоритм] в библиотеке алгоритмов Algolist.
	* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике		* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике.

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

ASA в 13:18, 14 марта 2018

2018-03-14T13:18:45Z

← Предыдущая версия		Версия от 13:18, 14 марта 2018
Строка 7:		Строка 7:
	\| output_data = индекc элемента		\| output_data = индекc элемента
	}}		}}

	Основные авторы описания: [[User:AntonChupin\|А. В. Чупин]].		Основные авторы описания: [[User:AntonChupin\|А. В. Чупин]].

Строка 209:		Строка 210:
	* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике		* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике

	[[Категория:~~Начатые статьи~~]]		[[Категория:Статьи в работе]]
	[[Категория:Алгоритмы поиска]]		[[Категория:Алгоритмы поиска]]
	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]

			[[en:Binary search: Finding the position of a target value within a sorted array]]

ASA в 13:16, 14 марта 2018

2018-03-14T13:16:19Z

← Предыдущая версия		Версия от 13:16, 14 марта 2018
Строка 1:		Строка 1:
	~~{{level-a}}~~

	{{algorithm		{{algorithm
	\| name = Бинарный поиск		\| name = Бинарный поиск

ASA в 14:28, 6 марта 2018

2018-03-06T14:28:49Z

← Предыдущая версия		Версия от 14:28, 6 марта 2018
Строка 1:		Строка 1:
			{{level-a}}

	{{algorithm		{{algorithm
	\| name = Бинарный поиск		\| name = Бинарный поиск

AntonChupin: /* Литература */

2016-07-08T13:07:09Z

Литература

← Предыдущая версия		Версия от 13:07, 8 июля 2016
Строка 191:		Строка 191:

	== Литература ==		== Литература ==
	~~{{примечания}}~~		<references />
	* Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180—183. — ISBN 5-8459-0987-2.		* Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180—183. — ISBN 5-8459-0987-2.
	* Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.		* Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.

AntonChupin: викификация

2016-07-08T13:05:56Z

викификация

Внесённые изменения

AntonChupin: /* Программная реализация алгоритма */

2016-07-08T12:48:34Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 12:48, 8 июля 2016
Строка 107:		Строка 107:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	Возможная простейшая реализация алгоритма на языке C:		Возможная простейшая реализация алгоритма на языке C:
	<source ~~language~~="C">		<source lang="C">
	int binary_find(int n, int *x, long A)		int binary_find(int n, int *x, long A)
	{		{

AntonChupin в 12:39, 8 июля 2016

2016-07-08T12:39:24Z

← Предыдущая версия		Версия от 12:39, 8 июля 2016
Строка 208:		Строка 208:

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]
			[[Категория:Алгоритмы поиска]]
			[[Категория:Алгоритмы с низким уровнем параллелизма]]

AntonChupin: /* Программная реализация алгоритма */

2016-07-08T10:30:00Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 10:30, 8 июля 2016
Строка 107:		Строка 107:
	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
	Возможная простейшая реализация алгоритма на языке C:		Возможная простейшая реализация алгоритма на языке C:
	<~~pre~~>		<source language="C">
	int binary_find(int n, int *x, long A)		int binary_find(int n, int *x, long A)
	{		{
Строка 121:		Строка 121:
	}		}
	}		}
	</~~pre~~>		</source>

	Здесь ряд индексов <math>l_k, m_k, r_k</math> из [[#Схема реализации последовательного алгоритма\|математической схемы алгоритма]] превращён в одну переменную, поскольку требуются только последние значения этих рядов.		Здесь ряд индексов <math>l_k, m_k, r_k</math> из [[#Схема реализации последовательного алгоритма\|математической схемы алгоритма]] превращён в одну переменную, поскольку требуются только последние значения этих рядов.

AntonChupin: /* Программная реализация алгоритма */

2016-07-08T10:29:33Z

Программная реализация алгоритма

← Предыдущая версия		Версия от 10:29, 8 июля 2016
Строка 122:		Строка 122:
	}		}
	</pre>		</pre>

			Здесь ряд индексов <math>l_k, m_k, r_k</math> из [[#Схема реализации последовательного алгоритма\|математической схемы алгоритма]] превращён в одну переменную, поскольку требуются только последние значения этих рядов.

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===