درک Memoization در جاوا اسکریپت و تایپ اسکریپت — به زبان ساده

۲۱۵ بازدید
آخرین به‌روزرسانی: ۰۷ شهریور ۱۴۰۲
زمان مطالعه: ۴ دقیقه
درک Memoization در جاوا اسکریپت و تایپ اسکریپت — به زبان ساده

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

Memoization چیست؟

بر اساس تعریف ویکی‌پدیا:

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

Memoization یک تکنیک برنامه‌نویسی است که امکان کاهش هزینه زمانی تابع را در برابر افزایش هزینه فضایی آن فراهم می‌سازد. یعنی تابع‌هایی که Memoize می‌شوند، در ازای اشغال فضای حافظه، عملکرد سریع‌تری ارائه می‌کنند.

توجه کنید که Memoization تنها در مورد «تابع‌های محض» (pure functions) قابل اجرا است. از این رو ابتدا باید با مفهوم تابع محض آشنا شویم. توجه کنید که گاهی از عبارت تابع خالص نیز استفاده می‌شود که مقصود یکی است. در انیمیشن زیر نتیجه‌هایی اعمال Memoization را روی یک کد می‌بینید:

Memoization

تابع محض چیست؟

تابع محض به تابعی گفته می‌شود که در صورت یکسان بودن آرگومان‌ها، همواره مقدار یکسانی را بازگشت دهد. برای نمونه تابع‌های زیر غیر محض هستند:

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

تابع محض تابعی است که هیچ عارضه جانبی مانند موارد زیر در اپلیکیشن ایجاد نمی‌کند:

  • تغییر دادن داده‌ها یا حالت اپلیکیشن
  • درخواست شبکه
  • درخواست پایگاه داده یا فایل
  • گرفتن ورودی کاربر
  • کوئری زدن به DOM

مزیت‌های تابع محض

تابع‌های محض در برنامه‌نویسی چند مزیت دارند. با این حال، این توابع صرفاً در برنامه‌نویسی مورد استفاده قرار نمی‌گیرند. مزیت‌های اصلی آن‌ها به شرح زیر است:

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

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

مثالی از تابع‌های محض

تابع‌های بازگشتی غالباً از تابع‌های محض استفاده می‌کنند. کلاسیک‌ترین مسئله بازگشتی، محاسبه فاکتوریل است.

Memoization

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

Memoization

مثال جالب دیگر از تابع‌های محض به صورت زیر است:

Memoization

Memoization در تابع‌های بازگشتی

Memoization یک تکنیک برنامه‌نویسی است که به ما امکان می‌دهد از محاسبه مجدد مقدار تابع محض خودداری کنیم. بدین ترتیب تابع محض زمانی که مقدار ورودی یکسان باشد، همان مقدار را بازگشت می‌دهد. بنابراین مقدار بازگشتی می‌تواند با استفاده از هر نوع کش مانند یک map یا آرایه در سیستم ذخیره شود.

بدین ترتیب اگر مقدار factorial(1) را محاسبه کنید می‌توانید مقدار بازگشتی 1 را ذخیره کنید و در هر تکرار این عمل قابل اجرا است. بدین نحو زمانی که فاکتوریل 100 را محاسبه می‌کنید، در بار اول شاید زمانی طول بکشد، اما در دفعه دوم و دفعات دیگر زمان محاسبه کاهش می‌یابد.

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

مثالی از Memoization به صورت کد عملی

در این بخش شیوه پیاده‌سازی Memoization را با استفاده از closure و الگوی decorator در جاوا اسکریپت بررسی می‌کنیم. الگوی decorator با بهره‌گیری از ترکیب‌بندی به جای سلسله‌مراتب، امکان افزودن قابلیت‌های جدیدی را به هر پروژه در زمان اجرا فراهم می‌سازد. هدف این الگو جلوگیری از ایجاد سلسله مراتب کلاسی از قابلیت‌ها است. یک پیاده‌سازی ساده از دکوراتور memoize در جاوا اسکریپت به صورت زیر است:

Memoization

  1. کش را تعریف می‌کنیم که نتیجه اجرای کد در آن ذخیره می‌شود. ما از یک شیء به صورت map برای ذخیره کردن نتیجه بهره می‌گیریم.
  2. دکوراتور یک تابع جدید بازگشت می‌دهد که همان رفتار تابع اصلی را دارد، اما memoization پیاده‌سازی شده است.
  3. کلید نگاشت key-value با استفاده از stringify ایجاد شده و آرگومان‌ها از تابع اصلی می‌آیند.
  4. result تابع جدید به صورت زیر خواهد بود:
    1. اجرای تابع اصلی fn(...args) در مواردی که چیزی در کش ذخیره نشده باشد.
    2. ذخیره مقدار در کش در صورت محاسبه قبلی
  5. result بازگشت می‌یابد.

شیوه استفاده از دکوراتور Memoize شده چگونه است؟

روش استفاده از این دکوراتور در جاوا اسکریپت بسیار آسان است:

Memoization

در این مثال، تابع add تابع اصلی بدون memoization و تابع addMemoized تابع جدیدی است که قابلیت جدید یعنی memoization را با استفاده از الگوی دکوراتور به دست آورده است.

دموی واقعی استفاده از Memoization

در این بخش می‌خواهیم یک دموی واقعی از طرز کار Memoization نمایش دهیم. یک الگوریتم پیچیده را تصور کنید که نشان می‌دهد آیا یک array یک مقدار یکتا دارد یا نه، اما به طرز بسیار بدی برنامه‌نویسی شده است:

Memoization

در بخش بعدی کد اصلی اجرا می‌شود و سپس کد با استفاده از memoization اجرا می‌شود، و زمان استفاده شده از سوی هر تابع مقایسه می‌شود. باید یادآوری کنیم که کد اصلی تغییر نیافته است، بلکه قابلیت memoization اضافه شده است.

تابع زیر برای اندازه‌گیری زمان صرف شده در هر اجرا مورد استفاده قرار می‌گیرد.

Memoization

آرایه‌ها در ابتدای اسکریپت ایجاد شده‌اند:

Memoization

و در نهایت زمانی که کاربر روی یک دکمه کلیک می‌کند، تابع‌ها اجرا می‌شوند.

بدون استفاده از Memoization

Memoization

با بهره‌گیری از Memoization

Memoization

نتیجه در انیمیشن زیر نمایش یافته است:

Memoization

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
better-programming
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *