Участник:RandomAtHome/Блочная cортировка - История изменений

RandomAtHome: Доделана страница в вики для задания

2019-12-04T03:43:21Z

Доделана страница в вики для задания

← Предыдущая версия		Версия от 03:43, 4 декабря 2019
Строка 49:		Строка 49:

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
			Вычислительное ядро, в данном случае, целиком совпадает с математическим описанием алгоритма. Большая часть работы уходит на внутренние сортировки в каждом блоке, при условии что общее время работы равно, по сути, самому худшему времени сортировки среди блоков, к которому прибавляется относительно стабильное время рассылки и сбора отсортированных данных.

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

	=== Схема реализации последовательного алгоритма ===		=== Схема реализации последовательного алгоритма ===
			Опишем схему последовательного алгоритма.
			Пусть у нас есть N элементов, p массивов-блоков и заранее известная функция распределения f, которая определяет в какой блок надо отправить элемент.

			1) Подготовим p массивов, по которым мы будем распределять элементы

			2) Пройдем по всем N элементам, распределяя их по блокам с помощью функции f

			3) Пройдем последовательно по всем блокам, отсортировывая их некоторой внутренней сортировкой

			4) Соединим все блоки назад в один массив

			Таким образом, мы последовательно отсортировали последовательность из N элементов, используя блочную сортировку.

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
			К сожалению последовательная сложность алгоритма может быть оценена только асимптотически, так как реальная сложность операций зависит от типа входных данных и от их распределения. При достаточно хорошем случае и правильно подобранном числе вычислительных блоков сложность может быть асимптотически равна <math>O(n)</math>, за счет малого числа элементов внутри блока для сортировки, однако есть шанс, что эта асимптотика деградирует асимптотики внутренней сортировки, например <math>O(n^2)</math> или <math>O(nlog(n))</math> - например в частном случае, если все элементы попали в один блок.

	=== Информационный граф ===		=== Информационный граф ===
			За неимением изображения графа, ограничимся его словесным описанием.

			Информационным графом здесь будет трехярусный граф, у которого на 1м ярусе и на 3м по одной вершине, вершина с 1ого яруса соединена со всеми вершинами со 2го, все вершины соединены с вершиной 3его.

			Вершина 1го яруса представляет собой последовательную часть с предобработкой и распределением данных, 2ой ярус это независимая сортировка блоков, 3ий ярус это сбор всех результатов сортировок блоков.

			Таким образом становится явно видно, что в алгоритме хорошо разделяется информация.

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
			Как было видно из информационного графа, есть три этапа данного алгоритма - распределение данных, внутренние сортировки и сбор данных. Если первый и последний шаги требует все тех же N действий, то есть проход по всем исходным данным, то второй этап отлично параллелизуется - в предельном случае, если каждый блок будет соответствовать одному значению элемента, то само выполнение распределения по блокам будет являть собой, по сути, полную сортировку, так как массив из одинаковых элементов даже не нужно сортировать. Большую роль для параллелизма сортировок играет, опять же, полная независимость данных каждого из блоков.

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

			Результатом работы алгоритма является отсортированный набор данных.

	=== Свойства алгоритма ===		=== Свойства алгоритма ===
			Алгоритм содержит последовательную часть в самом начале, связанную с распределением данных.

			Устойчивость алгоритма в смысле устойчивости сортировки зависит от устойчивости внутренней сортировки - при передаче данных их относительный порядок сохраняется. При этом алгоритм детерминирован.

			Вычислительную мощность можно оценить так - на передаваемый туда и обратно массив из N элементов приходится порядка <math>N*log(N)</math> операций, делаемых внутренней сортировкой. Так данные передаются назад в том же объеме, можно оценить что вычислительная мощность ~= <math>log(N)/2</math> в среднем. В зависимости от сортировки, если у нее асимптотика <math>O(N^2)</math>, то вычислительная мощность равна <math>N/2</math>. То есть, параллелизация может дать большой выигрыш по сравнению с последовательной версией.

	== Программная реализация алгоритма ==		== Программная реализация алгоритма ==
Строка 73:		Строка 108:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			На рис.1 продемонстрирована масштабируемость алгоритма, полученная опытным путем. Шкала по числу процессов логарифмирована, то есть реально использованное число процессов равно <math>2^s</math>. Стоит отметить, что с ростом числа процессов p время на сортировку уменьшается с асимптотикой <math>p^{-1}</math>, или же со скоростью <math>e^-s</math>, где <math>s = ln(p)</math>. Это явно видно на рис.2. Графики функции оценки ниже фактически получившихся значений времени, так как не учитывается overhead и затраты на пересылку и сбор данных, а лишь оценивается скорость падения времени. Зная асимптотику от числа процессов, легко оценить, с какого момента добавление новых процессов будет не столь эффективно. Так, по рис.2 видно что переход от 8 к 16 процессам (от 3ей степени к 4ой) и далее уже далеко не столь эффективны.

			[[File:Масштабируемость блочной сортировки.png\|thumb\|center\|700px\|Рис.1 Масштабируемость блочной сортировки]]
			[[File:Срез по числу элементов для блочной сортировки.png\|thumb\|center\|700px\|Рис.2 Cрез для числа элементов равного <math>10^{8}</math>]]
	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Строка 79:		Строка 117:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			Реализаций этого алгоритма и его подвидов не так много, так как они требуют дополнительной памяти и достаточно чувствительны к "хорошести" входных данных.
			Смешанную с блочной сортировкой реализацию имеет SpreadSort, использующийся в библиотеке Boost для C++. (https://www.boost.org/doc/libs/1_58_0/libs/sort/doc/html/index.html)
	== Литература ==		== Литература ==

	<references />		<references />

RandomAtHome: Добавлено авторство

2019-10-24T15:16:02Z

Добавлено авторство

← Предыдущая версия		Версия от 15:16, 24 октября 2019
Строка 1:		Строка 1:
	~~Требуемые для зачёта пункты описания: 1.1~~-~~1.9, 2.4, 2.7, 3~~.		Автор - студент 401 группы факультета ВМК Чухарев Фёдор Сергеевич.

	Общая схема описания алгоритмов имеет следующий вид:		Общая схема описания алгоритмов имеет следующий вид:

RandomAtHome: Закончен математиский параграф 1.2

2019-10-24T15:12:13Z

Закончен математиский параграф 1.2

@@ Строка 4: / Строка 4: @@
 == Свойства и структура алгоритмов ==
 === Общее описание алгоритма ===
@@ Строка 20: / Строка 19: @@
 === Математическое описание алгоритма ===
 === Вычислительное ядро алгоритма ===
@@ Строка 54: / Строка 81: @@
 == Литература ==
 <references />

RandomAtHome: Дополнение про сортировку вставками

2019-10-24T14:32:34Z

Дополнение про сортировку вставками

← Предыдущая версия		Версия от 14:32, 24 октября 2019
Строка 15:		Строка 15:
	Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке <math>[0, 1)</math>. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.		Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке <math>[0, 1)</math>. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.

			Еще стоит отметить, что в алгоритме в качестве внутренней сортировки часто используется сортировка вставками из-за некоторых ее свойств:
			* Сортировка вставками может работать по мере поступления данных, в отличие от той же сортировки Хоара или сортировки слиянием
			* Из-за константных множителей и членов более низкого порядка сортировка вставками может выполняться для небольших входных данных быстрее, чем другие сортировки с более низким порядком роста<ref>Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 3-е изд. — М.: Вильямс, 2013. — С. 51.</ref>

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
	~~Дадим оценку~~

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

RandomAtHome: Сделан 1.1

2019-10-24T13:56:49Z

Сделан 1.1

← Предыдущая версия		Версия от 13:56, 24 октября 2019
Строка 7:		Строка 7:

	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===
	~~В данном разделе представляется самый первый вариант описания тех задач~~ (~~или классов задач~~), ~~для решения которых предназначен алгоритм. В описании поясняются особенности как алгоритма~~, так ~~и объектов~~, ~~с которыми он работает~~. ~~Если описание соответствует целому классу схожих по структуре алгоритмов~~, либо же ~~посвящено описанию отдельного представителя некоторого класса~~, ~~то это здесь указывается явно~~. ~~Описываются базовые математические свойства~~ и ~~структура~~ входных данных. ~~При необходимости~~, ~~в описании могут присутствовать формулы~~, а также ~~даваться ссылки~~ на ~~описания других используемых алгоритмов~~. ~~Данное описание должно быть достаточным~~ для ~~однозначного понимания сути решаемой задачи~~.		Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо любой другой сортировкой. Затем элементы помещаются обратно в массив. Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для большинства других сортировок - например сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой и т.д. В данном случае, дополнительные знания о данных нужны для того, чтобы правильно составить функцию распределяющую элементы по блокам, чтобы количество элементов в каждом блоке было примерно одинаковым.

			Особенностью блочной сортировки является то, что она может обладать линейным временем исполнения на удачных входных данных <ref name="ref1">Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234</ref>, а также очень сильно деградировать на неудачных, в зависимости от алгоритма использующегося внутри блока сортировки. Например, в случае если блок сортируется с помощью сортировки вставками, то сложность становится равной <math>O(n^2)</math>.

			Другим интересным примером является случай если число блоков <math>n = 2</math> и используется рекурсивная блочная сортировка - тогда алгоритм, по сути, становится эквивалентен сортировке Хоара.

			Лучше всего алгоритм работает, когда для входных данных удается построить функцию, равномерно распределяющую их по блокам. Хороший пример - набор чисел с фиксированной точкой равномерно распределенный на отрезке <math>[0, 1)</math>. Иными словами, сортировка отлично подходит для случаев когда данные случайны и равномерно распределены по диапазону с известными границах.

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

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===

RandomAtHome: Удалено содержание остальных секций, оставлены только те, которые будут заполнены

2019-10-24T13:20:45Z

Удалено содержание остальных секций, оставлены только те, которые будут заполнены

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

RandomAtHome: Скопирован шаблон описания алгоритма

2019-10-24T12:58:30Z

Скопирован шаблон описания алгоритма

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