میتونی مثل merge sort نصف آرایتو با یه نخ نصف دیگشو با یه نخ دیگه به روش Quick sort مرتب کنی و از تابع merge استفاده کنی تا نتایج تو تا نخ رو با هم ادغام کنی. اگه میخوای درجه ی parallelism رو بالاتر ببری میتونی با تعداد بیشتری نخ این کار رو انجام بدی. نخ هات رو هم پارامتر دار بساز که بتونی رنج قسمتی رو که اون نخ قراره سورت کنه رو مشخص کنی. برای مساله ی concurrency هم میتونی یا قفل بذاری (که سرعت زیاد بالا نمیره و حتی پایین تر هم ممکنه بیاد) و میتونی آرایه رو کلا بشکونی که این روش بهتره.
-------
این کد رو با دو تا نخ نوشتم، زمان اجرا رو هم تقریبا به اندازه ی دو پنجم کاهش میده البته هر چقدر اعداد بیشتر باشن زمان اجرا با دو تا نخ تقریبا نصف میشه. میتونی از همین ایده استفاده کنی و تعداد نخ ها رو هم به صورت پویا تعریف کنی، یعنی با توجه به تعداد هسته های پردازنده و حجم آرایه:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
using System.Diagnostics;
namespace ConsoleApplication3
{
class Program
{
static object mylock = new object();
static public void MainMerge(int[] numbers, int left, int mid, int right)
{
int[] temp = new int[right+1];
int i, eol, num, pos;
eol = (mid - 1);
pos = left;
num = (right - left + 1);
while ((left <= eol) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
temp[pos++] = numbers[left++];
else
temp[pos++] = numbers[mid++];
}
while (left <= eol)
temp[pos++] = numbers[left++];
while (mid <= right)
temp[pos++] = numbers[mid++];
for (i = 0; i < num; i++)
{
numbers[right] = temp[right];
right--;
}
}
struct mystruct
{
public int left;
public int right;
}
static int[] array;
public static void mythread(object number)
{
int[] localarray;
mystruct num = (mystruct)number;
int x = 0;
int y = 0;
if (num.left == 0)
y = 1;
else
x = 1;
localarray = new int[num.right - num.left+y];
for (int i = 0; i < (num.right - num.left+y); i++)
{
localarray[i] = array[i + num.left];
}
QuickSort(localarray, 0, num.right - num.left-x);
for (int i = 0; i < (num.right - num.left+y); i++)
{
array[i + num.left] = localarray[i];
}
}
public static void ParallelSort(int items)
{
int mid;
int right = items;
int left = 0;
mid = (right + left) / 2;
mystruct s1 = new mystruct();
s1.left = left;
s1.right = mid;
mystruct s2 = new mystruct();
s2.left = (mid + 1);
s2.right = right;
Thread t1 = new Thread (new ParameterizedThreadStart(mythread));
Thread t2 = new Thread (new ParameterizedThreadStart(mythread));
t1.Start(s1);
t2.Start(s2);
t1.Join();
t2.Join();
MainMerge(array, left, (mid + 1), right-1);
}
public static int[] QuickSort(int[] Array, int Low, int High)
{
if (Low < High)
{
int p = partition(Array, Low, High);
QuickSort(Array, Low, p - 1);
QuickSort(Array, p + 1, High);
}
return Array;
}
private static int partition(int[] Array, int Low, int High)
{
int lb = Low + 1, rb = High, temp, pivot = Array[Low], p;
while ((lb <= rb))
{
while (Array[lb] <= pivot)
{
lb++;
if (!(lb <= rb))
break;
}
while (Array[rb] > pivot)
{
rb--;
if (!(lb <= rb))
break;
}
if (lb < rb)
{
temp = Array[lb];
Array[lb] = Array[rb];
Array[rb] = temp;
}
}
if (rb == High)
p = High;
else if (rb == Low)
p = Low;
else
p = lb - 1;
Array[Low] = Array[p];
Array[p] = pivot;
return p;
}
static void Main(string[] args)
{
Random rnd = new Random(DateTime.Now.Millisecond);
int number = 5000000;
array = new int[number];
for (int i = 0; i < number; i++)
{
array[i] = rnd.Next(0, number);
}
var x = Stopwatch.StartNew();
QuickSort(array, 0, number - 1);
x.Stop();
Console.WriteLine("Quick sort takes "+x.ElapsedTicks+" ticks.");
for (int i = 0; i < number; i++)
{
array[i] = rnd.Next(0, number);
}
x = Stopwatch.StartNew();
ParallelSort(number);
x.Stop();
Console.WriteLine("Parallel sort takes " + x.ElapsedTicks + " ticks.");
Console.ReadKey();
}
}
}
پاسخ با نقل قول
نوشته شده توسط erfan_urchin
