ساختار داده‌های ماندگار

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

یک ساختار داده‌ای به طور جزئی پایدار است اگر بتوان به تمام نگارش‌ها دسترسی پیدا کند اما تنها جدیدترین نگارش می‌تواند تعدیل شده باشد. ساختار داده‌ای کاملاً پایدار است اگر هر نگارش هم در دسترس باشد و هم تعدیل شود.اگر در اینجا عملیاتی بود که از ترکیب دو ورژن قبل یک ورژن جدید خلق می‌کرد ساختار داده‌ای پایدار ترکیبی فراخوانی شده بود. این ساختار دادها (پایدار)نامیده می‌شود.ساختاری که(پایدار) نیست گذرا نامیده می‌شود این ساختار داده‌ها بیشتر (منحصراً) در برنامه نویسی تابعی ومنطقی رواج دارند ودر یک برنامه کاملاً تابعی تمام داده‌ها تغییر ناپذیر هستند. بنابر این تمام ساختار دادها به صورت خود کار کاملاً پایدار هستند.ساختار داده‌ها ی پایدار نیز می‌توانند با بروز کردن داده‌ها در همین نسخه بوجود بیایند و این کار عموماً باعث می‌شود که زمان وفضای ذخیره کمتری ازنمونه کاملاً تابعی مورد استفاده قرار بگیرند. در حالیکه پایداغری داده‌ها می‌تواند خیلی ساده از طریق کپی کردن صورت بگیرد اما این کار از لحاظ فضا و زمان کارایی ندارد چون بیشتر عملیاتی که انجام می‌شود تغییرات مختصری در ساختار داده‌ها بوجود می‌آورد. یک روش بهتر این است که از شباهت‌هایی که بین ورژنهای جدید وقدیم وجود دارد استفاده کنیم تا از ساختار بین آنها به نسبت مساوی بهره ببریم مانند استفاده از فرعی که در تعدادی از ساختارهای درختی موجود است. به هر حال از آنجایی که به سرعت امکان پذیر نیست که مشخص شود که چند تا ورژن قبلی در این کار وجود دارد که چه قسمت‌هایی از ساختار وبه دلیل اینکه غالب اوقات مطلوب آن که ورژنهای قدیمی منسوخ شده‌اند این امر مستلزم این است که با جمع آوری کلکسیون‌های منسوخ ایجاد شود. شاید ساده‌ترین ساختار داده‌ای ماندگار لیست linked-singly یا لیست based-cons باشد.یک لیست ساده فرم اهداف به وسیله هر یک مراجع حامل به لیست بعد است. این پایدار است زیرا ما می‌توانیم یک انتها از لیست را بگیریم، به معنی k آیتم قبلی برای k تا و اضافه کنیم به انتهای آن. این دنباله ممکن است دو نسخه‌ای نباشد ولی در عوض مناسب برای هر دو نسخه جدید و قدیم خواهد بود. تعدادی از منابع پایدار ساختار داده‌ها از قبیل درخت black-red و صفها می‌توانند به راحتی با نسخه‌های پایدار متناسب شوند. یک نسخه پایدار آرایه‌ای ساختار داده‌ای Vlistتوسط phil bagwellتشریح شده‌است.