دستاورد ها در زبان پایتون چیست ؟
دستاورد ها در زبان پایتون چیست ؟
اگر با تابع fibonacci از بخش 5-7 کار کرده باشید، احتمالاً متوجه شدهایـد کـه هـر چـه آرگومان مقرر بزرگتر باشد زمان بیشتري صرف اجراي تابع میشود. بهعلاوه زمان اجـرا خیلـی سـریع افـزایش مــییابــد. بــر روي یک ـی از ماشـینهــاي مــا، (20(fibonacci فــوراً اجـرا مــیشــود، (30(fibonacci حدود 1 ثانیـه زمـان مـیبـرد و (40(fibonacci تقریبـاً تـا ابـد بـه طـول میانجامد. یک گراف فراخوانی، مجموعه قابهاي تابع را با خطوطی کـه هـر قـاب را بـه قـابهـاي توابـع فراخوانــده شــده وصـل مــیکننـد نمـایش مــیدهـد. در بــالاي گــراف fibonacci بــا a4=na، fibonacci با 3 = n و 2 = n را صدا مـیزنـد. بـه همـین ترتیـب fibonacci بـا a3=na، fibonacci با 2 = n و 1 = n را فرامیخواند و … . تعداد دفعات فراخوانی (0(fibonacci و (1(fibonacci را بشمارید. این یک راه حـل ناکارآمد مسأله است و همینطور که آرگومان تابع بزرگتر میگردد، وضع بدتر و وخیمتر میشود. یک راه حل مناسب براي این مسأله حفظ مقادیر از پیش محاسبه شده بهوسـیلۀ مرتـب کـردن آنها در یک دیکشنري است. به مقداري که قبلاً محاسبه شده و براي استفاده در محاسبات بعدي به کار میرود دستاورد میگویند. در اینجا اجرایی از fibonacci را با استفاده از دستاوردها میبینیم:
previous = {0:1, 1:1}
def fibonacci(n):
if previous.has_key(n):
return previous[n]
else:
newValue = fibonacci(n-1) + fibonacci(n-2)
previous[n] = newValue
return newValue
دیکشنري previous اعداد فیبوناچی را که تاکنون بهدست آوردهایم، ثبت میکند. تنها با دو جفت، عملیات را شروع میکنیم: 0 به 1 و 1 هم به 1 نگاشت میکند. هر گاه که fibonacci فراخوانی شود، دیکشنري را چک میکند تا تعیـین کنـد آیـا حـاوي نتیجه هست یا نه. اگر نتیجه در دیکشنري موجود بود تابع میتواند بدون هیچگونه فراخوانی بازگشـتی سریعاً بازگردد، در غیر این صورت باید مقدار جدید را محاسبه نماید. این مقدار جدید قبـل از بازگشـت تابع به دیکشنري اضافه میشود. با استفاده از این نسخۀ fibonacci ماشینهاي ما (40(fibonacci را در یک چشم به هم زدن محاسبه میکنند. اما هنگامی که سعی میکنـیم (50(fibonacci را محاسـبه کنـیم بـه اشکالی متفاوت بر میخوریم:
>> fibonacci(50)
OverflowError: integer addition
پاسخی که تا یک دقیقۀ دیگر خواهید دید 074,011,365,20 میباشد. مشکل آنجـا اسـت که این عدد براي جا شدن در متغیرهاي صحیح پایتون (integer) خیلی بـزرگ اسـت و سـرریز میشود. خوشبختانه این مشکل راه حل سادهاي دارد.
برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید
ثبت نام
با ایمیل خود وارد شویدورود
