Kinetic data structure
একটি কাইনেটিক ডেটা স্ট্রাকচার হল একটি ডেটা স্ট্রাকচার যা একটি জ্যামিতিক সিস্টেমের একটি বৈশিষ্ট্য ট্র্যাক করতে ব্যবহৃত হয় যা ক্রমাগত চলছে। উদাহরণস্বরূপ, একটি গতিময় উত্তল কাঠামো গতিশীল বিন্দুর একটি গোষ্ঠীর উত্তল কাঠামো বজায় রাখে। গতিজ তথ্য কাঠামোর বিকাশ ক্রমাগত গতিতে শারীরিক বস্তুর সাথে জড়িত গণনামূলক জ্যামিতি সমস্যা দ্বারা অনুপ্রাণিত হয়েছিল, যেমন রোবোটিক্স, অ্যানিমেশন বা কম্পিউটার গ্রাফিক্সে সংঘর্ষ বা দৃশ্যমানতা সনাক্তকরণ। কিনেটিক ডেটা স্ট্রাকচারগুলি এমন সিস্টেমে ব্যবহার করা হয় যেখানে একটি পরিচিত ফ্যাশনে সময়ের ফাংশন হিসাবে পরিবর্তিত হওয়া মানগুলির একটি সেট রয়েছে। সুতরাং সিস্টেমের কিছু মান রয়েছে এবং প্রতিটি মানের জন্য, এটি জানা যায়। কাইনেটিক ডেটা স্ট্রাকচারগুলি বর্তমান ভার্চ্যুয়াল সময়ে একটি সিস্টেমে প্রশ্নের অনুমতি দেয় এবং দুটি অতিরিক্ত ক্রিয়াকলাপের অনুমতি দেয়ঃ : বর্তমান সময়ের হিসাবে মানের গতিপথ পরিবর্তন করে। অতিরিক্ত অপারেশনগুলি সমর্থিত হতে পারে। উদাহরণস্বরূপ, কাইনেটিক ডেটা স্ট্রাকচারগুলি প্রায়শই পয়েন্টগুলির একটি সেটের সাথে ব্যবহৃত হয়। এই ক্ষেত্রে, কাঠামোটি সাধারণত পয়েন্টগুলি ঢোকানো এবং মুছে ফেলার অনুমতি দেয়। ঐতিহ্যবাহী তথ্য কাঠামোর সাথে বৈপরীত্য একটি গতিজ তথ্য কাঠামো এতে সঞ্চিত মানগুলিকে সময়ের সাথে অবিচ্ছিন্নভাবে পরিবর্তন করতে দেয়। নীতিগতভাবে, নির্দিষ্ট সময়ের ব্যবধানে পয়েন্টগুলির অবস্থানের নমুনা নিয়ে এবং প্রতিটি পয়েন্টকে "স্ট্যাটিক" (ঐতিহ্যবাহী) ডেটা স্ট্রাকচারে মুছে দিয়ে পুনরায় সন্নিবেশ করে এটি আনুমানিকভাবে অনুমান করা যেতে পারে। যাইহোক, কোন সময়ের ব্যবধান ব্যবহার করা হয় তার উপর নির্ভর করে এই ধরনের পদ্ধতি ওভারসাম্পলিং বা আন্ডারসাম্পলিংয়ের জন্য ঝুঁকিপূর্ণ এবং গণনামূলক সম্পদের অপচয়ও হতে পারে। শংসাপত্রের পদ্ধতি কাইনেটিক ডেটা স্ট্রাকচার তৈরি করতে নিম্নলিখিত সাধারণ পদ্ধতিটি ব্যবহার করা যেতে পারেঃ বর্তমান সময়ে সিস্টেমে একটি ডেটা স্ট্রাকচার সংরক্ষণ করুন। এই তথ্য কাঠামোটি বর্তমান ভার্চ্যুয়াল সময়ে সিস্টেমে প্রশ্নের অনুমতি দেয়। শংসাপত্রের মাধ্যমে তথ্য কাঠামো বৃদ্ধি করুন। শংসাপত্র হল এমন শর্ত যার অধীনে তথ্য কাঠামো সঠিক হয়। শংসাপত্রগুলি এখন সমস্ত সত্য, এবং তথ্য কাঠামো কেবল তখনই সঠিক হবে যখন শংসাপত্রগুলির মধ্যে একটি আর সত্য হবে না। প্রতিটি শংসাপত্রের ব্যর্থতার সময় গণনা করুন, যে সময় এটি সত্য হবে না। একটি অগ্রাধিকার সারিতে শংসাপত্রগুলি সংরক্ষণ করুন, যা তাদের ব্যর্থতার সময় দ্বারা চিহ্নিত করা হয় সময়ের সাথে এগিয়ে যাওয়ার জন্য, অগ্রাধিকার সারি থেকে সর্বনিম্ন ব্যর্থতার সময় সহ শংসাপত্রটি দেখুন। যদি শংসাপত্রটি সময়ের আগে ব্যর্থ হয়, তবে এটি সারি থেকে পপ করুন এবং ডেটা স্ট্রাকচারটি ঠিক করুন যাতে এটি ব্যর্থতার সময় সঠিক হয় এবং শংসাপত্রগুলি আপডেট করে। অগ্রাধিকার সারিতে সর্বনিম্ন ব্যর্থতার সময় সহ শংসাপত্রটি সময়ের পরে ব্যর্থ না হওয়া পর্যন্ত এটি পুনরাবৃত্তি করুন। অগ্রাধিকার সারিতে সর্বনিম্ন ব্যর্থতার সময় সহ শংসাপত্রটি যদি সময়ের পরে ব্যর্থ হয়, তবে সমস্ত শংসাপত্রগুলি সময়ে সঠিক হয় যাতে ডেটা কাঠামো সঠিকভাবে প্রশ্নের উত্তর দিতে পারে। ইভেন্টের ধরন সার্টিফিকেট ব্যর্থতাকে "ইভেন্ট" হিসাবে উল্লেখ করা হয়। একটি ইভেন্টকে অভ্যন্তরীণ হিসাবে বিবেচনা করা হয় যদি কাইনেটিক ডেটা স্ট্রাকচার দ্বারা রক্ষণাবেক্ষণ করা বৈশিষ্ট্যটি ইভেন্টটি ঘটার সময় পরিবর্তিত না হয়। একটি ইভেন্টকে বাহ্যিক হিসাবে বিবেচনা করা হয় যদি ইভেন্টটি ঘটলে ডেটা স্ট্রাকচার দ্বারা রক্ষণাবেক্ষণ করা সম্পত্তি পরিবর্তিত হয়। কর্মক্ষমতা শংসাপত্র পদ্ধতি ব্যবহার করার সময়, কর্মক্ষমতার চারটি পরিমাপ রয়েছে। আমরা বলি যে একটি পরিমাণ ছোট হয় যদি এটি একটি পলিলোগারিদমিক ফাংশন হয়, বা নির্বিচারে ছোট হয়, যেখানে বস্তুর সংখ্যাঃ প্রতিক্রিয়াশীলতা প্রতিক্রিয়াশীলতা হল তথ্য কাঠামো ঠিক করার জন্য এবং একটি শংসাপত্র ব্যর্থ হলে শংসাপত্রগুলি বাড়ানোর জন্য প্রয়োজনীয় সময়ের সবচেয়ে খারাপ পরিমাণ। একটি কাইনেটিক ডেটা স্ট্রাকচার প্রতিক্রিয়াশীল হয় যদি কোনও আপডেটের জন্য সবচেয়ে খারাপ সময়ের প্রয়োজন হয়। স্থানীয়তা যে কোনও একটি মূল্যের সাথে জড়িত শংসাপত্রের সর্বাধিক সংখ্যা। চলমান পয়েন্টগুলির সাথে জড়িত কাঠামোগুলির জন্য, এটি যে কোনও একটি পয়েন্টের সাথে সর্বাধিক সংখ্যক শংসাপত্র জড়িত। একটি কাইনেটিক ডেটা স্ট্রাকচার স্থানীয় হয় যদি কোনও একটি মানের সাথে জড়িত শংসাপত্রের সর্বাধিক সংখ্যা ছোট হয়। কম্প্যাক্টনেস যে কোনও সময়ে ডেটা কাঠামো বাড়ানোর জন্য ব্যবহৃত শংসাপত্রের সর্বাধিক সংখ্যা। একটি কাইনেটিক ডেটা স্ট্রাকচার কম্প্যাক্ট হয় যদি এটি ব্যবহার করা শংসাপত্রের সংখ্যা বা নির্বিচারে ছোট হয়। (রৈখিক স্থানের চেয়ে একটি ছোট ফ্যাক্টর বেশি) দক্ষতা হল সবচেয়ে খারাপ ঘটনার অনুপাত যা ঘটতে পারে যখন কাঠামোটি ডেটা কাঠামোর "প্রয়োজনীয় পরিবর্তনের" সবচেয়ে খারাপ ক্ষেত্রে অগ্রসর হয়। "প্রয়োজনীয় পরিবর্তন"-এর সংজ্ঞা সমস্যা নির্ভর। উদাহরণস্বরূপ, চলন্ত বিন্দুর একটি সেটের গতিজ কাঠামো বজায় রাখার ক্ষেত্রে, প্রয়োজনীয় পরিবর্তনের সংখ্যা হবে সময়ের সাথে সাথে গতিজ কাঠামো কতবার পরিবর্তিত হয়। একটি কাইনেটিক ডেটা স্ট্রাকচারকে কার্যকর বলা হয় যদি এই অনুপাতটি ছোট হয়। গতিপথের প্রকার একটি নির্দিষ্ট গতিগত তথ্য কাঠামোর কার্যকারিতা নির্দিষ্ট ধরনের গতিপথের জন্য বিশ্লেষণ করা যেতে পারে। সাধারণত, নিম্নলিখিত ধরনের গতিপথ বিবেচনা করা হয়ঃ এফাইনঃ (লিনিয়ার ফাংশন) বাউন্ডেড-ডিগ্রি বীজগাণিতিকঃ (বাউন্ডেড ডিগ্রির পলিনোমিয়াল ফাংশন) কিছু স্থিরের জন্য। ছদ্ম-বীজগাণিতিকঃ ট্র্যাজেক্টরিগুলি এমন যে কোনও সুদের শংসাপত্র সত্য এবং মিথ্যা সময়ের মধ্যে উল্টে যায়। উদাহরণ কাইনেটিক টুর্নামেন্ট কাইনেটিক সাজানো তালিকা কাইনেটিক হিপ কাইনেটিক উত্তল হুল কাইনেটিক নিকটতম জোড়া কাইনেটিক মিনিমাম স্প্যানিং ট্রি কাইনেটিক ইউক্লিডিয়ান মিনিমাম স্প্যানিং ট্রি রেফারেন্স কাইনেটিক ডেটা স্ট্রাকচার