Алгоритм параллельной сортировки
Я ищу простую реализацию параллельного (многопоточного) алгоритма сортировки в C#, который может работать на List<T> или массивы, и, возможно, с использованием параллельных расширений, но эта часть не является строго необходимой.
Изменить: Фрэнк Крюгер дает хороший ответ, однако я хочу преобразовать этот пример в тот, который не использует LINQ. Также обратите внимание, что Parallel.Do() кажется, был заменен Parallel.Invoke(),
Благодарю.
5 ответов
От "Темной стороны" в его статье " Параллельные расширения" до.Net Framework у нас есть версия параллельных расширений быстрой сортировки:
(Изменить: Поскольку ссылка теперь не работает, заинтересованные читатели могут найти ее архив на Wayback Machine)
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 элементов:
Время Параллельное Время Последовательное ------------- --------------- 2854 мс 5052 мс 2846 мс 4947 мс 2794 мс 4940 мс... ... 2815 мс 4894 мс 2981 мс 4991 мс 2832 мс 5053 мс Среднее значение: 2818 мс. Среднее значение: 4969 мс. Стандарт: 66 мс Стандарт: 65 мс Spd: 1,76x
Я получил ускорение в 1,76 раза - довольно близкое к оптимальному 2x, на которое я надеялся - в этой среде:
- 2 000 000 случайных
Modelобъекты - Сортировка объектов по делегату сравнения, который сравнивает два
DateTimeсвойства. - Моно JIT-компилятор версии 2.4.2.3
- Max OS X 10.5.8 на 2,4 ГГц Intel Core 2 Duo
На этот раз я использовал QuickSort Бена Уотсона в C#. Я изменил его 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. Я могу почистить его, если есть интерес.
Для справки - версия без лямда-выражений, которая будет компилироваться в C#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 битов, причем каждый процессор начинает объединять блоки с правильным смещением в блоки.
Я не пробовал писать это.
(Поскольку относительная скорость кэш-памяти ЦП и основной оперативной памяти не так уж далеко отличается от относительной скорости ОЗУ и ленты в момент обнаружения сортировки слиянием, возможно, нам следует снова начать использовать сортировку слиянием)
Разделите список, который вам нужно отсортировать на подсписки одинакового размера, в зависимости от того, сколько у вас процессоров, и затем, когда две части сделаны, объединяйте их вместе в новую часть, пока не останется только одна левая часть и все потоки не будут завершены. Очень просто, вы должны иметь возможность реализовать это самостоятельно, а сортировка списков в каждом потоке может быть выполнена с использованием любого существующего алгоритма сортировки (как в библиотеке).