Примеры различных сортировок массивов с использованием принципа параллелизма

Введение в асинхронные задачи

Использование класса Task

С появлением версии .NET Framework 4.0 разработчики получили новую библиотеку для параллельного программирования - TPL и в частности - класс Task. Данный класс позволяет в значительной степени упростить написание параллельного кода, без необходимости работы, непосредственно с потоками или пулом потоков. От класса Thread класс Task отличается тем, что он является абстракцией, представляющей асинхронную операцию, а в классеThread инкапсулируется поток исполнения.

Сами задачи создаются в виде объектов класса Task и создавать эти задачи можно различными способами:

· С использованием делегата Action и именного метода;

· С использованием анонимного делегата;

· С использованием лямбда-выражения и именного метода;

· С использованием лямбда-выражения и анонимного метода.

Для создания объектов класса Task используется следующий конструктор:

public Task(Action действие)

где действие обозначает точку входа в код, представляющий задачу, тогда как Action - делегат, определенный в пространстве имен System. Сама же форма делегата Action, выглядит следующим образом:

public delegate void Action();

Пример:

Task task = new Task (new Action(Print));

где Print - метод программы, который будет выполнен в отдельной задаче.

Класс TaskFactory

Класс TaskFactory кодирует некоторые распространенные шаблоны класса Task в методы, которые получают параметры по умолчанию, настраиваемые посредством своих конструкторов. В классе TaskFactory предоставляются различные методы, упрощающие создание задач и управление ими.

По умолчанию объект класса TaskFactory может быть получен из свойства Factory, доступного только для чтения в классе Task, используя это свойство, можно вызвать любые методы класса TaskFactory. Одним из таких методов - является метод StartNew(), у которого имеется множество форм вызова. Одна из таких форм продемонстрирована ниже:

public Task StartNew(Action действие)

где действие - точка входа в исполняемую задачу. Сначала в методе StartNew() автоматически создается экземпляр класса Task для действия, определяемого параметром действие, а затем планируется запуск задачи наисполнение. Следовательно, нет необходимости использовать метод Start(). Ниже представлены различные способы запуска задач с использованием TaskFactory:

// Использование фабрики задач

TaskFactory taskfactory = new TaskFactory();

Task task = taskfactory.StartNew(Действие);

// Использование фабрики задач через задачу

Task task = Task.Factory.StartNew(Действие);

// Использование конструктора Task

Task task = new Task(Действие);

task.Start();

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

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

// Вызов именного метода с помощью лямбда-выражения

Task task = Task.Factory.StartNew(() => DoSomething());

// Вызов анонимного метода с помощью лямбда-выражения

Task task = new Task.Factory.StartNew(() => { Console.WriteLine("Hello world!"); });

Примеры различных сортировок массивов с использованием принципа параллелизма

В данной части лекции будут рассмотрены различные виды алгоритмов сортировки массивов, а именно:

· Сортировка пузырьком;

· Сортировка вставками;

· Быстрая сортировка.

Ниже приведен пример программы, реализующей алгоритмы сортировки целочисленного случайно-сгенерированного массива в трех различных задачах, и последующем выводом на консоль, времени сортировки по каждому алгоритму:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Threading;

using System.Diagnostics;

namespace SortsExample

{

//создаем класс SortResults реализующий интерфейс IDisposable

class SortResults : IDisposable

{

//создаем объект класса Stopwatch, для измерения потраченного времени на работу алгоритмов сортировки

private Stopwatch _stopwatch = new Stopwatch();

private string sortName;

//создаем типизированную коллекцию List<string>

static private List<string> propResult = new List<string>();

//cоздаем свойство возвращающая значение типа List<string>

static public List<string> results

{

get { return propResult; }

}

//создаем конструктор класс SortResults в который будет передаваться название сортировки

public SortResults(string name)

{

//присваиваем переменной sortName значение имени сортировки

sortName = name;

//запускаем таймер

_stopwatch.Start();

}

//создаем метод интерфейса IDisposable - Dispose, который будет

вызываться по окончанию работы КАЖДОГО из алгоритмов сортировки

public void Dispose()

{

//останавливаем таймер

_stopwatch.Stop();

//добавляем в коллекцию результаты работы таймера в мс и название алгоритма

results.Add(string.Format("{0} : {1:N0}ms", sortName,

_stopwatch.ElapsedMilliseconds));

}

}

//создаем класс SortManager

class SortManager

{

//создаем типизированную коллекцию List<int>

private static List<int> integerList = new List<int>();

//создаем объект класса Barrier и задаем количество участвующих потоков в нашем случае это 3

private static Barrier sortBarrier = new Barrier(3);

//создаем метод который будет генерировать случайный числа

private static void PopulateIntegerList(uint size)

{

//создаем экземпляр класса Random

Random randomNumber = new Random(DateTime.Now.Millisecond);

for (int count = 0; count < size; count++)

{

//добавлем в коллекцию сгенерированное число

integerList.Add(randomNumber.Next());

}

}

//создаем метод реализующий алгоритм быстрой сортировки

public static void PivotSort(List<int> integerList, int start, int end, int pivot)

{

if (start < end)

{

pivot = integerList[end];

int location = start;

int bound = end;

while (location < bound)

{

if (integerList[location] < pivot)

{

location++;

}

else

{

integerList[bound] = integerList[location];

integerList[location] = integerList[bound - 1];

bound--;

}

}

integerList[bound] = pivot;

PivotSort(integerList, start, bound - 1, pivot);

PivotSort(integerList, bound + 1, end, pivot);

}

}

//создаем метод реализующий алгоритм сортировки вставками

public static void InsertionSort(List<int> sortedList)

{

int count = sortedList.Count;

int currentLocation, currentValue, insertionLocation;

sortedList.Insert(0, 0);

for (int location = 1; location < count + 1; location++)

{

currentLocation = location;

insertionLocation = location - 1;

currentValue = sortedList[currentLocation];

while (sortedList[insertionLocation] > currentValue)

{

sortedList[currentLocation] = sortedList[insertionLocation];

currentLocation--;

insertionLocation--;

}

sortedList[currentLocation] = currentValue;

}

sortedList.Remove(0);

}

//создаем метод реализующий алгоритм сортировки пузырьком

public static void BubbleSort(List<int> sortedList)

{

int count = sortedList.Count;

int temporary;

for (int iteration = 0; iteration < count; iteration++)

{

for (int index = 0; index + 1 < count; index++)

{

if (sortedList[index] > sortedList[index + 1])

{

temporary = sortedList[index];

sortedList[index] = sortedList[index + 1];

sortedList[index + 1] = temporary;

}

}

}

}

public static void DoSort()

{

//передаем в метод PopulateIntegerList, значение соответствующее количеству сгенерированных чисел

PopulateIntegerList(100000);

//создаем типизированную коллекцию List<int>, которая является копией

сгенерированного массива integerList и будет использоваться для сортировки пузырьком

List<int> bubbleList = integerList.ToList();

//создаем задачу сортировки пузырьком

Task taskBubbleSort = new Task(() =>

{

//вызываем метод SignalAndWait для синхронизации потока

sortBarrier.SignalAndWait();

//создаем объект класса SortResults

using (new SortResults("Сортировка пузырьком"))

{

//передаем значение коллекции bubbleList в метод сортировки пузырьком BubbleSort

BubbleSort(bubbleList);

}

});

//запускаем задачу

taskBubbleSort.Start();

//создаем типизированную коллекцию List<int>, которая является копией

сгенерированного массива integerList и будет использоваться для сортировки вставками

List<int> insertionList = integerList.ToList();

//создаем задачу сортировки вставками

Task taskInsertionSort = new Task(() =>

{

//вызываем метод SignalAndWait для синхронизации потока

sortBarrier.SignalAndWait();

//создаем объект класса SortResults

using (new SortResults("Сортировка вставками"))

{

//передаем значение коллекции insertionList в метод сортировки вставками InsertionSort

InsertionSort(insertionList);

}

});

//запускаем задачу

taskInsertionSort.Start();

//создаем типизированную коллекцию List<int>, которая является копией

сгенерированного массива integerList и будет использоваться для быстрой сортировки

List<int> pivotList = integerList.ToList();

//создаем задачу быстрой сортировки

Task taskPivotSort = new Task(() =>

{

//вызываем метод SignalAndWait для синхронизации потока

sortBarrier.SignalAndWait();

//создаем объект класса SortResults

using (new SortResults("Быстрая сортировка"))

{

//передаем значение коллекции pivotList в метод быстрой сортировки пузырьком PivotSort

PivotSort(pivotList, 0, pivotList.Count - 1, 1);

}

});

//запускаем задачу

taskPivotSort.Start();

// ожидаем завершения всех задач

Task.WaitAll(new Task[] { taskBubbleSort, taskInsertionSort, taskPivotSort });

//выводим результат на экран

foreach (string result in SortResults.results)

{

Console.WriteLine(result);

}

Console.ReadLine();

}

}

class Program

{

static void Main(string[] args)

{

//вызываем метод класса SortManager - DoSort

SortManager.DoSort();

}

}

}

Результат выполнения программы отображен на Рис. 5.1, который показывает, что массив, состоящий из 100000 случайных чисел, быстрее будет отсортирован алгоритмом "быстрой сортировки" нежели другими алгоритмами.

увеличить изображение
Рис. 6.1.Результаты выполнения программы сортировки массива