ساختمان داده( مقدمه به تحلیل الگوریتم) - قسمت دوم

احتمالاً تا الان می‌دانید که ساختمان داده (Data Structure) یک روش سیستماتیک برای سازماندهی اطلاعات است و الگوریتم (Algorithm) هم همان دستورالعمل گام‌به‌گام ما برای انجام یک کار مشخص.

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

بیایید این موضوع را با یک مثال معروف و جذاب بررسی کنیم.

تله‌ای به نام دنباله فیبوناچی!

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

1,1,2,3,5,8,13,...

تعریف ریاضی این دنباله به این شکل است:

a(n)=a(n−1)+a(n−2)

a(0)=1,a(1)=1

(البته در بعضی تعاریف، دنباله با ۰ شروع می‌شود که فعلا با آن کاری نداریم).

حالا فرض کنید می‌خواهیم این دنباله را با کامپیوتر تولید کنیم. اولین و ساده‌ترین ایده‌ای که به ذهن هر برنامه‌نویسی می‌رسد، استفاده از توابع بازگشتی (Recursive) است:

def fib(n):
    if n == 1 or n == 0:
        return 1
    return fib(n - 1) + fib(n - 2)

کد بالا کاملاً درست کار می‌کند و ظاهراً هیچ مشکلی ندارد. اما این کد یک فاجعه‌ی به تمام معناست!

کافیست به این تابع، ورودی n=100 را بدهید. فکر می‌کنید چه اتفاقی می‌افتد؟ سیستم شما برای مدت بسیار طولانی (شاید روزها و سال‌ها!) درگیر محاسبات تکراری می‌شود و احتمالاً قبل از اینکه جواب را ببینید، لپ‌تاپتان را خاموش می‌کنید!

نکته حرفه‌ای (Pro Tip): دلیل این کندی شدید این است که این الگوریتم یک درخت محاسباتی بزرگ می‌سازد و یک مقدار ثابت را بارها و بارها از نو محاسبه می‌کند. به این مشکل اصطلاحاً می‌گویند Time Complexity یا پیچیدگی زمانی از نوع نمایی (Exponential).

دقیقاً به همین خاطر است که ما به الگوریتم‌های کارآمد نیاز داریم و ساختمان‌داده‌ها (مثل آرایه‌ها یا هش‌مپ‌ها برای کش کردن نتایج) اینجا نقش منجی را بازی می‌کنند.

تحلیل تجربی (Experimental Studies): کرنومتر به دست بگیرید!

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

اما آیا این روش بهترین راه است؟ قطعا نه! تحلیل تجربی معایب بزرگی دارد:

1. نوشتن کد اجباری است: اول باید حتماً الگوریتم را پیاده‌سازی کنید تا بتوانید آن را تست کنید.

2. وابستگی به زبان برنامه‌نویسی: یک الگوریتم یکسان در C++ خیلی سریع‌تر از Python اجرا می‌شود، پس مقایسه عادلانه نیست.

3. وابستگی به سخت‌افزار: زمان اجرا روی پردازنده Core i9 با یک پردازنده ضعیف موبایل کاملاً متفاوت است.

4. نیاز به تکرار آزمایش: برای رسیدن به یک عدد قابل اتکا، باید آزمایش را ده‌ها بار تکرار کرده و میانگین بگیرید.

5. عدم قابلیت تعمیم: اگر الگوریتم شما تا ورودی n=41 خوب کار کرد، هیچ تضمینی نیست که روی n=100 هم همان رفتار را نشان دهد (نمودار همیشه خطی نمی‌ماند).

به خاطر همین ضعف‌هاست که مهندسان نرم‌افزار به سمت تحلیل‌های تئوری (مثل نمادهای Big O) می‌روند که در مقالات بعدی حسابی در موردشان صحبت می‌کنیم.

چطور خودمان زمان اجرای کد را اندازه بگیریم؟ (در پایتون)

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

1. ثبت زمان شروع

2. اجرای الگوریتم

3. ثبت زمان پایان

4. تفریق این دو زمان از هم

در زبان پایتون، ما ابزارهای برای این کار داریم:

روش اول: استفاده از ماژول time

این ساده‌ترین روش برای اندازه‌گیری زمان است:

import time

def fib(n):
    if n == 0 or n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


start_time = time.perf_counter() 

fib(30) 

end_time = time.perf_counter()

print(f"Time taken: {end_time - start_time} seconds")

نکته حرفه‌ای: در کد بالا به جای time.time() از time.perf_counter() استفاده کردیم. چرا؟ چون perf_counter دقیق‌ترین ساعت موجود در پایتون برای اندازه‌گیری فواصل زمانی کوتاه است و بر خلاف time()، تحت تاثیر تغییرات ساعت سیستم‌عامل قرار نمی‌گیرد!

روش دوم: ابزار دقیق‌تری به نام timeit

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

import timeit

setup = 'from __main__ import fib'

def fib(n):
    if n == 0 or n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)


print(timeit.timeit('fib(20)', setup=setup, number=1))

برای استفاده از این ماژول، دستورات اجرایی و دستورات آماده‌سازی (Setup) را به صورت رشته (String) به آن پاس می‌دهیم. پارامتر number هم مشخص می‌کند که کد چند بار اجرا شود (مقدار پیش‌فرض آن ۱,۰۰۰,۰۰۰ بار است که برای کدهای سنگین بهتر است آن را کاهش دهید).