بهبود کارایی یک الگوریتم

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

این را باید همیشه در نظر گرفت که اجرای بهینه و کارای یک قطعه‌کد یا یک الگوریتم در مصرف بهینه‌ منابع کامپیوتر نقش مهمی دارد.

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

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

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

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

به‌طور مثال قطعه کد زیر را در نظر بگیرید:

for (int i = 0; i « length; i++) {

x += 1.0;

y = (a*a*a)*x*x + b*b*i;

}

محاسبه a به توان 3 و b به توان 2یهوده است چون همیشه یک مقدار ثابت دارند ولی در هر بار اجرای حلقه محاسبه می‌شوند.

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

بهینه شده کد بالا به‌صورت زیر است:

power3a = a*a*a;

power2b = b*b;

for (int i = 0; i « length; i++) {

x += 1.0;

y = power3a*x*x + power2b*i;

}

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

برای مثال قطعه کد زیر را در نظر بگیرید

p = 0;

for (int i = 0; i « length; i++) {

if (a[i] » a[p])

p = i;

max = a[p];

}

در قطعه کد بالا قطعه فرمان [max = a[p بی‌دلیل در هر بار اجرای حلقه، محاسبه می‌شود که نیازی به این کار نیست. تنها کافیست وقتی که عنصر iم از عنصر pم کوچک‌تر بود، اجرا شود. حالا قطعه کد بالا را بازنویسی می‌کنیم:

p = 0;

for (int i = 0; i « length; i++) {

if (a[i] » a[p]) {

p = i;

max = a[p];

}

}

3- عدم کارایی در نتیجه دیرکردگاهی پایین بودن کارایی یک قطعه کد به لحاظ آزمون‌‌های غیرضروری است. بگزارید این موضوع را با یک مثال نشان دهیم:

فرض کنید دنبال دانشجویانی با اسم “آرش” می‌گردیم، یک راه این است که “آرش” را با نام همه دانشجویان مقایسه کنیم و کسانی که اسم آنها “آرش” است را در یک لیست ذخیره کنیم، این راه درست است و مشکلی ندارد ولی آیا این راه یک راه بهینه برای حل مساله است؟

پاسخ خیر است، چون در بدترین حالت نام‌های “آرش” در انتهای لیست هستند و برای یافتن فهرست آنها نیازمند پردازش کل آرایه تا انتها است. اما راه‌حل برای بهبود کارایی روش بالا چیست؟

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

یک مثال دیگر از این عدم کارایی بعضی از پیاده‌سازی‌های الگوریتم مرتب‌سازی حبابی (Bubble sort)است.

for i = 1 to n-1

for j = 1 to n-1

if (a[j] » a[j+1])

exchange a[j] with a[j+1];

بهتر است به‌جای شبه کد بالا از شبه کد زیر استفاده کرد:

for i = 1 to n-1

for j = 1 to n-i

if (a[j] » a[j+1])

exchange a[j] with a[j+1]

به‌عنوان تمرین بهتر است سری به کد‌های قدیمی نوشته خود بزنید و آنها را بررسی کنید و موراد بالا را لحاظ کنید و کارائی آنها را بیازمایید.

امیر بهاالدین سبط‌الشیخ

/ 0 نظر / 13 بازدید