محاسبه زمان اجرای الگوریتم ها از طریق برنامه نویسی

به نام خدا

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

1) پروژه خواسته شده شامل موارد زیر است

1. کد برنامه

2. شبه کد برنامه(pseudocode)

3. الگوریتم برنامه

4. تابع پیچیدگی و مرتبه آن :مرتبه یک قطعه کد با توجه به حلقه ها در قطعه کد اصلی برنامه بدست می آید. ممکن است برای مثال تابع پیچیدگی کل کد یک برنامه 12n^3+5n باشد اما قطعه کد اصلی برنامه دارای تابع پیچیدگی 2n^2 باشد. تابع پیچیدگی از روی کد برنامه بدین ترتیب محاسبه می گردد که اگر حلقه ها درون هم باشند گام های حلقه ها، که البته لزوما هم یکسان نیستند، در هم ضرب شده و اگر متوالی باشند گام های حلقه ها با هم جمع می شوند. برای مثال در مثال یاد شده فوق کل برنامه می تواند دارای 12 حلقه for بوده که هرکدام دارای 3 حلقه for تودرتو باشند و نیز دارای 5 حلقه for متوالی باشد. و در قطعه کد اصلی احتمالا فقط 2 حلقه for داریم که هرکدام دارای 2 حلقه for تودرتو می باشند. همچنین واضح است 12n^3+5n از مرتبه n^3 و همچنین 2n^2 از مرتبه n^2 می باشد.

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

با بدست آوردن مقادیر می توان در برنامه Excel نمودار آن را به هر طریقی که مورد نظر است(تغییرات یک متغیر یا مقایسه تغییرات چند متغیر) مشاهده کرد. کافیست داده ها را در ستون ها(برای هر متغیر یک ستون) متناظر باهم نوشته و سپس از زبانه Insert و در قسمت Scatter نوع نمودار و شکل آنرا تعین نمود.

6. بررسی شود که برنامه با کدام یک از روش هایی که در کلاس بحث شده، انجام گرفته است.

2) نحوه ی زمانگیری

اصولا زمانگیری دو گونه است:

1. بوسیله تنظیم دستی زمان در برنامه

2. بوسیله ساعت سیستم

ما در اینجا به شرح روش دوم می پردازیم. این روش بدین صورت است که ابتدا تعداد کلاک اجرای برنامه رابدست آورده و بر تعداد کلاک در هر ثانیه تقسیم می کنیم. نتیجه با دقت میلی ثانیه خواهد بود.

در این روش ضمن اضافه کردن تابع کتابخانه ای time.h به ابتدای برنامه، قبل از اجرای قطعه کد اصلی برنامه باید این خط را اضافه نمود:

clock_t start = clock();

و در پایان قطعه کد اصلی برنامه :

printf("\nTime elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);

لازم به ذکر دو نکته در استفاده از این قطعه کد است:

یکم اینکه اگر قسمت اول کد از ابتدای برنامه استفاده گردد زمانگیری دقیق نبوده و یا اشتباه خواهد بود. بدین صورت که زمان اضافی شامل مکث کاربر جهت ورودی داده را نیز ثبت خواهد کرد، که این مورد نظر نیست.

دوم اینکه اگر در برنامه خواهان دوبار زمانگیری در یک برنامه باشیم، کافیست نام متغیر زمانگیری را بدین صورت برای بار دوم به بعد تغییر دهیم:

clock_t start1 = clock();

و در چاپ نیز بدین صورت با همان نام ایجاد شده:

printf("\nTime elapsed: %f\n", ((double)clock() – start1) / CLOCKS_PER_SEC);

و همینطور الی آخر برای دیگر زمانگیری ها.

3) تسهیل عملیات زمانگیری

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

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

راه دوم راه متداولتری است. بدین صورت که زمان هر مرحله در متغیری بطور جداگانه ذخیره و در انتها چاپ می کنیم. در یک مثال بطور کامل با این روش آشنا خواهیم شد.

برای قطعه کد زیر می خواهیم عملیات زمانگیری را انجام دهیم:

#include

int main()

{

int n, x;

printf( "How many disks? " );

scanf( "%d", &n );

printf("\n");

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

getch();

return 0;

}

می خواهیم به ازای مقادیر 14و 15و 16 و17 و18 و 19 برای n عملیات زمانگیری را در یک بار اجرای برنامه انجام دهیم.با تغییرات گفته شده که در کد برنامه ایجاد می کنیم برنامه بصورت زیر درخواهد آمد:

#include

int main()

{

int n, x;

float t,t1,t2,t3,t4,t5; //متغیرها برای هرکدام از زمانگیری ها

n=14;

clock_t start = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t=(((double)clock() - start) / CLOCKS_PER_SEC); // ذخیره زمان برای ورودی14

n=15;

clock_t start1 = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t1=((double)clock() - start1) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی15

n=16;

clock_t start2 = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t2=((double)clock() - start2) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی16

n=17;

clock_t start3 = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t3=((double)clock() - start3) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی17

n=18;

clock_t start4 = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t4=((double)clock() - start4) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی18

n=19;

clock_t start5 = clock();

for (x=1; x < (1 << n); x++)

printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );

t5=((double)clock() - start5) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی19

printf("\nTime elapsed: %f\n", t); // چاپ زمان ها بترتیب

printf("\nTime elapsed: %f\n", t1);

printf("\nTime elapsed: %f\n", t2);

printf("\nTime elapsed: %f\n", t3);

printf("\nTime elapsed: %f\n", t4);

printf("\nTime elapsed: %f\n", t5);

getch();

return 0;

}

که نتیجه اجرای مطابق شکل زیر است

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

4) عموما برنامه هایی که توسط خود دانشجویان نوشته می شود بدون توجه به این موضوع انجام می گیرد که در هنگام زمانگیری نیاز به دادن ورودی های بسیار بزرگ نیز وجود دارد. و این بی توجهی باعث بروز خطاهایی مانند سرریز(overflow) می شود. بهتر است از ابتدا برنامه ها را بصورت پویا و با استفاده از آرایه پویا یا پشته(تابع بازگشتی هم از پشته استفاده می کند) انجام داد.

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

5) مکث در هنگام چاپ

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

6) چگونه ورودی بزرگ برای برنامه با ورودی های ترتیبی وارد کنیم؟

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

printf("kafe maghadir:");//برای انتخابی کردن کف و سقف مقادیر رندوم که داخل آرایه پویا می ریزیم

scanf("%d",&a);

printf("saghfe maghadir:");

scanf("%d",&b);

srand(time(0)); //برای اینکه اعداد تصادفی تولید شده در هر بار متفاوت باشد

for (i = 0; i < n; i++ )// ایجاد اعداد رندوم به تعداد ورودی خواسته شده

{

int rand100 = rand()%(b-a+1)+a;

*(z+i)=rand100; //قرار دادن هر مقدار تولید شده در یک خانه از آرایه پویا که از اشاره گر استفاده شده

}

قطعه کد فوق در ابتدا بازه تولید اعداد رندوم را از کاربر گرفته و کمترین را در a و بیشترین را در b قرار می دهد. سپس با استفاده از تابع رندوم و کف و سقفی که به آن داده ایم آماده ایجاد اعداد رندوم به تعداد عناصر آرایه پویای z است. در حلقه هربار عدد رندوم در بازه داده شده تولید شده و بترتیب به عناصر آرایه پویا نسبت داده می شود.

اعداد رندوم بصورت پیشفرض در هر بار یکسان تولید می شوند. در صورت تمایل برای ایجاد اعداد تصادفی متنوع در هر بار باید ایجاد کننده اعداد تصادفی( random seed ) تغییر کند. بنابراین از تابع srand(int seed) استفاده شده است. که میتوان مقدار seed را در هربار از کاربر پرسید تا هربار اعداد تولید شده متفاوت باشند. اما راه بهتر برای تولید اعداد تصادفی متفاوت آن است که seed را بوسیله ساعت سیستم یعنی با time(0) در هربار متمایز کنیم، بدون آنکه لازم باشد از کاربر بخواهیم.

7) طرح یک سوال:

چرا چاپ؟

چرا در زمانگیری باید چاپ داشته باشیم؟ آیا واقعا چاپ لزومی دارد؟

بسیاری از برنامه ها اصلا چاپ های متوالی ندارند و حتی برای ورودی های بسیار بزرگ هم محاسبات آن بیش از چند دقیقه بطول نخواهد انجامید.

بعنوان مثال در برنامه های برجهای هانوی درصورتی که چاپ متوالی حرکات دیسک را نداشته باشیم براحتی تا حدود 40 دیسک را در مرز دقیقه خواهیم داشت. درحالیکه با چاپ برای 27 دیسک در بهترین حالت(الگوریتم دودویی) 7 ساعت و 20 دقیقه طول می کشد. مشخص است که اکثر زمان مربوط به عمل چاپ کردن است. چاپ کردن چه ارزشی دارد؟ اصلا ارزشی در محاسبات زمانگیری الگوریتم ها دارد؟

برای آزمایش تغییر جزئی در برنامه ایجاد می کنیم. \n های پایان printf ها را برداشته و عبارت توضیحی چاپ را کوتاه می کنیم. نتیجه بسیار تامل برانگیز است. در حالت قبلی برای 22 دیسک زمان در الگوریتم بازگشتی 1، زمان 836.609 ثانیه ثبت شده است. اما در حالتی که تغییرات یاد شده اعمال گشته زمانگیری عدد 629.766 ثانیه را نشان می دهد.

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

8) این پست یا ابه اصطلاح راهنما باز گذاشته می شود تا تجربیات ارزشمند دیگر دوستان در ادامه آن ثبت گردد. بارزترین نکته آنکه از زبان c بعنوان پایه استفاده شده است اما در این درس از زبان های برنامه نویسی دیگر نیز می توان استفاده کرد. امید است بمرور بدل به راهنمای جامع و کاملی گردد تا دانشجویان بطور کامل از اطلاعات مفید آن بهره کافی ببرند.

همچنین این راهتما در سایت برنامه نویس به عنوان یک تاپیک گذاشته شده است. می توانید از طریق لینک زمانگیری-اجرای-یک-برنامه به زبان سی به آن دسترسی داشته باشید.

بازدیدکنندگان این پست می توانند نظرات تکمیلی خود را از طریق نظرات همین پست، ارسال کنند.

علی آیت اللهی نصرآبادی