من پت هستم

منتظر حمایت سبز شما از iampat در IEEEXtreme 4 هستیم.

التماس دعا

پس نوشت ۱ : قضیه معرکه‌گیری سر پیریه! کلا توی اواخر دهه‌ی سوم زندگی حضور مسابقات قهرمانی یک جور شوخی محسوب می‌شود ولی بعد از ۳۰ دیگر حتی شوخی هم نیست. حالا ورزش باشد یا برنامه‌نویسی، فرقی نمی‌کند!

پس نوشت ۲: اگر یادتون باشد گفته بودم که مشغول کاری هستم که صداش ۲۹ آبان امسال در می‌آید. متاسفانه بدلیل اندکی آسیب‌دیدگی آن قضیه فعلا منتفی شد ولی امیدوارم قبل از ۳۰ سالگی اون قضیه هم به سرانجام برسد. التماس دعا

بد جور حوصله‌ام سر رفته. از یک طرف مشغول کار کردن روی یکی از مقاله‌ی یکی از کارهای قدیمی‌ام هستم. که حالم از سر تا پای اون کار بهم می‌خوره. خدایش تصور کنید با این همه انگیزه چطور می‌توانم کار را تمام کنم؟ کلا انرژی منفی است که داره به وجودم تزریق می‌شود

از طرف دیگر، از ابتدای تابستان تا به حال هیچ کار مفیدی در راستای تزم انجام ندادم و خدا به دادم برسد اگر این استادهای شنگول و منگول من سراغی از پیشرفت کار بگیرند که در حال حاضر من تقریبا موضوع کارم را هم فراموش کرده‌ام.

• I worked  about 10 minutes to find an optimum but slow algorithm,
• then 2 hours to find a slower dummy not optimum algorithm.
  Finally, after 2 days, I found the fastest (as I believe UNTIL now) optimum algorithm.

* These days, I am practising to get ready for an important interview.

اول، بابا برگشت ایران و جاش توی خانه خیلی خالیه!

دوم، اسباب کشی کردم. وسط شهر به من نمی‌ساخت، تحمل سر و صدا و شلوغی وسط شهر را اصلا نداشتم. خلاصه دوباره برگشتم وسط جنگل.

سوم، مامان حوصله‌اش از پت و مت سر رفت و گذاشت رفت آمریکا. جاش توی خانه خیلی خالیه!

چهارم، هر ۲ تا استادم دوباره دودر کردند و رفتند مسافرت و خدا می‌دونه کی بر می‌گردند. حالا من بدبخت هستم و پروژه‌ای که نمی‌دانم به کدام سمت قرار است برود.

پنجم این آخر هفته سطح پتانه‌ی خونم به شدت بالا رفته بود. از طرف دیگر با مت بانو، جعفر و سارا رفتیم کایاک سواری. خوب حدس زدنش کار سختی نیست که من چه خراب کاری‌ای کردم. اول، من و مت بانو توی یک کایاک دو نفره بودیم. از لحظه‌ای که وارد آب شدیم مت بانو سعی می‌کرد گربه را دم حجله بکشد و به نحوی من را متقاعد کنه که افتادن توی آب پر از عروس دریایی تجربه‌ی زیاد جالبی نیست. اما اتفاقی که نباید می‌‎افتاد افتاد   ولی سرنشین‌های یک قایق تفریحی نجات‌مان دادند و خوشبختانه توی ۸-۷ دقیقه شنای اجباری، هیچکدام از عروس‌های دریایی هوس نکردند ما را نیش بزند. فکر کردید داستان خرابکاری‌های من تمام شد؟ نخیر! مت بانوی غضبناک تصمیم گرفت راهش را از من جدا کنه و ما با ۲ تا کایاک تک‌نفره سفر را از اول شروع کردیم و من باز هم چپ کردم!  اما شما به نیمه‌ی پر لیوان نگاه کنید. مسئول کرایه‌ی ‌قایق‌ها می‌گفت: هر ماه شاید فقط یک نفر چپ کند، روی این حساب من به تنهایی توانستم برای ۲-۳ ماه خطر را از سر کایاک‌سواران کم تجربه دور کنم!

ششم، موبایل‌های پت و مت در مقابل آب نمک مقاوم نبودند و سوختند، برای ۴۸ ساعت ما سکوت رادیویی را تجربه کردیم.

هفتم، چند تا رستوران می‌شناسم که خوراک هشت‌پای خیلی خوب و ارزانی دارند! منتظر پایه‌ام تا برویم و به روح و جسم‌مان یک صفای حسابی بدهیم.

هشتم، سر پیری و معرکه‌گیری! حالا این یکی محرمانه است و نمی‌توانم بیشتر بنویسم ولی یک کاری خبرهایی است که صداش ۲۹ ام آبان همین امسال در می‌آید

اندر مصائب کار کردن در یک موضوع بین رشته‌ای و سر و کله زدن با دو فروند استاد نابغه با حوزه‌ها کاری متفاوت این است که امکان داره توی کامنت‌های مقاله‌ات که ۳ هفته‌ی پیش بهشون دادی، همچین جمله‌هایی را ببینی:

Why the following equations are part of the problem? What are all these equations?

خدایش ببینید من از دست این دو تا نابغه چه می‌کشم. کلا این روزها بنده اسباب تفریح و خنده‌ی دوستان شده‌ام.

Trillions from MAYAnMAYA on Vimeo.

چند ماهی است که زمینه‌ی کاری‌ام را عوض کرده‌ام. تا وقت بشود و در موردش بنویسم به ویدئوی بالا نگاه کنید تا حدی گویای قضیه هست

آقا یک ایده‌ای داشتیم ماه بود به خدا. یعنی یک چیزی من می‌گوم یک چیزی شما می‌شنوید. قرار بود پیاده‌سازیش کنم و بعد مقالش را بنویسم. و بعد هم که چاپ شد و  ملت مقاله‌ش را ‌خواندند همچین انگشت به دهان  بماندند که این نابغه تا به حال کجا بود، این خورشید تابان علم پس چرا نیومد توی دانشگاه ما توی آزمایشگاه ما کار کنه ( این آخریه را مخصوصا دلم می‌خواست که اون استاد بی‌ادب استنفورد که بهم پذیرش نداد می‌گفت). آره سرتون را درد نیارم یک هفته‌ای توی کف ایده‌ی خودم بودم. ۲-۳ روزی هم آمدم پیاده‌اش کنم و سرانجام امروز با دیدن نتایج دیدم که ای دل غافل، جواب این ایده‌ی ما با بهترین الگوریم موجود (از سال ۲۰۰۴) کاملا معادل از آب در در آمد

خلاصه این دفعه که نشد یک شبه و بدون دود چراغ خوردن آدم مشهوری بشویم و چشم ۳-۴ تا آدم خاص را از حسادت بترکونیم. خلاصه ما رفتیم تا ایده‌ی شهر آشوب بعدی را پیدا کنیم ...

فرض کنید N نفر از نخبگان گالیگولا (+ و +) (مثلا ۱۰ نفر) قرار است که در جلسه‌ی دیدار با نخبگان پادشاه گالیگولا شرکت کنند. قبل از ورود هر فرد به مکان جلسه به دستور پادشاه، کلاهی بر روی سر او گذاشته می‌شود، که این کلاه یا سفید است و یا سیاه. و البته این کلاه‌ گذاشتن‌ها به نحوی است که هیچ کس رنگ کلاه خودش را نمی‌فهمد ولی به همه‌ی افراد گفته می‌شود که حداقل یکی  از افراد حاضر در جلسه با کلاه سفید حاضر خواهد شد.

با وارد شدن افراد به جلسه، هر کسی می‌تواند با دیدن کلاه بقیه‌ی افراد رنگ کلاه بقیه را بفهمد، ولی به دستور پادشاه اجازه ندارد که کلاه خودش را  بردارد و ببیند، از بقیه هم نمی‌تواند بپرسد وگرنه پادشاه خدمتش می‌رسد!!

تا این‌جا مشکلی وجود ندارد. از حس فضولی که بگذریم، این نخبگان مشکلی با ندانستن رنگ کلاهشان نداشتند. ولی ناگهان پادشاه بلند ‌شد و ‌گفت که هر کس که رنگ کلاهش را نداند اعدام خواهد شد!! من چندین بار دستان مبارکم را به هم خواهم زد، پس از هر بار دست زدن هر کس رنگ کلاهش را فهمید، بگوید و جانش را نجات دهد.

همه حاضرین به هم نگاه می‌کنند ... پادشاه برای بار اول دستانش را بهم می‌کوبد، صدا در سالن می‌پیچد، و سکوت ...، چند دقیقه‌ی بعد بار دیگر پادشاه دستانش را بر روی هم می‌کوبد و ...چند باری که می‌گذرد ناگهان همه‌ی نخبگان، لبخند زنان بلند می‌شوند و پس از کسب اجازه از پادشاه رنگ کلاهشان را به درستی به پادشاه می‌گویند.

خوب به نظر شما این نخبگان چگونه رنگ کلاه‌های‌شان را فهمیدند و جانشان را نجات دادند؟
اگر شما هم میان جلسه بودید، چه اتفاقی می‌افتاد؟ شما هم نجات پیدا می‌کردید؟ و اصلا نجات پیدا کردن و یا نجات پیدا نکردن شما تاثیری در سرنوشت بقیه هم داشت؟

(مساله زیر یک مساله‌ی کلاسیک و نسبتا معروف است برای همین اگر قبلا هم آن را نشنیده‌اید، با کمی جستجو در وب می‌توانید آن را پیدا کنید D: )

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

۱-هر فرد شرکت کننده در جلسه به اندازه‌ی کافی باهوش است
۲- هر فرد شرکت کننده در جلسه می‌داند که سایر افراد شرکت کننده هم باهوش هستند.
۳- هر فرد شرکت کننده در جلسه می‌داند که سایر افراد شرکت کننده هم می دانند که سایر افراد شرکت کننده می‌دانند که سایر افراد شرکت کننده هم باهوش هستند
۴- هر فرد شرکت کننده در جلسه می‌داند که سایر افراد شرکت کننده هم می دانند که سایر افراد شرکت کننده می‌دانند که سایر افراد شرکت کننده می‌دانند هم باهوش هستند
۵- ...

آقا من گفته بودم که توی این دانشگاه جدید ۲ تا استاد دارم یک گل‌تر از دیگری. شرایطم شده عین یه بچه یتیم که افتاده دست ۲ تا نامادری. استاد اولیه که اصلا تحویلم نمی‌گیره و بالاخره بعد از یک ماه خود شیرینی، این هفته توانستم، یک جواب سلام ازش بگیرم. حالا یک نیمچه امیدی به اون استاد دومیه داشتم که امروز با گرفتن این ایمیل نقش بر آب شد.

Hi everyone,

... I shall be away from campus from Oct. 1 to Dec. 31, 2009, (with the possible exception of Oct. 29 and 30).  In October ...
Take care!

ostad dovomi.

کلا به نظر می‌رسه قراره که در ۴ سال آینده با باحال‌ترین استادهای روی زمین کار کنم.

خوب در قسمت قبلی، خیلی وارد خود بحث بهینه‌سازی نشدم و بیشتر به مقدمه و حاشیه‌ی کار پرداختم.  ولی امروز می‌خواهم کم کمک وارد بحث اصلی بشوم.

یک نکته‌ای که دفعه‌ی قبلی بیان آن فراموش شد، این بود که وقتی می‌گوییم «بهینه‌سازی»، منظورمان بهینه‌سازی الگوریتم نیست. بلکه من فرض کرده‌ام شما به دلیلی یک الگوریتم خاص را انتخاب کرده‌اید و حالا فقط تمایل دارید که آن را  به سریع‌ترین شکل ممکن پیاده‌سازی کنید. و یا اینکه یک تکه کد کند دارید و می‌خواهید سرعت اجرای آن را بهتر کنید.

موارد ۱ و ۲ را که در پست قبلی نوشته بودم. پس حالا می‌رویم سراغ مورد سوم:

۳- مشخص کردن گلوگاه‌های برنامه را می‌توان به عنوان گام بعدی برای هر گونه بهینه‌سازی بیان کرد. زیرا معمولا در هر برنامه یک یا چند نقطه‌ی گلوگاهی وجود دارد که باعث می‌شوند بهینه‌سازی سایر نقاط تاثیر چندانی بر عملکرد برنامه نداشته باشند.  به عنوان مثال، تصور کنید که برنامه‌ی شما ۲  تابع داشته باشد. که یکی ۹۸% زمان اجرا را به خود اختصاص بدهد و دیگری فقط ۲%. اگر شما حدس بزنید که با یک ساعت کلنجار رفتن با کد تابع اول می‌توانید آن را ۲ برابر سریع‌تر کنید و یا با صرف همین زمان بر روی تابع دوم  می‌توانید آن را ۲۰ برابر سریع‌تر کنید، ترجیح می‌دهید بر روی بهینه‌سازی کدام تابع کار کنید؟ ( بهینه‌سازی تابع اول زمان کلی را تفریبا نصف می‌کند ولی بهینه‌سازی تابع دوم تقریبا تاثیری روی زمان اجرای برنامه ندارد). وقتی شما یک تکه کد نوشته شده و آماده دارید دستور profiler در matlab می‌‌تواند بسیار کارگشا باشد. روش کار هم بسیار ساده است.

ابتدا در خط دستور بنویسید

>>profiler on
>>profiler clear

سپس برنامه‌ی خودتان را اجرا کنید و پس از اجرای آن بنویسید

>>profiler view

با اجرای این خط دستور، profiler سهم هر قسمت از برنامه  را از کل زمان مصرف شده  نشان می‌دهد و به راحتی می‌توان نقاط گلوگاهی برنامه را مشخص می‌کرد.

حالا که گلوگاه مشخص شد، باید دید چگونه می‌توان آن را بر طرف کرد.

۳- شاید ساده‌ترین و اولین گامی که باید در راستای تسریع برنامه‎‌های matlab برداشت، تخصیص حافظه به آرایه‌ها و ماتریس‌ها قبل از شروع محاسبات باشد که اصطلاحا preallocation نامیده می‌شود. در matlab این امکان وجود دارد که در حین اجرای برنامه، سایز آرایه‌ها و ماتریس‌ها آن را تغییر داد. ولی از آنجایی که این عمل خیلی بهینه نمی‌باشد و تغییر اندازه آرایه‌ها به صورت پویا و در حین اجرای برنامه  بسیار کند انجام می‌شود، انجام مکرر آن به راحتی می‌تواند تبدیل به گلوگاه اجرای برنامه شود.

۴- یکی از توانمندی‌های مهم matlab انجام محاسبات برداری و ماتریسی با سرعت و بازده بالا می‌باشد و بر خلاف این گونه محاسبات، اجرای حلقه‌ها (مانند for و یا while) و دسترسی به خانه‌های یک آرایه از طریق اندیس‌ به شدت کند و غیر بهینه می‌باشد. به همین دلیل با حذف دسترسی با اندیس به المان‌های آرایه‌ها و ماتریس‌ها و همچنین حذف حلقه‌ها و به جای آن‌ها پیاده سازی الگوریتم به کمک عملیات برداری می‌توان سرعت اجرا به مقدار قابل توجهی افزایش داد.

بسیاری از محاسبات برنامه را به راحتی می‌توان به صورت برداری و ماتریسی نوشت ولی برای تبدیل عده‌ای دیگر نیاز به لم‌ها و تکنیک‌هایی است که در قسمت بعدی این پست به تعدادی از آن‌ها اشاره خواهم کرد.

*قسمت بعدی احتمالا قسمت آخر این مجموعه می‌باشد.