مموایز کردن

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از ممویز)
پرش به: ناوبری، جستجو

الگو:مموایز با حفظ کردن اشتباه نشود.

در محاسبات، مموایز کردن یک تکنینک بهینه سازی است که در درجه اول برای سرعت بخشبدن به برنامه های کامپیوتری به وسیله ی فراخوانی های تابع است تا از تکرار محاسبات برروی نتایجی که قبلاً محاسبه شده بودند جلوگیری شود. مموایز کردن همچنین در میان متن های دیگر (و به منظور هایی به غیر از به دست آوردن سرعت)، مانند، در تجزیه بازگشتی متقابل کاهش یابنده[۱]، در یک الگوریتم کلی تجزیه بالا به پایین که ابهام راتطبیق می دهد و بازگشتی باقی‌مانده در فضا و زمان چندجمله ای[۲][۳]. اگرچه مطابق با کش کردن، مموایز کردن اشاره به به یک مورد خاص از این بهینه سازی دارد، تمایز میان این با شکل های کش نظیر بافر کردن یا جایگزینی صفحه قائل می شود.در محتوای بعضی از زبان های برنامه نویسی منطقی، مموایز کردن همچنین به نام جدول سازی نامیده می شود. به جدول سازی نگاهی بیندازید.[۴]

ریشه‌شناسی[ویرایش]

اصطلاح مموایز کردن توسط Donald Michie در سال 1968 ابداع شده بود [۵] واز کلمه لاتین memorandum(به یاد داشتن) برگرفته شده است و بنابراین دربردارنده ی معنی برگرداندن(نتایج ) یک تابع به چیزی است تا به یاد سپرده شود. در حالی که مموایز کردن ممکن است با به خاطر سپاری اشتباه گرفته شود(به خاطر به اشتراک گذاری ریشه مشترک)، مموایز کردن معنی خاصی در محاسبات دارد.

بررسی اجمالی[ویرایش]

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

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

اگرچه یک تجارت اتفاق می افتد(یعنی:فضای مورد مصرف زمان حاصل شده است)واین امر متفاوت است با دیگر بهینه سازی ها که تجارت فضا-زمان را مورد استفاده قرار می دهند،نظیر کاهش قدرت،که درآن مموایز کردن یک زمان اجرا به جای بهینه سازی زمان کامپایل است.علاوه بر این،کاهش قدرت به طور بالقوه، یک عملیات هزینه بر نظیر ضرب را با یک عملیات کم هزینه تر نظیر جمع جایگزین می کند، و نتایج در ذخیره ها می توانند بسیار وابسته به ماشین ،غیرقابل حمل، در طی ماشین ها باشند در حالی که مموایز کردن بیشتر وابسته به ماشین می باشد و در ضمن تدبیری کراس پلت فرم می باشد. تابع شبه کد پایین را برای محاسبه فاکتوریل 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≥0, نتیجه پایانی تابع فاکتوریل غیرمتغیراست. اگر به (x = factorial(3 استناد داده شده باشد، نتیجه طوری است که x همیشه برابر با مقدار 6 خواهد بود. یک نسخه غیر مموایز از مورد بالا،با طبیعت الگوریتم بازگشتی درگیر داده شده،احتیاج به فراخوانی های n + 1 فاکتوریل دارد تا به نتیجه بالا برسد و هرکدام ازاین فاخوانی ها، به نوبه خود، هزینه ای مرتبط در زمان می گیرد تا تابع مقدار محاسبه شده را بازگرداند. بسته به ماشین،این نتیجه جمع موارد زیر خواهد بود:

  1. هزینه راه اندازی قالب فراخوانی پشته کاربردی
  2. هزینه مقایسه n تا 0
  3. هزینه کم کردن 1 از n
  4. هزینه راه اندازی فراخوانی قالب پشته بازگشتی(مثل بالا)
  5. هزینه ضرب نتیجه فراخوانی بازگشتی به فاکتوریل به وسیله ی n
  6. هزینه ذخیره کردن نتیجه بازگشت طوری که ممکن است به وسیله ی محتوای فراخوانی مورد استفاده واقع شود.

در یک اجرای غیرمموایز،هرفراخوانی سطح بالا به فاکتوریل شامل هزینه انباشته مراحل 2 تا 6 متناسب با مقدار 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 nth slot [remember the result of n! for later]
        return x
    end if
end function

دراین مثال خاص،اگر فاکتوریل در ابتدا با 5 فراخوانی شود و سپس بعداً باهر مقداری کم تر و یا برابر با 5 فراخوانی شود،آن مقادیر بازگشتی همچنین مموایز خواهند شد،چون فاکتوریل به صورت بازگشتی با مقادیر0و1و2و3و4و5 فراخوانی خواهند شد،و مقادیر بازگشتی برای هر کدام از آن ها ذخیره خواند بود.اگرآن بعداً با یک شماره بزرگتر از 5،نظیر 7فراخوانی شود،فقط 2 فراخوانی بازگشتی(6و7)انجام می شود و نتیجه !5 از قبل ذخیره شده است.دراین روش،مموایز کردن به یک تابع اجازه می دهد که از نظر زمانی بیشتر بهینه شود مادامی که بیشتر فراخوانی می شود، بنابراین منتهی به یک افزایش سرعت نهایی می شود.

بعضی از دیگر ملاحظلات[ویرایش]

مموایزکردن اتوماتیک[ویرایش]

اگر چه ممکن است مموایز کردن به توابع به صورت داخلی و واضح به وسیله ی یک برنامه نویس کامپیوتر،بیسار شبیه به روش اشاره شده در بالا که برای اجرای فاکتوریل بود،اضافه شود،توابع شفاف ارجاعی ممکن است به صورت اتوماتیک و خارجی مموایز شوند.تکنیک هایی که توسط 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

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

منابع[ویرایش]

  1. Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1, pp. 91–98, March 1991.
  2. Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 – 120, June 2007, Prague.
  3. Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167–181, January 2008, San Francisco.
  4. Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009.
  5. Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19–22, 1968.

پیوند به بیرون[ویرایش]

[[sv:Memoisat