نمایش نتایج 1 تا 7 از 7

نام تاپیک: مرتب سازی سریع بصورت موازی

  1. #1
    کاربر دائمی آواتار Reza,M
    تاریخ عضویت
    تیر 1389
    محل زندگی
    ايران سراي من است
    پست
    412

    مرتب سازی سریع بصورت موازی

    با سلام
    دوستان از این الگوریتم برای مرتب سازی سریع استفاده می کنیم حال برای موازی کردن این الگوریتم چه کاری باید انجام داد؟

    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 <= rb)
    lb++;
    while (Array[rb] > pivot && lb <= rb)
    rb--;
    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;
    }





  2. #2

    نقل قول: مرتب سازی سریع بصورت موازی

    اگه منظورت مرتب سازی آرایه هستش میتونی از کد زیر هم استفاده بکنیا این همه کد نویسی لازم نیست
    Array.Sort(arrayname);

    البته اگه منظورتو درست فهمیده باشم و میخوای آرایه هایی که توشون عدد هستن رو مرتب کنی

  3. #3

    نقل قول: مرتب سازی سریع بصورت موازی

    میتونی مثل 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();
    }
    }
    }


    آخرین ویرایش به وسیله Arcsinos : شنبه 14 تیر 1393 در 15:06 عصر

  4. #4
    کاربر دائمی آواتار Reza,M
    تاریخ عضویت
    تیر 1389
    محل زندگی
    ايران سراي من است
    پست
    412

    نقل قول: مرتب سازی سریع بصورت موازی

    نقل قول نوشته شده توسط erfan_urchin مشاهده تاپیک
    اگه منظورت مرتب سازی آرایه هستش میتونی از کد زیر هم استفاده بکنیا این همه کد نویسی لازم نیست
    Array.Sort(arrayname);

    البته اگه منظورتو درست فهمیده باشم و میخوای آرایه هایی که توشون عدد هستن رو مرتب کنی
    دوست عزیز منظورم الگوریتمش بود.

  5. #5
    کاربر دائمی آواتار Reza,M
    تاریخ عضویت
    تیر 1389
    محل زندگی
    ايران سراي من است
    پست
    412

    نقل قول: مرتب سازی سریع بصورت موازی

    نقل قول نوشته شده توسط Arcsinos مشاهده تاپیک
    میتونی مثل merge sort نصف آرایتو با یه نخ نصف دیگشو با یه نخ دیگه به روش Quick sort مرتب کنی و از تابع merge استفاده کنی تا نتایج تو تا نخ رو با هم ادغام کنی. اگه میخوای درجه ی parallelism رو بالاتر ببری میتونی با تعداد بیشتری نخ این کار رو انجام بدی. نخ هات رو هم پارامتر دار بساز که بتونی رنج قسمتی رو که اون نخ قراره سورت کنه رو مشخص کنی. برای مساله ی concurrency هم میتونی یا قفل بذاری (که سرعت زیاد بالا نمیره و حتی پایین تر هم ممکنه بیاد) و میتونی آرایه رو کلا بشکونی که این روش بهتره.
    مرسی-میشه سمپل بزاری یا بیشتر توضیح بدی

  6. #6

    نقل قول: مرتب سازی سریع بصورت موازی

    نقل قول نوشته شده توسط Reza,M مشاهده تاپیک
    مرسی-میشه سمپل بزاری یا بیشتر توضیح بدی
    برادر پست قبلی رو ویرایش کردم و یه کد به دو تا نخ قرار دادم. اگه سوالی داشتی بپرس.
    در ضمن کدی هم که خودت گذاشتی باگ داشت که توی کدی که گذاشتم اون باگ هم برطرف شده. وقتی که lb بزرگتر از rb شد باید break بشه که این اتفاق صورت نمی گرفت.

  7. #7
    کاربر دائمی آواتار Reza,M
    تاریخ عضویت
    تیر 1389
    محل زندگی
    ايران سراي من است
    پست
    412

    نقل قول: مرتب سازی سریع بصورت موازی

    چرا به namespace
    using System.Threading.Tasks
    خطا میگیره؟؟

تاپیک های مشابه

  1. الگوریتم مرتب سازی سریع به زبان C#‎‎
    نوشته شده توسط loknatesabz در بخش C#‎‎
    پاسخ: 4
    آخرین پست: شنبه 14 بهمن 1391, 00:33 صبح
  2. مرتب سازی سریع
    نوشته شده توسط javad_babaey در بخش برنامه نویسی با زبان C و ++C
    پاسخ: 0
    آخرین پست: پنج شنبه 17 فروردین 1391, 12:34 عصر
  3. سوال: محاسبه تعداد عمل جابجایی مورد نیاز در مرتب سازی ارایه بصورت بازگشتی
    نوشته شده توسط sobhan1990 در بخش الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 1
    آخرین پست: یک شنبه 23 آبان 1389, 19:20 عصر
  4. الگوریتم مرتب سازی سریع(quick sort)
    نوشته شده توسط zahra11 در بخش برنامه‌نویسی جاوا
    پاسخ: 1
    آخرین پست: دوشنبه 02 اردیبهشت 1387, 22:54 عصر
  5. مرتب سازی سریع
    نوشته شده توسط eas_m66 در بخش برنامه نویسی با Borland C++‎ Builder
    پاسخ: 2
    آخرین پست: شنبه 27 بهمن 1386, 19:53 عصر

قوانین ایجاد تاپیک در تالار

  • شما نمی توانید تاپیک جدید ایجاد کنید
  • شما نمی توانید به تاپیک ها پاسخ دهید
  • شما نمی توانید ضمیمه ارسال کنید
  • شما نمی توانید پاسخ هایتان را ویرایش کنید
  •