মৌলিক ধারণা
একটি গতিশীল ডেটা স্ট্রাকচারকে একটি ডেটা স্ট্রাকচার হিসাবে সংজ্ঞায়িত করা হয় যা একটি জ্যামিতিক সিস্টেমের একটি বৈশিষ্ট্যকে ট্র্যাক করার জন্য প্রয়োগ করা হয় যা ক্রমাগত চলছে। উদাহরণস্বরূপ, একটি গতিশীল উত্তল হুল ডেটা স্ট্রাকচার n চলমান বিন্দুগুলির একটি গ্রুপের উত্তল হুলকে ট্র্যাক করে।
গতিশীল ডেটা স্ট্রাকচারের বিকাশ কম্পিউটেশনাল জ্যামিতি সমস্যাগুলির দ্বারা অনুপ্রাণিত হয়েছিল যা অবিচ্ছিন্ন গতিতে ভৌত বস্তুকে জড়িত করে, উদাহরণস্বরূপ রোবোটিক্স, অ্যানিমেশন বা কম্পিউটার গ্রাফিক্সে সংঘর্ষ বা দৃশ্যমানতা সনাক্তকরণ।
ওভারভিউ
গতিগত ডেটা স্ট্রাকচারগুলি এমন সিস্টেমে প্রয়োগ করা হয় যেখানে একটি নামক ফ্যাশনে সময়ের একটি ফাংশন হিসাবে পরিবর্তিত মানগুলির একটি সেট রয়েছে। সুতরাং সিস্টেমের কিছু মান আছে, এবং প্রতিটি সিস্টেমের মান v এর জন্য, এটি নির্দেশ করছে যে v=f(t)। গতিগত ডেটা স্ট্রাকচার বর্তমান ভার্চুয়াল সময়ে একটি সিস্টেমে প্রশ্নের অনুমতি দেয়, এবং দুটি অতিরিক্ত অপারেশন
- advance(t):সিস্টেম টু টাইম টি উন্নত।
- পরিবর্তন(v,f(t)):বর্তমান সময়ের হিসাবে v থেকে f(t) মানের ট্রাজেক্টোরি পরিবর্তিত হয়৷
অতিরিক্ত অপারেশন সমর্থিত হতে পারে. উদাহরণস্বরূপ, গতিগত ডেটা স্ট্রাকচারগুলি প্রায়শই পয়েন্টগুলির একটি সেটের সাথে প্রয়োগ করা হয়। এই ক্ষেত্রে, গঠনটি সাধারণত পয়েন্টগুলিকে সন্নিবেশিত এবং মুছে ফেলার অনুমতি দেয়৷
প্রথাগত ডেটা স্ট্রাকচারের সাথে বৈসাদৃশ্য
একটি গতিগত ডেটা কাঠামো এটিতে সঞ্চিত মানগুলিকে সময়ের সাথে ক্রমাগত পরিবর্তন করার অনুমতি দেয়। নীতিগতভাবে, নির্দিষ্ট সময়ের ব্যবধানে পয়েন্টের অবস্থানের নমুনা করে এবং প্রতিটি বিন্দুকে একটি "স্থির" (ঐতিহ্যগত) ডেটা কাঠামোতে মুছে এবং পুনরায় সন্নিবেশ করে এটি আনুমানিক করা যেতে পারে। যাইহোক, এই ধরনের পদ্ধতিটি ওভারস্যাম্পলিং বা আন্ডারস্যাম্পলিং-এর জন্য সংবেদনশীল, এটি নির্ভর করে সময়ের ব্যবধানের উপর নির্ভর করে এবং গণনামূলক সম্পদের অপচয়ও হতে পারে।
শংসাপত্র পদ্ধতি
গতিশীল ডেটা স্ট্রাকচার তৈরি করতে নিম্নলিখিত সাধারণ পদ্ধতি প্রয়োগ করা যেতে পারে
- বর্তমান সময়ে সিস্টেমে একটি ডেটা স্ট্রাকচার টি সংরক্ষণ করা হয়। এই ডেটা স্ট্রাকচার বর্তমান ভার্চুয়াল সময়ে সিস্টেমে প্রশ্ন করার অনুমতি দেয়।
- শংসাপত্র সহ ডেটা স্ট্রাকচার বর্ধিত করা হয়েছে। শংসাপত্রগুলিকে শর্ত হিসাবে বিবেচনা করা হয় যার অধীনে ডেটা কাঠামো সঠিক। শংসাপত্রগুলি এখন সবই সত্য, এবং ডেটা স্ট্রাকচার শুধুমাত্র তখনই নিখুঁত বা নির্ভুল হওয়া বন্ধ হবে যখন শংসাপত্রগুলির একটি আর সত্য হবে না৷
- প্রতিটি শংসাপত্রের ব্যর্থতার সময় গণনা করা হয়, সেই সময় যখন এটি সত্য হতে বন্ধ হবে৷
- একটি অগ্রাধিকার সারিতে থাকা শংসাপত্রগুলি সংরক্ষণ করা হয়, তাদের ব্যর্থতার সময় দ্বারা চাবি করা হয়৷
- টাইম টি-তে অগ্রসর হতে, অগ্রাধিকার সারি থেকে সর্বনিম্ন ব্যর্থতার সময় সহ শংসাপত্রটি দেখুন। যদি শংসাপত্রটি সময়ের আগে ব্যর্থ হয়, তাহলে সারি থেকে মুছুন বা পপ করুন এবং ডেটা কাঠামো ঠিক করুন যাতে ব্যর্থতার সময় এটি নিখুঁত বা সঠিক হয় এবং শংসাপত্রগুলি আপডেট করুন৷ এটি পুনরাবৃত্তি করুন যতক্ষণ না অগ্রাধিকার সারিতে সর্বনিম্ন ব্যর্থতার সময় সহ শংসাপত্রটি সময়ের পরে ব্যর্থ হয়। অগ্রাধিকার সারিতে ন্যূনতম ব্যর্থতার সময়ের সাথে শংসাপত্রটি যদি t সময়ের পরে ব্যর্থ হয়, তাহলে t সময়ে সমস্ত শংসাপত্র সত্য হিসাবে ঘোষণা করা হয় যাতে ডেটা স্ট্রাকচার টি সময়ে সঠিকভাবে প্রশ্নের উত্তর দিতে পারে।
ইভেন্টের প্রকারগুলি
শংসাপত্র ব্যর্থতাগুলিকে "ইভেন্ট" হিসাবে চিহ্নিত করা হয়। একটি ঘটনা অভ্যন্তরীণ হিসাবে ঘোষণা করা হয় যদি ঘটনা সংঘটনের সময় গতিগত ডেটা কাঠামো দ্বারা রক্ষণাবেক্ষণ করা সম্পত্তি পরিবর্তন না হয়। ঘটনা ঘটার সময় ডেটা স্ট্রাকচার দ্বারা রক্ষণাবেক্ষণ করা সম্পত্তি পরিবর্তন হলে একটি ইভেন্টকে বাহ্যিক হিসাবে ঘোষণা করা হয়।
পারফরম্যান্স
সার্টিফিকেট পদ্ধতি বাস্তবায়ন করার সময়, কর্মক্ষমতার চারটি পরিমাপ আছে। আমরা একটি পরিমাণকে ছোট বলি যদি এটি n এর একটি পলিলোগারিদমিক ফাংশন হয়, অথবা এলোমেলোভাবে ছোট €-এর জন্য O(n€) হয়, যেখানে n কে বস্তুর সংখ্যা হিসাবে গণ্য করা হয়।
