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

نکته‌ای در استفاده از map - تجربه‌های پراکنده‌ی یک مسعود
تجربه‌های پراکنده‌ی یک مسعود
315.005.00

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

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

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

 1  int main(){
 2      const int size = 700000;
 3      int a[size];
 4      map<int, int> b;
 5      clock_t tStart;
 6      double cps = CLOCKS_PER_SEC;
 7      a[0] = b[0] = 0;
 8      a[1] = b[1] = 1;
 9      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‌ مقرون به صرفه‌تره. در واقع هزینه‌ی زمانی رو به هزینه‌ی حافظه تبدیل می‌کنیم.


امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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

 

سوال:   سه هفت  تا؟    (عدد) تا