یکی از چیزهایی که هر دانشجوی کامپیوتر در درس «برنامه سازی» یاد میگیرد توابع بازگشتی هستند. توابع بازگشتی اگرچه در ابتدا درکشان سخت به نظر می رسد اما به محض اینکه متوجه بشوید چطور از آن ها استفاده کنید و چطور مسایل را با آن ها حل کنید ناگهان به ابزارهای فوق العاده زیبا و قدرتمندی تبدیل می شوند که مسایل را تقریبا به طرز جادویی حل میکنند. در توابع بازگشتی ما یاد میگیریم که نیازی نیست مساله اصلی را کامل حل کنیم بلکه کافی است بدانیم اگر مساله را در مقیاس کوچکتر حل شده فرض کنیم چطور تکه هایش را به هم وصل کنیم و تمام!!
اما زندگی در این رویای شیرین دیری نمی پاید چون بزودی متوجه می شوید راه حل های بازگشتی با تمام زیبایی شان از لحاظ محاسباتی بسیار سنگین هستند بنابراین توصیه می کنند از آن ها اجتناب کنید. اما همه مسایل روش سر راستی برای حل ندارند به عبارتی ما فقط می توانیم به سادگی آن ها را به صورت بازگشتی حل کنیم.
مشکل اینجاست که در برنامه های بازگشتی شما بارها و بارها مساله ای را که قبلا حل کرده اید را حل میکنید چون اساسا برنامه بازگشتی یه روش حل بالا به پایین (top down) است. مثلا برای محاسبه عدد فیبوناچی ۵ ام ما نیاز داریم درختی مانند زیر را حل کنیم. فقط دقت کنید که قرمز ها محاسبات تکراری است که انجام می دهیم! به عبارتی اگر ما مثلا مقدار F3 را حساب کرده ایم دیگر لازم نیست که درخت آن را دوباره رو به پایین بسازیم.
با روش هایی مثل برنامه سازی پویا می توان این مساله را حل و فصل کنیم. در برنامه سازی پویا باید قدری خلاق تر بود و ساختمان داده هایی را نگه داشت تا نتایج میانی را حفظ کنند و دوباره آن ها محاسبه نکنیم. اما معمولا نتایج نوشتن برنامه به روش برنامه سازی پویا چیزی است که بسیار طولانی تر و عملا زیبایی کد اولیه را ندارد چون شما مجبورید مقدار زیادی کدهای اضافه برای نگه داشتن و کار با ساختمان داده ها نگه دارید. این کار عملا سودی از لحاظ نظری ندارد یعنی در عمل تنها کاری که ما می کنیم ولی باعث می شود کل زیبایی و سادگی کد را نابود کنیم نگه داشتن یک کش (cache) از مقادیر تابع برای ورودی هایی است که قبلا گرفته است. باید راه ساده تری بدون جراحی کل کد وجود داشته باشد!
باید گفت خوشبختانه این راه وجود دارد و در بسیاری از زبان های مدرن به شکل زیبایی می توان آن را انجام داد. اینجا فقط دو زبان Python و MATLAB را بررسی میکنیم.
بهترین و ساده ترین روش در پایتون برای حل مشکل فراخوانی های مجدد بدون تغییرات زیاد در کد استفاده از دکوراتور ها (decorator) هاست. (اگر در مورد آن ها چیزی نمی دانید این پست را بخوانید) برای این منظور یک دکوراتور به نام lru_cache را بالای تابع قرار می دهیم. هیچ تغییر دیگری لازم نیست. lru در واقع همان الگوریتم least recently used است. به این معنا که خروجی های تابع را نگه داشته تا زمانی که به اندازه حد کش می رسیم و سپس شروع به حذف می کنیم اما حذف بر اساس کمترین استفاده اخیر می شود.
کد بالا بدون دکوراتور بسیار بسیار زمانبر است در صورتی که با دکوراتور در چند صدم ثانیه حل می شود.
همانطور که می بینید lru_cache از functools گرفته شده است و پارامتری به اندازه سایز می گیرد. پیاده سازی خود lru_cache بسیار ساده است. در اینجا یک نسخه ساده آن را پیاده سازی می کنیم:
دقت کنید این همان lru_cache از functools نیست بلکه یک نسخه ساده شده آن است(بنابراین آرگومان maxsize را هم ندارد). همانطور که می بینید این دکوراتور یک تابع داخلی دارد که memoized_func نام دارد و تمام ورودی ها را پاس می دهد(*args). اولین چیزی که چک می شود این است که آرگومان ها در cache که یک دیکشنری است باشد. در واقع کش یک دیکشنری است که کلید هایش آرگومان هایی است که قبلا به تابع پاس داده شده و مقادیرش مقادیری است که تابع قبلا محاسبه کرده است. پس اگر قبلا محاسبه شده نیازی به محاسبه نیست و cache[args] برگشت داده می شود. در غیر این صورت مقدار تابع اصلی باید محاسبه شود و مقدار آن در cache ذخیره شود. این مکانیزم بسیار ساده در عین حال بسیار موثر هم هست.
