مفهوم Memoization در php ( افزایش سرعت اجرا با استفاده از caching )

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

حالا بیایید در عمل بهتون نشون بدم چطور میشه مانع از تکرار پروسه های تکراری شد. دنباله فیبوناچی رو در ریاضی که یادتون هست، هر عدد از مجموع دو عدد قبل از خود حاصل می شود که البته آغازگر آن 0 و 1 است. چیزی شبیه این: 0,1,1,2,3,5,8,13 و الی آخر. محاسبه چنین پروسه ای در زبان php برابر است با کد زیر:

<?php

function fibonacci($n) {

          if ($n < 2) {
                   return $n;
           }

        $memoization= fibonacci($n - 1) + fibonacci($n - 2);
         return $memoization;
     }

خب مطابق بر دنباله فیبوناچی، کد بالا ابتدا در یک شرط چک میکند که عدد مورد نظر ما 0 و 1 است یا خیر. سپس بر مبنای ورودی، تا n عدد، دنباله فیبوناچی را محاسبه میکند. مثلا اگر بخوایم دنباله را تا 6 عدد محاسبه کنیم، عدد 6 به عنوان متغیر ورودی n$ به تابع داده می شود، سپس به شکل یک loop، دنباله فیبوناچی تکرار و محاسبه می شود. علت استفاده از n - 1 و n - 2 ، جمع عدد قبل با عدد بعد از خود است. در نهایت عدد نهایی برگشت داده می شود.

حالا تصور کنید این پروسه شامل محاسبه تمامی اعداد از عدد مورنظر یعنی 6 تا عدد 0 و جمع عدد قبل و بعد است. نتیجه می شود عدد 8.

خب تا اینجا که چیز عجیبی نیست، یک محاسبه ساده فیبوناچی، اما اگر بر فرض بخواهم زمان اجرا این محاسبه را اندازه بگیرم، چه کار میتوانم بکنیم؟ به روش زیر:

<?php 

$start_time = microtime(true);   // شروع محاسبه زمان

 function fibonacci($n) {   

     usleep(10000);  // ایجاد یک دیلی زمانی 1 ثانیه ای    
     if ($n < 2) {              
           return $n;         
   }        

   $memoization= fibonacci($n - 1) + fibonacci($n - 2);      
    return $memoization;     
 }

$time_taken = microtime(true) - $start_time;
fibb(6); 
print(&quot\n&quot . $time_taken);

حالا یک بار دیگر برنامه را اجرا کنید تا ببینید مدت زمان اجرای برنامه شما چقدر است. چیزی حدود 1.7 ثانیه می شود. 1 ثانیه آن دیلی است که برای ملموس تر شدن فاصله اجرا داده شده است. تا اینجا هم مشکل زیادی دیده نمی شود. مشکل زمانی است که بخواهیم دنباله های بیشتری را محاسبه کنیم به طور مثال:

fibb(6);
fibb(8);
fibb(10);

حالا زمان اجرا اسکریپت چطور است؟ چیزی حدود 2.4 ثانیه شد. با افزایش دنباله های فیبوناچی، زمان محاسبه دنباله ها رشد پیدا میکند. دلیل؟ محاسبه تمام اعداد در تکرار هر تابع، از ابتدا صورت میگیرد. ما باید از تکرار این پروسه در هر تابع جلوگیری کنیم. چطور؟ با استفاده از caching.

کانسپت caching، اشکال مختلفی دارد، شما میتوانید اطلاعات تکراری خودتون رو به شکل های مختلف ذخیره کنید تا در پروسه های تکراری قابل استفاده مجدد باشند. به 3 شکل میتونید caching بگیرید:

1_ ذخیره در فایل های روی disk

2_ ذخیره در سشن memory

3_ ذخیره در فایل های روی memory یا همان tmpfs

خب قرار نیست در مورد تک تک این ها توضیح زیادی بدم، دم دستی ترین روش رو استفاده میکنیم که احتمالا خیلی هاتون باهاش آشنا هستید، اطلاعات مون رو میریزم داخل یه آرایه ( ذخیره نوع دوم در memory ) و از طریق کلیدهای آرایه، میتونیم داده های تکراری را بازخوانی کنیم.

حالا تابع بالا را مطابق با آن، بازنویسی میکنیم:

<?php

function fibbmem($n, &$memo)
{
            usleep(10000);
            if ($n < 2) {
                    return $n;
           }
          if (isset($memo[$n])) {
                         return $memo[$n];
            }

            $memo[$n] = fibbmem($n - 1, $memo) + fibbmem($n - 2, $memo);
            return $memo[$n];
}

$memo = [ ]; // ساخت آرایه خالی

$result1 = fibbmem(6, $memo);
$result2 = fibbmem(8, $memo);
$result3 = fibbmem(10, $memo);

$time_takenmem = microtime(true) - $start_timemem;  // محاسبه زمان اجرا
print_r($memo);

حالا بیایید نگاهی به این تابع بازنویسی شده بندازیم. ما مجموع دو عدد قبل و بعد هر مرحله را در آرایه ذخیره کردیم و عدد n$ را برابر با کلید آن قرار دادیم. عدد n در هر مرحله، یک واحد کم میشود تا به 0 ختم شود.

زمانی که تابع دوم و سوم فیبوناچی بخواهند اجرا شوند، دیگر مجبور نیستند محاسباتشان را از اول انجام دهند، به این دلیل که مقادیر کش شده در آرایه ذخیره شده است کافی است در قسمت شرط با استفاده از isset چک کنیم ببینیم آیا مقدار محاسبه شده ما در آرایه موجود هست و تنها در صورتی که کش آن موجود نباشد، محاسبه انجام می شود و مقدار محاسبه شده در آرایه کش ذخیره میگردد.

حالا اسکریپت را اجرا کنید و تفاوت را بسنجید. برای من شد 0.3 ثانیه، بستگی به عوامل دیگر هم دارد و محاسبه زمانی، دقیق و کامل نیست اما حتی به صورت نسبی هم دیدید که چه اندازه سرعت اجرا بالا رفت. حالا تصور کنید که دنباله فیبوناچی به صورت تصاعدی، محاسبه اش تا چه اندازه رشد میکند یا در شرایط داشتن دیتابیس های حجیم، تا چه اندازه چنین روش هایی می تواند برای ما مفید باشد.

اگر سوالی در این باره داشتید در کامنت ها ازم بپرسید، پاسخ میدم ^__^