الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نکته‌ای در استفاده از map - الگوریتمستان
الگوریتمستان
  »  

نکته‌ای در استفاده از map

        نکته‌ای در مورد استفاده از ساختمان داده‌ی map با مثالی به زبان برنامه‌نویسی ++C

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

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

int main(){
    const int size = 700000;
    int a[size];
    map<int, int> b;
    clock_t tStart;
    double cps = CLOCKS_PER_SEC;
    a[0] = b[0] = 0;
    a[1] = b[1] = 1;
    tStart = clock();
10     for(int i = 2 ; i < size ; i++)
11         a[i] = a[i - 1] + a[i - 2];
12     cout << "Time for array: " << (clock() - tStart) / cps << "s" <<  endl;
13     tStart = clock();
14     for(int i = 2 ; i < size ; i++)
15         b[i] = b[i - 1] + b[i - 2];
16     cout << "Time for map: " << (clock() - tStart) / cps << "s" << endl;
17     return 0;
18 }

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

این برنامه‌ی ساده نشون می‌ده زمانی که کلید ما اعداد صحیح هستن، تا حد ممکن باید از آرایه استفاده کنیم. ممکنه محدوده‌ی اعداد صحیح مورد نظر ما از صفر شروع نشه یا حتی شامل اعداد منفی هم باشه. این موارد رو می‌شه با یه جابجایی ساده به صفر در نظر گرفت. مثلا اگه اعداد کلید در بازه‌ی [10,10-] هستن، می‌شه اون رو با آرایه‌ی به طول 21 پیاده‌سازی کرد که مقدار متناظر کلید i در اندیس i + 10 از آرایه ذخیره می‌شه. حتی اگه صرفا از احتمال توزیع کلید در یه بازه اطلاع داشته باشیم و کل عناصر بازه استفاده نشن، خیلی از اوقات استفاده از آرایه‌ی با اندازه‌ی max - min + 1 و وجود حافظه‌ی بلااستفاده، نسبت به استفاده از‌ map‌ مقرون به صرفه‌تره. در واقع هزینه‌ی زمانی رو به هزینه‌ی حافظه تبدیل می‌کنیم.

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
برچسب‌ها
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۸۶۵ روز
تعداد بازدید:  ۹۰۰۴ بازدید
تعداد امتیاز:  ۴ امتیاز
میانگین امتیاز:  ۵.۰۰  از  ۵.۰۰
»  بازی Lights Out و ریاضیات دوست داشتنی
        حل بازی Lights Out با ریاضیات دوست داشتنی
»  نکته‌ای در مورد کلاس‌ها و مجموعه‌ها در ++C
        بررسی روش تعریف کلاس برای قابلیت استفاده از ظرف‌های مجموعه (set و unordered_set) در زبان برنامه‌نویسی ++C
»  سوال Free Ticket
        راهنمای حل سوال Free ticket، از سوالات المپیاد ملی کامپیوتر هندوستان
»  sync_with_stdio در زبان ++C
        نکته‌ای در مورد کارایی عملیات ورودی و خروجی در زبان برنامه‌نویسی ++C و عملکرد تابع sync_with_stdio
»  نکته‌ای در محاسبه‌ی زمان اجرای کد
        در مورد تفاوت توابع clock و time در زبان برنامه‌نویسی ++C برای محاسبه‌ی زمان اجرای برنامه
»  ابزار VJudge
        معرفی وب‌سایت Virtual Judge برای برگزاری مجازی مسابقه‌ی برنامه‌نویسی به سبک مسابقات ACM-ICPC
»  هدر فایل bits/stdc++.h
        معرفی هدرفایل bits/stdc++.h برای کاهش زمان آماده شدن کد مسابقات برنامه‌نویسی
»  نکته‌ای از مسأله‌ی Graphical Editor
        استفاده از stringstream در حل سوالات مسابفات برنامه‌نویسی با زبان برنامه‌نویسی ++C
»  ابزار UVA Toolkit
        معرفی وب‌سایت UVA Toolkit برای کمک به حل سوالات برنامه‌نویسی UVA Online Judge
»  نکته‌ای از مسأله‌ی LC-Display
        نکته‌ای در باب روش ذخیره کردن ورودی یک مسأله
»  تابع popen
        روش اجرای برنامه‌ای دیگر داخل کد ++C و استفاده از خروجی آن
»  ظرف‌ها در ++C
        معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C
»  سینوس و کسینوس را قورت بده
        محاسبه‌ی جدولی سینوس و کسینوس زوایای مشهور
»  بازی مین‌روب
        بازنشر یک یادداشت قدیمی