Я ищу простую реализацию параллельного (многопоточного) алгоритма сортировки в С#, который может работать с List<T> или массивами, и, возможно, с использованием параллельных расширений, но эта часть не является строго необходимой.
Изменить: Фрэнк Крюгер дает хороший ответ, однако я хочу преобразовать этот пример в тот, который не использует LINQ. Также обратите внимание, что Parallel.Do(), кажется, было заменено на Parallel.Invoke().
Спасибо.
Из "The Darkside" в его статье Parallel Extensions для .Net Framework у нас есть эта параллельная версия версии quicksort:
private void QuicksortSequential<T>(T[] arr, int left, int right)
where T : IComparable<T>
{
if (right > left)
{
int pivot = Partition(arr, left, right);
QuicksortSequential(arr, left, pivot - 1);
QuicksortSequential(arr, pivot + 1, right);
}
}
private void QuicksortParallelOptimised<T>(T[] arr, int left, int right)
where T : IComparable<T>
{
const int SEQUENTIAL_THRESHOLD = 2048;
if (right > left)
{
if (right - left < SEQUENTIAL_THRESHOLD)
{
QuicksortSequential(arr, left, right);
}
else
{
int pivot = Partition(arr, left, right);
Parallel.Do(
() => QuicksortParallelOptimised(arr, left, pivot - 1),
() => QuicksortParallelOptimised(arr, pivot + 1, right));
}
}
}
Обратите внимание, что он возвращается к последовательной сортировке, когда количество элементов меньше 2048.
Обновление Теперь я добиваюсь улучшения более чем на 1,7 раза на двухъядерной машине.
Я думал, что попробую написать параллельный сортировщик, который работал в .NET 2.0 (я думаю, проверьте это), и это не использует ничего, кроме ThreadPool.
Ниже приведены результаты сортировки массива элементов размером 2 000 000:
Time Parallel Time Sequential ------------- --------------- 2854 ms 5052 ms 2846 ms 4947 ms 2794 ms 4940 ms ... ... 2815 ms 4894 ms 2981 ms 4991 ms 2832 ms 5053 ms Avg: 2818 ms Avg: 4969 ms Std: 66 ms Std: 65 ms Spd: 1.76x
Я получил ускорение 1,76 раза - довольно близко к оптимальному 2x, на который я надеялся - в этой среде:
Model объектовDateTime.На этот раз я использовал Ben Watson QuickSort в С#. Я изменил его внутренний цикл QuickSort:
QuickSortSequential:
QuickSortSequential (beg, l - 1);
QuickSortSequential (l + 1, end);
в
QuickSortParallel:
ManualResetEvent fin2 = new ManualResetEvent (false);
ThreadPool.QueueUserWorkItem (delegate {
QuickSortParallel (l + 1, end);
fin2.Set ();
});
QuickSortParallel (beg, l - 1);
fin2.WaitOne (1000000);
fin2.Close ();
(На самом деле, в коде я немного балансирую нагрузку, что помогает.)
Я обнаружил, что запуск этой параллельной версии только окупается, когда в массиве содержится более 25 000 элементов (хотя, как минимум, 50 000, как мне кажется, позволяют моему процессору больше дышать).
Я сделал так много улучшений, как я могу думать о своей маленькой двухъядерной машине. Я хотел бы попробовать некоторые идеи по 8-стороннему монстру. Кроме того, эта работа была выполнена на небольшом 13-дюймовом MacBook под управлением Mono. Мне любопытно, как другие покупают обычную установку .NET 2.0.
Исходный код во всей его уродливой славе доступен здесь: http://www.praeclarum.org/so/psort.cs.txt. Я могу очистить его, если у вас есть интерес.
Для записи здесь приведена версия без выражений lamda, которые будут компилироваться в С# 2 и .Net 2 + Parallel Extensions. Это также должно работать с Mono с собственной реализацией Parallel Extensions (от Google Summer of code 2008):
/// <summary>
/// Parallel quicksort algorithm.
/// </summary>
public class ParallelSort
{
#region Public Static Methods
/// <summary>
/// Sequential quicksort.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T>
{
QuicksortSequential(arr, 0, arr.Length - 1);
}
/// <summary>
/// Parallel quicksort
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="arr"></param>
public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T>
{
QuicksortParallel(arr, 0, arr.Length - 1);
}
#endregion
#region Private Static Methods
private static void QuicksortSequential<T>(T[] arr, int left, int right)
where T : IComparable<T>
{
if (right > left)
{
int pivot = Partition(arr, left, right);
QuicksortSequential(arr, left, pivot - 1);
QuicksortSequential(arr, pivot + 1, right);
}
}
private static void QuicksortParallel<T>(T[] arr, int left, int right)
where T : IComparable<T>
{
const int SEQUENTIAL_THRESHOLD = 2048;
if (right > left)
{
if (right - left < SEQUENTIAL_THRESHOLD)
{
QuicksortSequential(arr, left, right);
}
else
{
int pivot = Partition(arr, left, right);
Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);},
delegate {QuicksortParallel(arr, pivot + 1, right);}
});
}
}
}
private static void Swap<T>(T[] arr, int i, int j)
{
T tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static int Partition<T>(T[] arr, int low, int high)
where T : IComparable<T>
{
// Simple partitioning implementation
int pivotPos = (high + low) / 2;
T pivot = arr[pivotPos];
Swap(arr, low, pivotPos);
int left = low;
for (int i = low + 1; i <= high; i++)
{
if (arr[i].CompareTo(pivot) < 0)
{
left++;
Swap(arr, i, left);
}
}
Swap(arr, low, left);
return left;
}
#endregion
}
Сорт слияния, основанный на размере кеша процессора, с разметкой блоков между процессорами.
Этап слияния может быть выполнен путем разбиения слияния на n бит с каждым процессором, начинающим слияние блоков с правильным смещением в блоки.
Я не пробовал написать это.
(Поскольку относительная скорость кэша ЦП и основного плунжера не так далеко от относительной скорости ОЗУ и Ленты в качестве времени, когда была обнаружена сортировка слияния, возможно, нам следует снова начать использовать сортировки слияния)
Разделите список, который вам нужно отсортировать в подсписках равного размера, в зависимости от того, сколько процессоров у вас есть, а затем, когда выполняются две части, объедините их вместе с новой частью, пока не останется только один левый и все потоки завершены. Очень просто вы должны реализовать его самостоятельно, и сортировка списков в каждом потоке может быть выполнена с использованием любого существующего алгоритма сортировки (например, в библиотеке).