Kinetic data structure
حرکی ڈیٹا ڈھانچہ ایک ڈیٹا ڈھانچہ ہے جو ہندسی نظام کی خاصیت کو ٹریک کرنے کے لیے استعمال ہوتا ہے جو مسلسل حرکت کر رہا ہے۔ مثال کے طور پر، ایک حرکی کنویکس ہل ڈیٹا ڈھانچہ حرکت پذیر پوائنٹس کے گروپ کے کنویکس ہل کو برقرار رکھتا ہے۔ حرکی ڈیٹا ڈھانچوں کی ترقی کمپیوٹیشنل جیومیٹری کے مسائل سے متاثر تھی جس میں جسمانی اشیاء مسلسل حرکت میں شامل ہوتی ہیں، جیسے روبوٹکس، حرکت پذیری یا کمپیوٹر گرافکس میں تصادم یا مرئیت کا پتہ لگانا۔ جائزہ حرکی ڈیٹا ڈھانچے ان نظاموں پر استعمال ہوتے ہیں جہاں اقدار کا ایک مجموعہ ہوتا ہے جو وقت کی تقریب کے طور پر، معروف انداز میں تبدیل ہو رہے ہوتے ہیں۔ لہذا نظام کی کچھ اقدار ہوتی ہیں، اور ہر قدر کے لیے، یہ معلوم ہوتا ہے کہ۔ حرکی ڈیٹا ڈھانچے موجودہ ورچوئل وقت پر سسٹم پر سوالات کی اجازت دیتے ہیں، اور دو اضافی کارروائیاں:: سسٹم کو وقت کے ساتھ آگے بڑھاتا ہے۔ : موجودہ وقت کے مطابق قدر کی رفتار کو تبدیل کرتا ہے۔ اضافی کارروائیوں کی حمایت کی جا سکتی ہے۔ مثال کے طور پر، حرکی ڈیٹا ڈھانچے اکثر پوائنٹس کے ایک سیٹ کے ساتھ استعمال ہوتے ہیں۔ اس صورت میں، ڈھانچہ عام طور پر پوائنٹس کو داخل کرنے اور حذف کرنے کی اجازت دیتا ہے۔ روایتی ڈیٹا ڈھانچے کے ساتھ موازنہ ایک حرکی ڈیٹا ڈھانچہ اس میں محفوظ کردہ اقدار کو وقت کے ساتھ مسلسل تبدیل کرنے کی اجازت دیتا ہے۔ اصولی طور پر، وقت کے مقررہ وقفوں پر پوائنٹس کی پوزیشن کا نمونہ لے کر، اور ہر پوائنٹ کو "جامد" (روایتی) ڈیٹا ڈھانچے میں حذف اور دوبارہ داخل کرکے اس کا تخمینہ لگایا جا سکتا ہے۔ تاہم، اس طرح کا نقطہ نظر اوور سیمپلنگ یا انڈر سیمپلنگ کے لیے کمزور ہے، اس پر منحصر ہے کہ وقت کا کون سا وقفہ استعمال کیا جاتا ہے، اور کمپیوٹیشنل وسائل کا ضیاع بھی ہو سکتا ہے۔ سرٹیفکیٹ کا نقطہ نظر حرکی ڈیٹا ڈھانچے کی تعمیر کے لیے درج ذیل عمومی نقطہ نظر استعمال کیا جا سکتا ہے: موجودہ وقت میں سسٹم پر ڈیٹا ڈھانچہ محفوظ کریں۔ یہ ڈیٹا ڈھانچہ موجودہ ورچوئل وقت پر سسٹم پر سوالات کی اجازت دیتا ہے۔ سرٹیفکیٹ کے ساتھ ڈیٹا ڈھانچے کو بڑھائیں۔ سرٹیفکیٹ وہ حالات ہیں جن کے تحت ڈیٹا کا ڈھانچہ درست ہوتا ہے۔ سرٹیفکیٹ اب تمام درست ہیں، اور ڈیٹا کا ڈھانچہ صرف اس وقت درست نہیں رہے گا جب سرٹیفکیٹ میں سے ایک درست نہیں رہے گا۔ ہر سرٹیفکیٹ کے ناکامی کے وقت کا حساب لگائیں، وہ وقت جب یہ درست نہیں رہے گا۔ سرٹیفکیٹ کو ترجیحی قطار میں محفوظ کریں، جس کی کلید ان کے ناکامی کے اوقات سے ہوتی ہے۔ وقت کی طرف بڑھنے کے لیے، ترجیحی قطار سے سب سے کم ناکامی کے وقت کے ساتھ سرٹیفکیٹ کو دیکھیں۔ اگر سرٹیفکیٹ وقت سے پہلے ناکام ہوجاتا ہے، تو اسے قطار سے نکالیں اور ڈیٹا ڈھانچے کو ٹھیک کریں تاکہ یہ ناکامی کے وقت درست ہو، اور سرٹیفکیٹ کو اپ ڈیٹ کریں۔ اسے اس وقت تک دہرائیں جب تک کہ ترجیحی قطار میں سب سے کم ناکامی کا وقت والا سرٹیفکیٹ وقت کے بعد ناکام نہ ہو جائے۔ اگر ترجیحی قطار میں سب سے کم ناکامی کے وقت والا سرٹیفکیٹ وقت کے بعد ناکام ہو جاتا ہے، تو تمام سرٹیفکیٹ وقت پر درست ہوتے ہیں تاکہ ڈیٹا ڈھانچہ وقت پر سوالات کا درست جواب دے سکے۔ واقعات کی اقسام سرٹیفکیٹ کی ناکامیوں کو "واقعات" کہا جاتا ہے۔ ایک واقعہ کو اندرونی سمجھا جاتا ہے اگر حرکت پذیری ڈیٹا ڈھانچے کے ذریعہ برقرار رکھی گئی خاصیت واقعہ ہونے پر تبدیل نہیں ہوتی ہے۔ ایک واقعہ کو بیرونی سمجھا جاتا ہے اگر واقعہ ہونے پر ڈیٹا ڈھانچے کے ذریعہ برقرار رکھی گئی پراپرٹی بدل جاتی ہے۔ کارکردگی سرٹیفکیٹ کے نقطہ نظر کا استعمال کرتے وقت، کارکردگی کے چار اقدامات ہوتے ہیں۔ ہم کہتے ہیں کہ مقدار چھوٹی ہوتی ہے اگر یہ ایک پولی لوگرتھمک فنکشن ہے، یا من مانی طور پر چھوٹی ہے، جہاں اشیاء کی تعداد ہے: رسپانسیونیس رسپانسیونیس ڈیٹا اسٹرکچر کو ٹھیک کرنے اور سرٹیفکیٹ کے ناکام ہونے پر سرٹیفکیٹ کو بڑھانے کے لیے درکار وقت کی بدترین صورت ہے۔ ایک حرکی ڈیٹا ڈھانچہ ذمہ دار ہوتا ہے اگر کسی اپ ڈیٹ کے لیے درکار وقت کی بدترین صورت کم ہو۔ لوکلٹی سرٹیفکیٹ کی زیادہ سے زیادہ تعداد کسی بھی ایک قدر میں شامل ہے۔ حرکت پذیر پوائنٹس پر مشتمل ڈھانچوں کے لیے، یہ ہے کہ کسی بھی ایک پوائنٹ میں سرٹیفکیٹ کی زیادہ سے زیادہ تعداد شامل ہے۔ ایک حرکی ڈیٹا ڈھانچہ مقامی ہوتا ہے اگر کسی ایک قدر کے ساتھ سرٹیفکیٹ کی زیادہ سے زیادہ تعداد کم ہو۔ کمپیکٹنس کسی بھی وقت ڈیٹا ڈھانچے کو بڑھانے کے لیے استعمال ہونے والے سرٹیفکیٹ کی زیادہ سے زیادہ تعداد۔ ایک حرکی ڈیٹا ڈھانچہ کمپیکٹ ہوتا ہے اگر اس کے استعمال کردہ سرٹیفکیٹ کی تعداد یا من مانی طور پر کم ہو۔ (لکیری اسپیس سے زیادہ ایک چھوٹا عنصر) کارکردگی واقعات کی بدترین صورت کی تعداد کا تناسب جو اس وقت ہو سکتا ہے جب ڈھانچہ ڈیٹا ڈھانچے میں "ضروری تبدیلیوں" کی بدترین صورت کی تعداد تک پہنچ جاتا ہے۔ "ضروری تبدیلیوں" کی تعریف مسئلہ پر منحصر ہے۔ مثال کے طور پر، حرکت پذیر پوائنٹس کے سیٹ کے حرکی ہل کو برقرار رکھنے والے حرکی ڈیٹا ڈھانچے کی صورت میں، ضروری تبدیلیوں کی تعداد وقت کے ساتھ ساتھ حرکی ہل کی تبدیلیوں کی تعداد ہوگی۔ اگر یہ تناسب چھوٹا ہو تو حرکی ڈیٹا ڈھانچہ موثر کہا جاتا ہے۔ راستوں کی اقسام مخصوص قسم کے راستوں کے لیے ایک مخصوص حرکی ڈیٹا ڈھانچے کی کارکردگی کا تجزیہ کیا جا سکتا ہے۔ عام طور پر، درج ذیل قسم کے راستوں پر غور کیا جاتا ہے: افائن: (لکیری افعال) باؤنڈ ڈگری الجبرائی: (باؤنڈ ڈگری کے کثیر الجہتی افعال) کچھ فکسڈ کے لیے۔ فرضی الجبرائی: ٹریجیکٹریز ایسی ہوتی ہیں کہ سود کا کوئی بھی سرٹیفکیٹ صحیح اور غلط اوقات کے درمیان پلٹ جائے۔ مثال حرکی ٹورنامنٹ حرکی ترتیب شدہ فہرست حرکی ڈھیر حرکی کنویکس ہل حرکی قریب ترین جوڑی حرکی کم از کم پھیلے ہوئے درخت حرکی یوکلڈین کم از کم پھیلے ہوئے درخت حوالہ جات حرکی ڈیٹا ڈھانچے