Incremental computing with data structures

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