به خاطر سپاری (رایانش)

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

ریشه‌شناسی

اصطلاح مموایز کردن توسط Donald Michie در سال ۱۹۶۸ ابداع شده بود واز کلمه لاتین memorandum(به یاد داشتن) برگرفته شده‌است و بنابراین دربردارندهٔ معنی برگرداندن(نتایج) یک تابع به چیزی است تا به یاد سپرده شود. در حالی که مموایز کردن ممکن است با به memorization اشتباه گرفته شود (به خاطر به اشتراک‌گذاری ریشه مشترک)، مموایز کردن معنی خاصی در رایانش دارد.

بررسی اجمالی

یک تابع به خاطر سپاری نتایجی را که با مجموعه‌هایی از ورودی‌های خاص مرتبط است «به خاطر می‌سپارد» . فراخوانی‌های بعدی با ورودی‌های به خاطر سپرده شده نتایج را به جای محاسبه مجدد آن برمی‌گرداند، بنابراین هزینه اولیه فراخوانی با پارامترهای داده شده را از همه ی (به جز اولین) فراخوانی های تابع با آن پارامترها حذف می کند. مجموعه‌ ی ارتباطات به خاطر سپرده شده ممکن است یک مجموعه با اندازه ثابت باشد که توسط الگوریتم‌های جایگزینی یا یک مجموعه ثابت کنترل شود که بستگی به طبیعت تابع و کاربردهای آن دارد. یک تابع در صورتی می تواند به خاطر سپاری شود که به‌طور ارجاعی شفاف باشد؛ که فقط در صورتی ممکن است که، فراخوانی تابع دقیقا اثری مشابه با جایگزینی فراخوانی تابع با مقدار بازگشتی آن داشته باشد (اگرچه، موارد استثناء خاصی نیز برای این محدودیت وجود دارد). در حالیکه مموایز کردن با جداول مراجعه مرتبط است، چون اغلب از چنین جداولی در اجرایش استفاده می‌کند، اما مموایز کردن فضای کش نتایج اش را بطور شفاف و در حین اجرا، در صورت نیاز، و نه پیشاپیش، پر می‌کند.

مموایز کردن یک وسیله برای پایین آوردن هزینه زمان تابع در عوض افزایش هزینه فضا است؛ که به این معنی است که توابع مموایز شده برای افزایش سرعت در عوض استفادهٔ بیشتر از حافظه کامپیوتر بهینه می‌شوند. «هزینه» فضا/زمان الگوریتم‌ها اسم خاصی در رایانش به نام پیچیدگی محاسباتی دارند. همهٔ توابع یک پیچیدگی محاسباتی در زمان (یعنی: زمانی که برای اجرا لازم دارند) و در فضا دارند.

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

function factorial (n is a non-negative integer)
 if n is 0 then
 return 1 [by the convention that 0! = 1]
 else
 return factorial(n – 1) times n [recursively invoke factorial
                                        with the parameter 1 less than n]
 end if
end function

برای هر عدد صحیح n به‌طوری‌که n≥۰, نتیجه پایانی تابع فاکتوریل غیرمتغیر است. اگر به (x = factorial(3 استناد داده شده باشد، نتیجه طوری است که x همیشه برابر با مقدار ۶ خواهد بود. یک نسخه غیر مموایز از مورد بالا، با طبیعت الگوریتم بازگشتی درگیر داده شده، احتیاج به فراخوانی‌های n + 1 فاکتوریل دارد تا به نتیجه بالا برسد و هرکدام از این فراخوانیها، به نوبه خود، هزینه‌ای مرتبط در زمان می‌گیرد تا تابع مقدار محاسبه شده را بازگرداند. بسته به ماشین، این نتیجه جمع موارد زیر خواهد بود:

هزینه راه اندازی قالب فراخوانی پشته کاربردی
هزینه مقایسه n تا ۰
هزینه کم کردن ۱ از n
هزینه راه اندازی فراخوانی قالب پشته بازگشتی (مثل بالا)
هزینه ضرب نتیجه فراخوانی بازگشتی به فاکتوریل به وسیلهٔ n
هزینه ذخیره کردن نتیجه بازگشت طوری‌که ممکن است به وسیلهٔ محتوای فراخوانی مورد استفاده واقع شود.

در یک اجرای غیرمموایز، هر فراخوانی سطح بالا به فاکتوریل شامل هزینه انباشته مراحل ۲ تا ۶ متناسب با مقدار n اولیه است.

یک نسخه مموایز شده از تابع فاکتوریل به صورت پایین است:

function factorial (n is a non-negative integer)
 if n is 0 then
 return 1 [by the convention that 0! = 1]
 else if n is in lookup-table then
 return lookup-table-value-for-n
 else
 let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
 store x in lookup-table in the n slot [remember the result of n! for later]
 return x
 end if
end function

دراین مثال خاص، اگر فاکتوریل در ابتدا با ۵ فراخوانی شود و سپس بعداً باهر مقداری کم‌تر یا برابر با ۵ فراخوانی شود، آن مقادیر بازگشتی همچنین مموایز خواهند شد، چون فاکتوریل به صورت بازگشتی با مقادیر۰و۱و۲و۳و۴و۵ فراخوانی خواهند شد، و مقادیر بازگشتی برای هر کدام از آن‌ها ذخیره خواند بود. اگر آن بعداً با یک شماره بزرگتر از ۵، نظیر ۷فراخوانی شود، فقط ۲ فراخوانی بازگشتی(۶و۷)انجام می‌شود و نتیجه !۵ از قبل ذخیره شده‌است. در این روش، مموایز کردن به یک تابع اجازه می‌دهد که از نظر زمانی بیشتر بهینه شود مادامی که بیشتر فراخوانی می‌شود، بنابراین منتهی به یک افزایش سرعت نهایی می‌شود.

بعضی از دیگر ملاحظات

مموایزکردن اتوماتیک

اگر چه ممکن است مموایز کردن به توابع به صورت داخلی و واضح به وسیلهٔ یک برنامه‌نویس کامپیوتر، بیسار شبیه به روش اشاره شده در بالا که برای اجرای فاکتوریل بود، اضافه شود، توابع شفاف ارجاعی ممکن است به صورت اتوماتیک و خارجی مموایز شوند. تکنیک‌هایی که توسط Peter Norvig به کار گرفته شده‌اند کاربردهایی نه تنها در LISP مرسوم (زبانی که در آن در مقاله اش مموایزکردن اتوماتیک رانشان داد)، بلکه در تعداد زیادی از زبان‌های برنامه‌نویسی دیگر دارد. کاربردهای مموایز اتوماتیک به‌طور رسمی در مطالعات دوباره‌نویسی اصطلاح و هوش مصنوعی جستجو شده‌اند.

در زبان‌های برنامه‌نویسی جایی که توابع اشیاء کلاس پایه هستند (نظیر Lua, Python, یا Perl)، مموایز کردن اتوماتیک می‌تواند توسط جایگزینی (در زمان اجرا) یک تابع با مقدار محاسبه شده اش وقتی که یک مقدار از محاسبه به ازای پازامترهای داده شده به دست آمد، اجرا شود. تابعی که این جایگزینی مقدار برای تابع شی را انجام می‌دهد می‌تواند به‌طور کلی هر تابع ارجاعی شفافی را بسته‌بندی کند. شبه کد پایین را در نظربگیرید:(جایی که فرض شده توابع از مقادیر کلاس پایه هستند)

 function memoized-call
 if F has no attached array values then
 allocate an associative array called values;
 attach values to F;
 end if;

 if F.values[arguments] is empty then
 F.values[arguments] = F(arguments);
 end if;

 return F.values[arguments];
 end function

به منظور فراخوانی نسخه مموایز شده اتوماتیک فاکتوریل با استفاده از استراتژی بالا، به جای فراخوانی مستقیم فاکتوریل، کد فراخوانی مموایز ((factorial(n) را فراخوانی می‌کند. همچنین فراخوانی ای درابتدا چک می‌کند تا ببیند که آیا یک آرایه نگه دارنده برای ذخیره‌سازی نتایج اختصاص داده شده‌است، وگرنه، آن آرایه را الحاق می‌کند. اگر هیچ آرایه‌ای در مکان [values [arguments نباشد(جایی که آرگمان‌ها به عنوان کلید آرایه شرکت پذیر استفاده شده‌اند)ویک فراخوانی واقعی به فاکتوریل با آرگمان‌های فراهم شده درست می‌شود. درآخر، ورودی در آرایه در موقعیت کلید به فراخواننده بازمی‌گردد. استراتژی بالا به بسته‌بندی واضح در هر فراخوانی به یک تابع که می‌خواهد مموایز شود احتیاج دارد. در زبان‌هایی که به بستن اجازه می‌دهند مموایز کردن می‌تواند به‌طور ضمنی توسط یک کارخانه عمل‌کننده که یک شی تابع مموایز شده را بسته‌بندی می‌کند، تحت تأثیر قرار بگیرد. در شبه کد،این مورد می‌تواند به این صورت بیان شود:

function construct-memoized-functor

   allocate a function object called memoized-version;

   let memoized-version(arguments) be
      if self has no attached array values then [self is a reference to this object]
 allocate an associative array called values;
 attach values to self;
 end if;

 if self.values[arguments] is empty then
 self.values[arguments] = F(arguments);
 end if;

 return self.values[arguments];
 end let;

 return memoized-version;
end function

به جای فراخوانی فاکتوریل، یک شی جدید تابع memfact به صورت مقابل ایجاد می‌شود.

memfct = construct-memoized- functor factorial

مثال بالا فرض می‌کند که تابع فاکتوریل قبل از فراخوانی به تابع construct-memoized-functor ایجاد شده‌است. از این جا به بعد، memfact(n) هر وقت فاکتوریل n مورد نیاز باشد، فراخوانی می‌شود. در زبان‌هایی نظیر Lua، تکنیک‌های پخته‌تر بیشتری وجود دارند که به یک تابع اجازه می‌دهند تا با یک مقدار جدید با اسم مشابه جایگزین شود اجازه خواهند داد که:

factorial = construct-memoized-functor factorial

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

function construct-memoized-functor

 allocate a function object called memoized-version;

 let memoized-version(arguments) be
 if self has no attached array values then [self is a reference to this object]
 allocate an associative array called values;
 attach values to self;
 allocate a new function object called alias;
 attach alias to self; [for later ability to invoke F indirectly]
 self.alias = F;
 end if;

 if self.values[arguments] is empty then
 self.values[arguments] = self.alias(arguments); [not a direct call to F]
 end if;

 return self.values[arguments];
 end let;

 return memoized-version;
end function

(توجه کنید: بعضی از قدم‌هایی که در بالا نشان داده شد ممکن است به‌طور ضمنی به وسیلهٔ زبان پیاده‌سازی اداره شوند و برای نشان دادن مهیا شده‌اند)

منابع

↑ Norvig, Peter (1991). "Techniques for Automatic Memoization with Applications to Context-Free Parsing". Computational Linguistics. 17 (1): 91–98.
↑ Warren, David. "Tabling and Datalog Programming". Retrieved 29 May 2009.
↑ Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19–22, 1968.

پیوند به بیرون

groovy.lang.Closure#memoize() – Memoize is a Groovy 1.8 language feature.
Memoize – Memoize is a small library, written by Tim Bradshaw, for performing memoization in لیسپ معمولی.
IncPy – A custom Python interpreter that performs automatic memoization (with no required user annotations)
Dave Herman's Macros for defining memoized procedures in Racket.
Memoize.pm – a Perl module that implements memoized functions.
Java memoization – an example in Java using dynamic proxy classes to create a generic memoization pattern.
Memoization in C++ – although C++ doesn't support first-class functions, here is a toolkit that supports automated memoization (via pre-processing).
C-Memo – Generic memoization library for C, implemented using pre-processor function wrapper macros.
Tek271 Memoizer – Open source Java memoizer using annotations and pluggable cache implementations.
memoize – A Ruby module that implements memoized methods.
Python memoization – A Python example of memoization.
OCaml memoization – Implemented as a Camlp4 syntax extension.
Memoization in Lua – Two example implementations of a general memoize function in Lua.
Memoization in Mathematica – Memoization and limited memoization in متمتیکا.
Memoization in Javascript – Extending the Function prototype in جاوااسکریپت.
Memoization in Javascript – Examples of memoization in javascript using own caching mechanism and using the YUI library
X-SAIGA – eXecutable SpecificAtIons of GrAmmars. Contains publications related to top-down parsing algorithm that supports left-recursion and ambiguity in polynomial time and space.
Memoization in Scheme – A Scheme example of memoization on a class webpage.
Memoization in Combinatory Logic – A web service to reduce Combinatory Logic while memoizing every step in a database.
MbCache – Cache method results in .NET.

[Norvig1991-1] Norvig, Peter (1991). "Techniques for Automatic Memoization with Applications to Context-Free Parsing". Computational Linguistics. 17 (1): 91–98.

[Warren1999-2] Warren, David. "Tabling and Datalog Programming". Retrieved 29 May 2009.

[Michie1968-3] Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19–22, 1968.