Набор Алгоритмов
Данная статья посвящена Многопоточной быстрой сортировке, её основному применению.
Алгоритмы - Алгоритмы сортировки #4, Многопоточная Быстрая Сортировка
На больших массивах у Быстрой сортировки происходит переполнение стека.
Рассмотрим примеры кода, частный случай реализации концепции многопоточной быстрой сортировки. Все примеры написаны на C#. Далее приводится реализация кода и сравнение производительности многопоточной быстрой сортировки и однопоточной. Практического применения кода далее нет, т.к. на одном компьютере быстрее работает однопоточная сортировка, т.к. для многопоточной быстрой сортировки много времени занимает синхронизация. Но данный пример учит тому, как разделить монолитный массив данных на независимые объекты и является для понимания концепции не плохим примером.
Код основного файла для реализации быстрой многопоточной и однопоточной сортировки (QuickSorter.cs):
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace MultithreadedQuickSort
{
public class QuickSorter<T> where T : System.IComparable<T>, new()
{
#region Variables
private static int count = 0;
private static object locker = new object();
private static object lockerFinished = new object();
private ConcurrentDictionary<int, T> dict;
private bool _finished = false;
public bool Finished
{
get
{
lock (lockerFinished)
return _finished;
}
}
public T[] Array
{
get
{
lock (lockerFinished)
{
if (_finished)
return dict.Values.ToArray();
else
{
return new T[0];
}
}
}
}
#endregion
#region Main Methods
public static void Sort(ref T[] array, SortDirection sortDirection)
{
_Sort(ref array, 0, array.Length - 1, sortDirection);
}
private static void _Sort(ref T[] array, long low, long high, SortDirection sortDirection)
{
// 1. Если в массиве более одного элемента, то:
if (low < high)
{
// 1.1. Располагаем все элемента больше или равные справа последнего элемента, меньше - слева и вычисляем позицию новой середины.
long p = Partition(ref array, low, high, sortDirection);
// 1.2. Запускаем алгоритм рекурсивно для левой части.
_Sort(ref array, low, p - 1, sortDirection);
// 1.3. Запускаем алгоритм рекурсивно для правой части.
_Sort(ref array, p + 1, high, sortDirection);
}
}
private static long Partition(ref T[] array, long low, long high, SortDirection sortDirection)
{
// 1. Получаем значение последнего элемента и сохраняем в переменную x.
T x = array[high];
// 2. Устанавливаем i = (Индекс наименьшего элемента) - 1.
long i = low - 1;
// 3. Запускаем цикл от j = (Индекс наименьшего элемента) до предпоследнего включительно:
if (sortDirection == SortDirection.FromHighToLow)
for (long j = low; j < high; j++)
{
// 3.1. Если arr[j] <= x, то:
if (!(array[j].CompareTo(x) < 0))
{
// 3.1.1. Увеличиваем i на единицу.
i = i + 1;
// 3.1.2. Обмениваем местами arr[i] и arr[j].
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
else
for (long j = low; j < high; j++)
{
// 3.1. Если arr[j] >= x, то:
if (!(array[j].CompareTo(x) > 0))
{
// 3.1.1. Увеличиваем i на единицу.
i = i + 1;
// 3.1.2. Обмениваем местами arr[i] и arr[j].
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// 4. Обмениваем местами arr[i+1] и arr[high].
T temp2 = array[high];
array[high] = array[i + 1];
array[i + 1] = temp2;
// 5. Возвращаем i + 1.
return i + 1;
}
private int _MTPartition(int low, int high, SortDirection sortDirection)
{
// 1. Получаем значение последнего элемента и сохраняем в переменную x.
T x;
dict.TryGetValue(high, out x);
// 2. Устанавливаем i = (Индекс наименьшего элемента) - 1.
int i = low - 1;
// 3. Запускаем цикл от j = (Индекс наименьшего элемента) до предпоследнего включительно:
if (sortDirection == SortDirection.FromHighToLow)
for (int j = low; j < high; j++)
{
T arrayj;
dict.TryGetValue(j, out arrayj);
// 3.1. Если arr[j] <= x, то:
if (!(arrayj.CompareTo(x) < 0))
{
// 3.1.1. Увеличиваем i на единицу.
i = i + 1;
// 3.1.2. Обмениваем местами arr[i] и arr[j].
T temp;
dict.TryGetValue(i, out temp);
dict.TryUpdate(i, arrayj, temp);
dict.TryUpdate(j, temp, arrayj);
}
}
else
for (int j = low; j < high; j++)
{
T arrayj;
dict.TryGetValue(j, out arrayj);
// 3.1. Если arr[j] >= x, то:
if (!(arrayj.CompareTo(x) > 0))
{
// 3.1.1. Увеличиваем i на единицу.
i = i + 1;
// 3.1.2. Обмениваем местами arr[i] и arr[j].
T temp;
dict.TryGetValue(i, out temp);
dict.TryUpdate(i, arrayj, temp);
dict.TryUpdate(j, temp, arrayj);
}
}
// 4. Обмениваем местами arr[i+1] и arr[high].
T arrayhigh, temp2, arrayip1;
dict.TryGetValue(high, out arrayhigh);
temp2 = arrayhigh;
dict.TryGetValue(i + 1, out arrayip1);
dict.TryUpdate(high, arrayip1, arrayhigh);
dict.TryUpdate(i + 1, temp2, arrayip1);
// 5. Возвращаем i + 1.
return i + 1;
}
public void MultiThreadedSortWithCallback(T[] array, SortDirection sortDirection, Action callback)
{
dict = new ConcurrentDictionary<int, T>(Enumerable.Range(0, array.Length).ToDictionary(i => i, i => array[i]));
_MultiThreadedSort(0, array.Length - 1, sortDirection, callback);
}
public void MultiThreadedSort(T[] array, SortDirection sortDirection)
{
dict = new ConcurrentDictionary<int, T>(Enumerable.Range(0, array.Length).ToDictionary(i => i, i => array[i]));
_MultiThreadedSort(0, array.Length - 1, sortDirection, null);
}
private void _MultiThreadedSort(
int low, int high, SortDirection sortDirection, Action callback)
{
// 1. Если в массиве более одного элемента, то:
if (low < high)
{
// 1.1. Располагаем все элемента больше или равные справа последнего элемента, меньше - слева и вычисляем позицию новой середины.
int p = _MTPartition(low, high, sortDirection);
Thread caller1 = new Thread(
new ThreadStart(() => { _MultiThreadedSort(low, p - 1, sortDirection, callback); }));
Thread caller2 = new Thread(
new ThreadStart(() => { _MultiThreadedSort(p + 1, high, sortDirection, callback); }));
caller1.Start();
caller2.Start();
}
else
{
lock (locker)
{
count++;
if (count >= 2)
{
lock (lockerFinished)
{
if(!_finished)
{
if(callback != null)
callback();
_finished = true;
}
}
}
}
}
}
#endregion
}
}
Вспомогательный класс для работы основного кода, перечисление с заданием направления сортировки (SortDirection.cs):
namespace MultithreadedQuickSort
{
public enum SortDirection
{
FromLowToHigh,
FromHighToLow
}
}
Главный файл тестов для демонстрации работы примера (Program.cs):
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace MultithreadedQuickSort
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("____________________________________");
Console.WriteLine("Sorting Test");
Console.WriteLine("____________________________________");
PreTest();
Console.WriteLine("____________________________________");
Console.WriteLine("Performance Test");
Console.WriteLine("____________________________________");
Test();
Console.WriteLine("____________________________________");
Console.ReadKey();
}
private static void PreTest()
{
// Массив состоит из 15 целых чисел
int[] arr = new int[15];
// Заполняем его случайными числами
Random random = new Random((new Random()).Next());
for (int i = 0; i < 15; i++)
{
arr[i] = random.Next(0, 100);
}
// Выводим начальный массив
PrintArray("Start Array 1", arr);
// Замеряем время начала сортировки
DateTime startTime = DateTime.Now;
// Сортируем (в один поток) начальный массив от Большего к меньшему
QuickSorter<int>.Sort(ref arr, SortDirection.FromHighToLow);
// Замерям время окончания
DateTime endTime = DateTime.Now;
// Вывод отсортированного массива
PrintArray(String.Format("Array 1 sorted from high to low (Time is {0} ticks)", endTime.Subtract(startTime).Ticks), arr);
// Переинициализируем массив для чесноты эксперимента
Random random2 = new Random((new Random()).Next());
for (int i = 0; i < 15; i++)
{
arr[i] = random2.Next(0, 100);
}
// Выводим начальный массив
PrintArray("Start Array 1", arr);
// Замеряем время начала сортировки
DateTime startTimeM = DateTime.Now;
// Сортируем (в неограниченное число потоков) начальный массив от Меньшего к большему
QuickSorter<int> mqs = new QuickSorter<int>();
mqs.MultiThreadedSort(arr, SortDirection.FromLowToHigh);
while (!mqs.Finished) { Thread.Yield(); }
arr = mqs.Array;
// Замерям время окончания
DateTime endTimeM = DateTime.Now;
// Вывод отсортированного массива
PrintArray(String.Format("Array 1 sorted (multi) from low to high (Time is {0} ticks)", endTimeM.Subtract(startTimeM).Ticks), arr);
}
static void PrintArray(String arrayName, int[] arr)
{
Console.WriteLine(String.Format("{0} = ({1})", arrayName, String.Join(", ", arr)));
}
private static void Test()
{
// Массив состоит из 3000 целых чисел, не будем брать большое количество элементов, т.к. стек может быть переполнен
int[] arr = new int[10000];
long ticks1 = 0;
for (int testI1 = 0; testI1 < 5; testI1++)
{
// Заполняем его случайными числами
Random random = new Random((new Random()).Next());
for (int i = 0; i < 10000; i++)
{
arr[i] = random.Next(0, 1000000);
}
// Замеряем время начала сортировки
DateTime startTime = DateTime.Now;
// Сортируем (в один поток) начальный массив от Большего к меньшему
QuickSorter<int>.Sort(ref arr, SortDirection.FromHighToLow);
// Замерям время окончания
DateTime endTime = DateTime.Now;
ticks1 += endTime.Subtract(startTime).Ticks;
}
// Вывод результатов
Console.WriteLine(String.Format("Array 2 sorted from low to high (Time is {0} ticks)", ticks1/5));
long ticks2 = 0;
// Замеряем время начала сортировки
DateTime startTimeM = DateTime.Now;
int counter = 0;
for (int testI2 = 0; testI2 < 5; testI2++)
{
// Переинициализируем массив для чесноты эксперимента
Random random2 = new Random((new Random()).Next());
for (int i = 0; i < 10000; i++)
{
arr[i] = random2.Next(0, 1000000);
}
// Сортируем (в неограниченное число потоков) начальный массив от Меньшего к большему
QuickSorter<int> mqs = new QuickSorter<int>();
mqs.MultiThreadedSortWithCallback(arr, SortDirection.FromLowToHigh, () =>
{
DateTime endTimeM = DateTime.Now;
ticks2 = endTimeM.Subtract(startTimeM).Ticks;
Console.WriteLine(String.Format("Array 2 sorted (multi) from low to high (Time is {0} ticks)", ticks2));
++counter;
});
}
while(counter < 5) { Thread.Yield(); };
}
}
}
Консольный вывод результатов работы:
____________________________________
Sorting Test
____________________________________
Start Array 1 = (22, 99, 5, 62, 97, 76, 78, 93, 46, 27, 17, 54, 74, 42, 10)
Array 1 sorted from high to low (Time is 29984 ticks) = (99, 97, 93, 78, 76, 74, 62, 54, 46, 42, 27, 22, 17, 10, 5)
Start Array 1 = (67, 47, 5, 48, 83, 88, 67, 63, 49, 79, 41, 61, 22, 66, 99)
Array 1 sorted (multi) from low to high (Time is 1999068 ticks) = (5, 22, 41, 47, 48, 49, 61, 63, 66, 67, 67, 79, 83, 88, 99)
____________________________________
Performance Test
____________________________________
Array 2 sorted from low to high (Time is 17978 ticks)
Array 2 sorted (multi) from low to high (Time is 2808556 ticks)
Array 2 sorted (multi) from low to high (Time is 35219982 ticks)
Array 2 sorted (multi) from low to high (Time is 140380184 ticks)
Array 2 sorted (multi) from low to high (Time is 419170853 ticks)
Array 2 sorted (multi) from low to high (Time is 1047972920 ticks)
____________________________________
Как видно из результатов тестирования, многопоточная быстрая сортировка медленнее однопоточной (по тестированию на 4-х ядерном ПК). Это связано с тем, что много времени тратиться на объекты синхронизации C#.
Заключение
На больших массивах быстрая сортировка даёт исключение переполнения стека, в этом случае рекомендуемо использование циклических методов сортировки (см. Алгоритмы сортировки #1). Если требуется разделить массив на независимые объекты, которые в дальнейшем будут обработаны отдельно, допустим большие объёмы данных будут разделены по серверам, тогда быстрая сортировка — это правильный выбор.