Archive for 2010/10

مسابقه هوش مصنوعي گوگل

۱۳۸۹/۰۸/۰۱ ۱۳:۰۱ Salar https://www.blogger.com/profile/08261083424775464146 منتشر شده در تاریخ : ۱۳۸۹/۰۸/۰۱ دسته بندی : ، ، ، 12

اخیرا دوره دوم مسابقه برنامه نویسی هوش مصنوعی گوگل توسط دانشگلاه واترلو کانادا از 27 سپتامبر گذشته شروع به کار کرده. مهلت شرکت در مسابقه تا 27 نوابر امسال هست. در صورت علاقه مندی به این موضوع فرصت رو از دست ندید.

زبانهای برنامه نویسی بسیاری در این دوره پشتیبانی شده اند مانند C#, C++, Java, Python, PHP حتی Lisp هم شامل اونها هست. برای مشاهده لیست زیانهای پشتیبانی شده اینجا مراجعه کنید.

موضوع این دوره جنگ سیارات هست که الهام گرفته از بازی فلش Galcon هست. در این بازی باید تمامی سیارات دشمن رو تسخیر کنید. استراتژی و الگوریتم هوش مصنوعی که برای این منظور به کار می گیرید تعیین کننده پیروزی یا شکست شما خواهد بود. در این میان میتونید از سیاراتی که هنوز تسخیر نشده اند هم کمک بگیرید. به همین سادگی!
دو حریف در حال نبرد
دو حریف در حال نبرد

در صورتی که خواستید شرکت کنید این ابزار تست به درد شما خواهد خورد.

در مورد #C متاسفانه سرور آنها از نسخه قدیمی Mono استفاده می کند که فقط از از C# 2 پشتیبانی می کند و همچنین کامپایلر آن یک باگ دارد که باعث می شود بسیاری از ارسالها بی جهت کامپایل نشوند.

توجه کنید که این سایت از امکانات Html5 استفاده می کند و باید با مرورگرها جدید مانند نسخه جدید کروم و یا فایرفاکس4 این سایت رو مشاهده کنید.

پ.ن 1: ظاهرا گوگل این وسط هیچکاره هست و هیچ کمکی نمی کنه و شرکت کنندگان از وضع سرور خیلی ناراضی هستند و می خوان تا حامی دیگری برای این مسابقه پیدا کنند.

پ.ن 2: این مسابقه هیچ جایزه ای تا الان که این رو مینوسم نداره! گوگل هیچ کارس مثل اینکه!

پ.ن 3: من هم خواستم که شانس خودم رو امتحان کنم و نتیجه اش این شد! ده نفر اول واقعا که دانش بسیار بالایی دارند!

پ.ن 4: لیست ایرانی های حاظر در مسابقه، خیلی کمه!

 

Parallel سازي براي دات نت 2

۱۳۸۹/۰۷/۱۶ ۱۳:۴۲ Salar https://www.blogger.com/profile/08261083424775464146 منتشر شده در تاریخ : ۱۳۸۹/۰۷/۱۶ دسته بندی : ، ، ، ، 1

Parallel
همانطور که در دو پست قبلی مطالعه کردید در دات نت فریم ورک 4 قابلیت بسیار مفید parallel اضافه شده است. آن مجموعه کلاسها این امکان را فراهم می کنند که چندین کار در میان هسته های سیستم تقسیم شده و همزمان انجام شود. تنها عیب آن این است که فقط برای دات نت 4 در دسترس است.

برای حل این محدودیت می توان از روش های جایگزین استفاده کرد. گرچه این روشها باز هم به پای امکانات مهیا شده در دات نت 4 نمی رسد ولی باز هم بسیار راه گشا هستند. برای روش جایگزین می توان هم مستقیما از Thread ها استفاده کرد و هم از ThreadPool که کنترل thread ها را خودکار انجام می ده. البته این دو روش تفاوت فاحشی با هم دارند. تفاوت روش استفاده مستقیم از thread با threadpool عدم وابستگی به تعداد هسته cpu ها است، بدین معنا که در آن تقریبا همه آیتمها را به یکباره مورد پردازش قرار خواهند گرفت(البته به تعداد تعیین شده). اما threadpool همانند دات نت 4 عمل کرده و متدهای در حال اجرا و همزمان را به تعداد هسته cpu محدود می کند (با اندکی تفاوت). ابتدا متدی که مستقیما با thread ها کار می کند را معرفی می کنم و سپس روش threadpool را معرفی خواهم کرد.

با استفاده تابع زیر که تهیه کردم این امکان فراهم می آید که لیستی از آیتم ها را برای پردازش توسط یک متد یا رویه به طور همزمان پردازش نمایید. متد WorkAsParallel که در پایین ملاحظه می کنید دو ورودی می گیرد که ورودی اول لیستی جنریک از آیتم ها است و ورودی دوم متد پردازشگر مورد نظر که بر روی تک تک آیتم ها اجرا شده و عمل مورد تان را انجام می دهد.
public static void WorkAsParallel<T>(IList<T> itemsList, ParameterizedThreadStart itemDoWork)
{
// the maximum number of active threads
const int maxThreads = 10;
List<Thread> workers = new List<Thread>();

if (itemsList.Count > maxThreads)
{
    int currentItem = 0;
    for (int i = 0; i < maxThreads; i++)
    {
        T item = itemsList[i];
        try
        {
            Thread worker = new Thread(itemDoWork);
            worker.IsBackground = true;
            worker.Name = item.ToString();

            workers.Add(worker);

            // item index
            currentItem++;

            // start the thread
            worker.Start(item);
        }
        catch
        {
            // ignore any exception
        }
    }

    // A little break in current thread
    Thread.Sleep(5);

    do
    {
        // start waiting
        for (int i = workers.Count - 1; i >= 0; i--)
        {
            Thread worker = workers[i];

            if ((worker.ThreadState | ThreadState.Stopped) == ThreadState.Stopped)
            {
                workers.RemoveAt(i);

                // thread finished! run next irem if it is there
                if (currentItem <= itemsList.Count - 1)
                {
                    T item = itemsList[currentItem];
                    worker = new Thread(itemDoWork);
                    worker.IsBackground = true;
                    worker.Name = item.ToString();

                    workers.Add(worker);

                    // increase the item index
                    currentItem++;

                    // start the thread
                    worker.Start(item);
                }
            }
        }

        // a little break
        Thread.Sleep(5);

    } while (itemsList.Count > currentItem);

    // now all the list items are in progress

    // start waiting for them to be done
    foreach (Thread worker in workers)
    {
        // just wait for it
        // an infinity wait!
        worker.Join();
    }
}
else
{
    // all items are starting in threads
    foreach (T item in itemsList)
    {
        try
        {
            Thread worker = new Thread(itemDoWork);
            worker.IsBackground = true;
            worker.Name = item.ToString();

            workers.Add(worker);

            // start the thread
            worker.Start(item);
        }
        catch
        {
            // ignore any exception
        }
    }

    // A little break in current thread
    Thread.Sleep(5);

    // start waiting for them to be done
    foreach (Thread worker in workers)
    {
        // just wait for it
        // an infinity wait!
        worker.Join();
    }
}
}

به طور پیش فرض تعداد thread فعال 10 در نظر گرفته شده است (توسط ثابت maxThreads که قابل افزایش است) بدین معنا که در صورتی تعداد آیتمهای لیست شما بیش از 10 تا باشد ابتدا فقط 10 آیتم ابتدایی اجرا خواهند شد و تنها پس از پایان هر thread آیتم بعدی مورد پردازش قرار خواهد گرفت. این محدودیت به خاطر جلوگیری از وارد شدن فشار بیش از حد به سیستم در نظر گرفته شده و در صورت صلاحدید شما قابل افزایش است.

  • روش استفاده از WorkAsParallel

در مثال زیر یک لیست از DateTime با تاخیر زمانی 1 ثانیه چاپ می شود تا همزانی اجرا هم مشخص شود.
public void TestWorkAsParallel()
{
    List<DateTime> theList = new List<DateTime>();
    theList.Add(DateTime.Now.AddDays(1));
    theList.Add(DateTime.Now.AddDays(2));
    theList.Add(DateTime.Now.AddDays(3));

    ParallelWorks.WorkAsParallel(theList, x =>
    {
        DateTime item = (DateTime)x;
        Console.Write(item);
        Thread.Sleep(1000);
    });
}

و برای استفاده در VS 2005 که با کامپایلر CCS2 کار می کنه مثال مذبور رو به این تغییر بدید:
ParallelWorks.WorkAsParallel(theList, delegate(object x)
{
    DateTime item = (DateTime) x;
    Console.Write(item);
    Thread.Sleep(1000);
});

  • استفاده از ThreadPool

متد مورد نظر من در این پست از وبلاگ معرفی شده است. این متد لیستی از متد های قابل اجرا را دریافت کرده و به صورت همزمان اجرا می کند.
public class ParallelProcessor
{
    public delegate void Method();

    /// <summary>
    /// Executes a set of methods in parallel and returns the results
    /// from each in an array when all threads have completed.  The methods
    /// must take no parameters and have no return value.
    /// </summary>
    /// <param name="m"></param>
    /// <returns></returns>
    public static void ExecuteParallel(params Method[] methods)
    {
        // Initialize the reset events to keep track of completed threads
        ManualResetEvent[] resetEvents = new ManualResetEvent[methods.Length];

        // Launch each method in it's own thread
        for (int i = 0; i < methods.Length; i++)
        {
            resetEvents[i] = new ManualResetEvent(false);
            ThreadPool.QueueUserWorkItem(new WaitCallback((object index) =>
            {
                int methodIndex = (int)index;

                // Execute the method
                methods[methodIndex]();

                // Tell the calling thread that we're done
                resetEvents[methodIndex].Set();
            }), i);
        }

        // Wait for all threads to execute
        WaitHandle.WaitAll(resetEvents);
    }
}

روش استفاده آن هم همانطور که در آن پست ذکر شده آسان است.
ParallelProcessor.ExecuteParallel(() =>
{
    Console.WriteLine("The long task 1");
    Thread.Sleep(500);
}, () =>
{
    Console.WriteLine("The long task 2");
    Thread.Sleep(500);
},
() =>
{
    Console.WriteLine("The long task 3");
    Thread.Sleep(500);
});

و برای VS2005 از این روش فراخوانی استفاده کنید:
ParallelProcessor.Method[] methods = new ParallelProcessor.Method[3];
methods[0] = delegate{
    Console.WriteLine("The long task 1");
    Thread.Sleep(500);
};
methods[1] = delegate{
    Console.WriteLine("The long task 1");
    Thread.Sleep(500);
};
methods[2] = delegate{
    Console.WriteLine("The long task 1");
    Thread.Sleep(500);
};
ParallelProcessor.ExecuteParallel(methods);

  • مقایسه WorkAsParallel و ParallelProcessor در عمل

مسلما مقایسه این دو روش زیاد صحیح نخواهد بود. این به علت متفاوت بودن شیوه اجرای این دو روش است. به هرحال جهت نمایش این تفاوت مثال زیر را اجرا می کنیم:
static void Main(string[] args)
{
    Console.WriteLine("Parallels for .NET 2, salarblog.wordpress.com");

    // The list
    List<int> taskList = new List<int>() { 1, 2, 3, 4, 5, 6 };

    var pwatch = Stopwatch.StartNew();
    ParallelWorks.WorkAsParallel(taskList, x =>
    {
        Console.WriteLine("The long task {0} started at {1}", x, DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    });
    pwatch.Stop();
    Console.WriteLine("WorkAsParallel done!");

    var twatch = Stopwatch.StartNew();
    ParallelProcessor.ExecuteParallel(delegate
    {
        Console.WriteLine("Task 1 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    }, delegate
    {
        Console.WriteLine("Task 2 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    }, delegate
    {
        Console.WriteLine("Task 3 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    }, delegate
    {
        Console.WriteLine("Task 4 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    }, delegate
    {
        Console.WriteLine("Task 5 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    }, delegate
    {
        Console.WriteLine("Task 6 started at " + DateTime.Now.ToString("ss:fff"));
        Thread.Sleep(1000);
    });
    twatch.Stop();

    Console.WriteLine();
    Console.WriteLine("WorkAsParallel finished in {0} seconds", pwatch.Elapsed.TotalSeconds);
    Console.WriteLine("ParallelProcessor finished in {0} seconds", twatch.Elapsed.TotalSeconds);

    // wait
    Console.ReadKey();
}

نتیجه اجرا چیزی مانند این خواهد بود (این نتیجه سیستم دو هسته من هست):
WorkAsParallel v.s. ParallelProcessor[/caption]به زمانها دقت کنید. تفاوت فاهش است، 3 ثانیه برای ParallelProcessor در مقابل 1 ثانیه برای WorkAsParallel. اما این دلیل بر بهتر بودن WorkAsParallel نیست. اگر به زمانهای شروع هر تسک نگاه کنید می بینید که تسک های متد WorkAsParallel همه تقریبا همزمان اجرا شده اند. (زمانها به صورت میلی ثانیه:ثانیه هستند). دلیل این امر را همانطور که گفتیم استفاده مستقیم از thread است.

در هر صورت این دو توابع در دسترس هستند و می توانید با توجه به نیاز خود هر کدام را که خواستید انتخاب کرده و مورد استفاده قرار دهید.

 

نگاهي به Parallel Extensions در دات نت 4 بخش دوم

۱۳۸۹/۰۷/۰۹ ۱۵:۱۱ Salar https://www.blogger.com/profile/08261083424775464146 منتشر شده در تاریخ : ۱۳۸۹/۰۷/۰۹ دسته بندی : ، ، ، ، ، ، 3

در نوشته قبلی در مورد شیوه عملکرد و به کارگیری PLINQ و Parallel ها مطالبی خواندید. در این نوشتار قصد دارم در مورد Task ها (وظایف) صحبت کرده و مروری بر نکات مهم آن داشته باشیم.

  • Task چیست

Task کلاس جدیدی است که نماینده کاری است که قرار است انجام بدهید. تسکها نیز همانند Parallel ها فقط بر روی هسته های CPU زمی شوند. به این معنا که به تعداد هسته های CPU تسک ها خواهند توانست به طور همزمان اجرا شوند. متدها و کلاسهایی برای کنترل تسک ها فراهم شده تا امکان کنترل اجرای آنها و همزمان سازی آنها را مهیا کند.

تمامی پیچیدگی کار و اعمالی قرار است بر روی تسک ها انجام بشود توسط Task Scheduler (زمان بند وظایف) پیاده شده و انجام می شود. کاری که Task Scheduler انجام می دهد مدیریت اجرای تسک ها و کنترل نحوه تقسیم آنها در میان Thread های مختلف است.

فرایندی که هنگام کار با Task Scheduler اتفاق می افتد را اینگونه می توان شرح داد:

  • هنگام ایجاد تسک، آن به صف عمومی تسک ها اضافه می شود.

  • ایجاد Thread های "کارگر" مورد نیاز برای انجام کار تسک ها توسط مدیر Thread های دات نت (Thread pool). تعداد دقیق این thread ها بستگی به فاکتور های مختلفی از جمله تعداد هسته های cpu سیستم، حجم کارهای فعلی در جریان، نوع کار در جریان دارد. برای مثال اگر مدیر thread ها تشخصی دهد که فرایندها در مرحله کار با I/O دارای تاخیر هستند (مانند ذخیره یا دانلود فایل) تعداد thread بیشتری را برای افزایش سرعت ایجاد خواهد کرد. همچنین فرایند پشت زمینه ای هم همزمان هر 0.5 ثانیه پایان کار thread ها را بررسی می کند که اگر هیچ کدام به پایان نرسیده باشد، thread جدیدی را برای انجام کار ایجاد کند.

  • هر thread کارگر تسک ها را از صف عمومی تسک ها برداشته و به صف داخلی خود برای اجرا انتقال می دهد.

  • هر thread کارگر تسک های صف داخلی خود را انجام می دهد.

  • اگر هر thread صف داخلی خود را به پایان برساند، از صف thread های دیگر کارهای در انتظار را از آخر صف برداشته و پردازش می کند.

  • نموداری از فرایند بالا را مشاهده کنید:

روند کار مدیر تسک ها
روند کار مدیر تسک ها

  • ایجاد و مدیریت تسکها

ایجاد و به کار گیری تسک ها بسیار ساده و آسان است. برای ایجاد تسک از دو طریق می توان اقدام کرد. متد Task.Factory.StartNew که ورودی تابع مورد نظر (از نوع action delegate) را دریافت کرده و فورا شروع به کار می کند. مانند مثال زیر:

Task test = Task.Factory.StartNew(() => Console.WriteLine("hello"));

و یا اینکه مستقیما نمونه جدید از کلاس Task ایجاد کنید که ورودی آن هم تابع مورد نظر برای اجرا خواهد بود. برای اجرای تسک سپس باید متد Start را فرواخوانی بکنید:
Task test= new Task(() => Console.WriteLine("hello"));
test.Start();

انتظار برای پایان تسک

در حالت عادی اجرای تسک سبب مسدود شدن رویه در حال اجرا نخواهد شد. در صورتی که مایل باشید تا اجرای رویه را تا پایان تسک یا تسک های مورد نظر متوقف کنید از توابع زیر می توانید استفاده کنید.

متد Task.Wait سبب انتظار برای پایان تسک مورد نظر خواهد شد. برای انتظار به چندین تسک از متد Task.WaitAll استفاده کنید که چندین تسک را به عنوان ورودی دریافت می کند و رویه اجرای برنامه تا پایان همه آنها منتظر خواهد بود.

متد Task.WaitAny چندین ورودی تسک را دریافت می کند و تا زمانی که حداقل یکی از تسک ها به پایان برسد منتظر خواهد ماند. کاربرد این روش می تواند برای انجام عملی باشد که نتیجه مشابهی دارد و از روش متفاوت می توان استفاده کرد و نتیجه برایتان مهم است.

مثالی از کاربرد این متد ها:
Task task1 = Task.Factory.StartNew(() => Console.WriteLine("task 1"));
Task task2 = new Task(() => Console.WriteLine("hello task 2"));
Task task3 = Task.Factory.StartNew(() => Console.WriteLine("task 3")); 

task2.Start(); 

task1.Wait();
Task.WaitAll(task2, task3);

با استفاده از ویژگی IsComplete نیز میتوانید به پایان رسیدن یک تسک را مورد آزمایش قرار دهید.

ترتیب اجرا

در صورتی که نیاز داشته باشید تا حتما پس از پایان یک تسک، تسک بعدی اجرا شود تابع ContinueWith برای همین منظور در نظر گرفته شده است. این تابع باید بر روی تسک مورد نظر فراخوانی شود. در این صورت متد ارسالی به ContinueWith بعد از تسک مورد نظر فراخوانی خواهد شد.
Task task = Task.Factory.StartNew(() => Console.WriteLine(" task 1"))
.ContinueWith(x=>  Console.WriteLine("task 2") )
.ContinueWith(x=>  Console.WriteLine("task 3") )
.ContinueWith(x=>  Console.WriteLine("task 4") );

نکته: توجه کنید که در این مثال تسکها یکی پس از دیگری و فقط در صورت پایان هر تسک، تسک بعدی اجرا خواهد شد. (یعنی تسک ها به طور همزمان بر روی هسته های مختلف اجرا نخواهند شد)

همچنین تابع ContinueWith ورودی از نوع TaskContinuationOptions را دریافت می کند که امکان تعیین شرط برای اجرای تسک را فراهم و همچنین ویژگیهای ویژه ای را برای تسک تعیین می کند. برای مثال با تعیین TaskContinuationOptions.OnlyOnFaulted به عنوان شرط، تسک بعدی فقط در صورت شکست اجرای تسک قبلی اجرا خواهد شد. برای اطلاع بیشتر راجع به سایر مقادیر به راهنمای msdn مراجعه کنید.

دریافت خروجی از تسک

برای دریافت خروجی کافی هست که در متد تسک مورد نظر خروجی را ارسال کنیم ( در حقیقت داریم از Func delegate استفاده می کنیم). در این صورت خروجی از طریق ویژگی Result در دسترس خواهد بود.
var data = Task.Factory.StartNew(() => GetResult());
Console.WriteLine("Parallel task returned with value of {0}", data.Result);

Task<string> t = new Task<string>(()=>{
return "hello";
});
t.Start();
Console.WriteLine("The result is {0}", t.Result);

نکته: فراخوانی ویژگی Result در صورتی که هنوز تسک به پایان نرسیده سبب خواهد شد تا برنامه تا زمان پایان یافتن اجرای تسک و دریافت خروجی متوقف شود. برای جلوگیری از این اتفاق می توانید از ویژگی IsComplete یا روشهایی که خواندید استفاده کنید.

  • تداخل با UI

هنگام کار با thread ها نمی توانید مقادیر کنترل ها را تغییر بدهید به عبارت دیگر، به thread مربوط به GUI دسترسی نخواهید داشت. (این محدودیت به علت جلوگیری از مشکلات احتمالی توسط دات نت اعمال شده است).

با توجه به اینکه Task هم از thread ها برای اجرای متدهایش استفاده می کند همین مشکل نیز در استفاده از آنها وجود دارد. راه حل این مشکل بسیار ساده می باشد.

برای حل این مشکل با استفاده از تابع TaskScheduler.FromCurrentSynchronizationContext که مدیر تسک های(TaskScheduler) جدیدی را برای thread فعلی ایجاد کرده و بر میگرداند. حال اگر این تابع را در فرم اجرا کنیم محیط اجرا در thread GUI قرار خواهد داشت. سپس کافی است تا این مقدار را به سازنده تسک و یا ادامه دهنده آن (ContinueWith) ارسال کنیم. در این صورت تسک مورد نظر در thread فرم اجرا خواهد شد و در نتیجه تغییر کنترل ها بدون مشکل میسر خواهد بود.
private void button1_Click(object sender, EventArgs e)
{
    var ui = TaskScheduler.FromCurrentSynchronizationContext();

    Task.Factory.StartNew(() =>
    {
        return LoadAndProcessImage(); // compute the image

    }).ContinueWith(t =>
    {

        pictureBox1.Image = t.Result; // display it

    }, ui);
}

در این مثال ابتدا پردازش مورد نظر انجام می شود سپس در تسک بعدی که در thread مربوط به GUI اجرا خواهد شد، نتیجه به کنترل تصویر تخصیص داده می شود.

موفق باشید.

  • منابع

APress - Pro .NET 4 Parallel Programming in C#
APress - Introducing .NET 4.0
What’s new in Beta 1 for the Task Parallel Library?