آنالیز

قسمت اول

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

علاوه بر موارد بالا، لازمه که با تفاوت real time و cpu time آشنا باشیم. اینها رو میگیم.

زمان واقعی یا real time: این زمان از لحظه شروع برنامه تا لحظه پایان اون محاسبه میشه. مثلا یه برنامه داریم که قراره یه ورودی از کاربر بگیره و اونو رو صفحه پرینت کنه. اما اگه کاربر ۱۰ دقیقه همینجوری صبر کنه و بعد چیزی رو وارد کنه، این زمان بیکاری هم جزو real time حساب میشه. یعنی اول کار زمان شروع برنامه رو میگیریم و آخر کار هم زمانی که برنامه به پایان رسید دوباره زمان رو میگیریم و زمان ابتدا رو از انتها کم میکنیم. برای محاسبه زمان واقعی تو پایتون میتونیم این کارو بکنیم:

import time

start = time.time()

...

end = time.time()

print(f'real time is: {end - start}')

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

زمان cpu یا cpu time:

واقعیت اینه که اینجور نیست که وقتی یه برنامه رو اجرا کنیم‌ از وقتی که اجرا بشه تا لحظه آخر cpu رو در اختیار داشته باشه. مثلا برنامه ما ممکنه به یه ورودی از کاربر نیاز داشته باشه. در این صورت برنامه ما به حالت sleep میره و پردازنده ازش گرفته میشه. یعنی ممکنه زمان واقعی که سپری شده باشه ۱۰ دقیقه باشه ولی زمان در اختیار داشتن cpu فقط چیزی مثل ۰.۰۰۱ ثانیه باشه. البته ممکنه real time و cpu time با هم برابر هم باشن. در حالت کلی:

cpu time <= real time

برای اندازه گیری cpu time در پایتون میتونیم از ماجول timeit استفاده کنیم. البته با timeit میشه real time رو هم اندازه گرفت و اتفاقا حالت پیش فرض همینه.

import timeit

import time

def foo():

    # do something

timer = timeit.Timer(stmt=foo, timer=time.process_time)

timer.timeit(number=1)

خب cpu time میتونه معیار بهتری نسبت به real time باشه اما باز هم تفاوت های سخت افزاری دخالت دارند.

• انواع آنالیز

آنالیز تجربی:

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

۱ - ما نمیتونیم همه ورودی‌های ممکن رو به برناممون بدیم و فقط تعداد مشخصی رو بهش ورودی میدیم و از یه سری از ورودی‌ها صرف نظر کردیم در حالی که ممکنه اون ورودی‌ها مهم بوده باشن.

۲ - اندازه‌گیری زمان اجرا به در این روش وابسته به ویژگی‌های سخت‌افزاری و نرم‌افزاری هستش و مقایسه بین زمان اجرای دو الگوریتم در این روش سخت و حتی ناممکنه.

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

ایراد سوم مهم ترین ایراد روش تجربی هستش. ما باید یه رویکردی رو پیش بگیریم که این سه تا ایراد رو نداشته باشه. یعنی رویکرد ما باید :

۱ - تمام ورودی‌های ممکن رو پیش‌بینی کنه

۲ - مستقل از ویژگی‌های سخت افزاری و نرم افزاری باشه و برای هر کامپیوتری صادق باشه

۳ - بدون نیاز به implement کردن اون و با استفاده از یک رویکرد سطح بالا بتونیم اون رو مطالعه و آنالیز کنیم.