- یه پشته بساز.
- صدا زدن تابع رو پوش۱ معنی کن.
- برگردوندن مقدار توسط تابع رو پاپ۲ معنی کن.
- محاسبات اصلی رو بذار داخل یه حلقه و اول هر حلقه، مقادیر مورد نیازت رو از پشته پاپ کن.
شروع داستان!
اما داستان این پست از اونجا شروع میشه که در متلب پشته نداریم! :) اما نوع داده‌ی مجردش رو که داریم :دی پشته، همونطور که احتمالا دیگه همه میدونن، یه ساختمان داده‌ی LIFO۳ئه: «هر کی آخر اومد، اول میره». اول ببینم که من چیکار میخوام بکنم؟
- داده‌هایی که من باهاشون کار میکنم، بردارهایی مثل [۲ ۳ ۴ ۰ ۹ ۸] هستن.
- تابعی که من باهاش کار میکنم، این بردار رو با یه درایه‌ی دیگه پاس میده به خودش و تا زمانی که شرط توقف که مشخص هست فعال نشه، این کار ادامه پیدا میکنه. مثلا داخل تابع اینطور عبارتی رو دارم:
myFunc([8 9 0 4 3 2], 11);و این میاد برداری که بهش دادم رو با یه سری دنگ و فنگا به یه بردار بزرگتر که با توجه به ۱۱ بدست میاد، توسیع میده، مثلا خروجی تابع من اینطور چیزی میشه: [۷ ۲ ۳ ۴ ۰ ۹ ۸].
بنابراین من یه چیزی میخوام که
- بتونم بردارهای با طول متفاوت -و احتمالا هر چیز دیگه‌ای- رو بریزم توش (چون بردارهایی که دارم باهاشون کار میکنم، طول مشخصی ندارن)،
- تعداد عنصرهایی که میتونه بپذیره متغیر باشه (چون مشخص نیست که تابع من کی به شرط توقفش برسه، ممکنه با فرستادن مثلا ۳ بردار این اتفاق بیفته، ممکنه با فرستادن ۳۷تا، بنابراین باید بتونه عمل پوش رو به درستی هندل کنه)،
- بتونم ازش داده بردارم و داده رو حذف کنم (برای عمل پاپ).
این مشخصاتی که در بالا دادم، فقط به یه چیز در متلب میخوره: «سلول» یا Cell.
سه‌لول
سلول‌ها موجوداتی در متلب هستن که رفتاری مثل آرایه‌ها دارن، اما هر نوع داده‌ای رو می‌پذیرن. مثلا من یه سلول میسازم که اول اسم خودم رو میریزم توش (یه رشته)، بعد سنم رو (یه عدد صحیح) و بعد عدد پی رو (به عنوان یه عدد با ممیز شناور). نکته اینه که مثل ماتریس‌ها یا بردارها در متلب، سلول هم متناسب با نیاز من بزرگ میشه:
>> C{1} = 'Meysam'; >> C{2} = 25; >> C{3} = pi; >> C C = 'Meysam' [25] [3.1416]لول۱) برای دسترسی به محتوای یک موقعیت از سلول، از آکولاد استفاده میشه. مثلا من میخوام ببینم در موقعیت سوم سلولی که در بالا ساختم چی وجود داره:
>> C{3} ans = 3.1416یا میخوام محتوای سلول دوم رو بذارم بردار [۳ ۴ ۱]:
>> C{2} = [1 4 3] C = 'Meysam' [1x3 double] [3.1416] >> C{2} ans = 1 4 3یا یه عنصر جدید بهش اضافه کنم و بعد هم مقدارش رو میریزم داخل متغیر a و نوعش رو هم می‌بینیم:
>> C{4} = 'You are myself!, hum?' C = 'Meysam' [1x3 double] [3.1416] [1x21 char] >> a = C{4} a = You are myself!, hum? >> whos a Name Size Bytes Class Attributes a 1x21 42 charلول۲) با استفاده از عملگر پرانتز، میتونیم به خونه‌ی یک سلول دست پیدا کنیم. در نگاه اول، لول۱ و لول۲ تفاوتشون شاید مشخص نباشه، اجازه میخوام یه مثال ملموس بزنم! :{ فرض کنیم ما یه آپارتمان داریم که هر واحدش یه شماره داره، آقای آکولاد ازمون یه شماره میگیره و میره محتویات داخل اون واحد رو بهمون نشون میده، یعنی چیزی که آکولاد برمیگردونه، دقیقا و فقط، محتویات داخل واحده! برای مثال اگه داخل واحد ۵ یه آدم باشه و یه ساعت، آکولاد با گرفتن عدد ۵، اون آدم و ساعت رو برمیگردونه. اما خانم پرانتز، با دریافت یه شماره، میره اون واحد رو از بیخ برمیداره و میاره. مثلا اگه همون عدد پنج رو بهش بدیم، بهمون یه واحد برمیگردونه که داخل اون یه آدم و یه ساعت هست! مثلا از سلولی که ما در بالا ساختیم، من با عملگر پرانتز ۴مین موقعیت سلول رو میریزم تو متغیر b و نوعش رو هم نشون میدم:
>> b = C(4) b = 'You are myself!, hum?' >> whos b Name Size Bytes Class Attributes b 1x1 154 cellفکر کنم با این مثال، تفاوت کاملا مشخص باشه دیگه، در مثال بالاتر، وقتی محتوای موقعیت چهارم سلول رو با آکولاد ریختیم داخل متغیر a، متغیر a حاوی یک رشته شد، اما وقتی موقعیت چهارم رو با پرانتز ریختیم داخل متغیر b، متغیر b یه سلول شد که داخلش یه رشته‌ست. هوم؟ :دی
لول۳) طول یک سلول رو میشه با تابع
length بدست آورد. مثلا برای سلول بالا محتویات رو می‌بینیم و طولش رو بدست میاریم:>> C C = 'Meysam' [1x3 double] [3.1416] [1x21 char] >> length(C) ans = 4همینجا میشه نتیجه گرفت که
length، همیشه بالاترین موقعیت سلول رو نشون میده. برای مثال من آخرین موقعیت سلول رو نشون میدم و بعد یه موقعیت جدید ایجاد میکنم و داخلش یه بردار میریزم و در نهایت باز آخرین موقعیت سلول رو نشون میدم:>> C{length(C)} ans = You are myself!, hum? >> C{5} = [10 20 3 15 1000 60 16] C = 'Meysam' [1x3 double] [3.1416] [1x21 char] [1x7 double] >> C{length(C)} ans = 10 20 3 15 1000 60 16یا من از سلول موقعیت دومش رو حذف میکنم و دوباره طولش رو می‌گیریم. برای حذف کردن یک موقعیت از سلول، کافیه اون خونه رو خالی کنیم (دقت کنیم که اون خونه و نه محتوای اون خونه!). پس همونطور که اول پاراگراف خواستم، اول می‌بینم که داخل سلول چی دارم، بعد دومین داده‌ی سلول رو حذف میکنم و در نهایت سلولی که بروزشده رو می‌بینم و طولش رو می‌گیرم:
>> C C = 'Meysam' [1x3 double] [3.1416] [1x21 char] [1x7 double] >> C(2) = [] C = 'Meysam' [3.1416] [1x21 char] [1x7 double] >> length(C) ans = 4تا اینجا هر چی که برای ساختن پشته نیاز بود رو داریم پس! معمولا، اگه یه جایی بخوام متلب رو برای کسی بگم، اینجا که میرسه، احتمالش هست که بخواد سرم رو از تنم جدا کنه، اینه که معمولا اینطور جاها فضا باید تلطیف شه :دی اینه که باید اینجا ذکر کنم، این لول‌هایی که گفتم (لول۱ و لول۲ و لول۳)، Level خونده نمیشه، در حقیقت همون LOL خارجیا هست به معنی همون هارهارهار خودمون :)). (بی‌مزه بود! قبول دارم! :دی).
پیاده‌سازی!
فکر نمیکنم دیگه چیزی برا گفتن مونده باشه :دی برای ساختن استک، کافیه دوتا عملش رو بنویسیم، اول پوش! برای پوش کردن داخل استک، کافیه طول سلول رو بگیریم و در یک موقعیت بالاتر از اون، محتوا رو وارد کنیم. مثلا اگه داخل سلول ۶تا داده داریم، باید داده‌ی جدید رو در موقعیت هفتم وارد کرد. مثلا یه سلول به اسم stack می‌سازیم، چندتا بردار رو پوش میکنم و بعد از هر وارد کردن محتوا رو نشون میدم:
>> stack = {} stack = {} >> stack{length(stack)+1} = [1 1 1] stack = [1x3 double] >> stack{length(stack)+1} = [2 2 2] stack = [1x3 double] [1x3 double] >> stack{length(stack)+1} = [3 3 3] stack = [1x3 double] [1x3 double] [1x3 double] >> stack{length(stack)+1} = 'Mosabegheye Mahale :D'; stack = [1x3 double] [1x3 double] [1x3 double] [1x21 char]
این از این! میمونه پاپ! پاپ کردن هم که یعنی محتوای آخرین موقعیت رو بردار و اون موقعیت رو از بین ببر. پس کافیه اول با عملگر آکولاد بالاترین محتوا رو بریزم تو یه متغیر و بالاترین موقعیت رو خالی کنم. برای مثال، اول سلول stack که در مثال بالا ساخته بودم رو نشون میدم، بعدش دوتا عنصر رو پاپ می‌کنیم و بعد از هر پاپ، محتوایی که پاپ شده با سلول بروزشده رو نشون میدم:
>> stack stack = [1x3 double] [1x3 double] [1x3 double] [1x21 char] >> a1 = stack{length(stack)}; >> stack(length(stack)) = []; >> a1 a1 = Mosabegheye Mahale :D >> stack stack = [1x3 double] [1x3 double] [1x3 double] >> a2 = stack{length(stack)}; >> stack(length(stack)) = []; >> a2 a2 = 3 3 3 >> stack stack = [1x3 double] [1x3 double]
خب کارمون تمومه! ولی شیک‌تر میشه اگه برا پوش و پاپ تابع بنویسیم، هوم؟ :] این تابع پوش که یه سلول به عنوان استک و یه داده برای ورود به استک رو میگیره و استک بروزشده رو برمیگردونه:
function stack = pushStack(stack, d) % Get stack, push data d into it and return updated stack. if(~iscell(stack)) error('First parameter must have cell type.'); end
stack{length(stack)+1} = d; end
برا تابع بالا، تنها چیزی که برای جلوگیری از خطا چک می‌کنیم، اینه که پارامتر اول، حتما یه سلول باشه. مسلما برای کامل شدن این تابع، خیلی چیزهای دیگه میتونست چک شه، ولی به نظر من نیاز نیست. تنها اشکالی که من به صورت غیرعمدی میتونم مرتکب شم اینه که یه داده‌ی غیرسلولی رو به تابع پاس بدم، البته این کار میتونه باعث تولید خطا شه، ولی یه یادآوری کوچیک ضرر نداره، برای باقی موارد ممکن هم که نیازی نیست از نظر من! این یه برنامه‌ی امنیتی نیست :دی و ثانیا، کم شدن زمان اجرا، در حد چند ده هزارم ثانیه هم، برای من لذت‌بخش‌ه۴ :دی.
و این هم تابع پاپ که استک رو میگیره، بالاترین موقعیت استک رو پاپ میکنه و در نهایت استک بروزشده و داده‌ی پاپ‌شده رو برمیگردونه:
function [stack, d] = popStack(stack) % Get top data of stack and update structure. if(isempty(stack)) error('Stack is empty.'); end d = stack{length(stack)}; stack(length(stack)) = []; end
و یک نمونه‌ی اجرا این دوتا تابع:
>> stack = pushStack({}, [1]) stack = [1] >> stack = pushStack(stack, [2 3]) stack = [1] [1x2 double] >> stack = pushStack(stack, [4 5 6]) stack = [1] [1x2 double] [1x3 double] >> [stack, data1] = popStack(stack) stack = [1] [1x2 double] data1 = 4 5 6 >> [stack, data2] = popStack(stack) stack = [1] data2 = 2 3
پ.ن ۱: عکس عنوان، ترکیب دوتا عکس‌ه که از ویکی‌پدیا برشون داشتم، این لینک و این لینک.
پ.ن ۲: اینایی که تو فرانسه به دنیا اومدن و تو انگلیس تحصیل کردن و بعد از چند سال کار کردن تو مالزی، اومدن ایران، معادل‌های فارسی بیشتری برای خیلی از کلمات تخصصی میدونن تا منی که از اینطرف تا کرمان و از اونطرف تا مشهد اونورتر نرفتم! :دی
۱ و ۲: پوش و پاپ، فارسی‌شون چی میشه؟ :دی
۳. Last Input First Output.
۴. در یک بحث، فرود نکته‌ی خیلی خوبی در این مورد رو بهم تذکر داد. اون هم اینکه در قبال این میکرو اپتیمایزها، چی دریافت میشه؟. این نکته درسته، احتمالا اگه من میخواستم این برنامه رو با پایتون یا سی++ بنویسم و اون رو برای کاربرد بفروشم یا منتشر کنم، به جای توجه کردن به ده‌هزارم‌ثانیه‌ها، برنامه رو جوری می‌نوشتم که بعدها در استفاده از اون، خودم یا فرد دیگه‌ای، ساعت‌ها وقتش رو صرف اشکال‌زدایی ناشی از اصرار بیش از حد بر این بهینه‌سازی‌ها نکنه.
و
یه نگاه به رشتتون بکنید و مطمئن بشید که باز هم برنامه رو بهینه مینوشتید اما در کنار تلاش میکردید که خطا هم نده :)