موضوع مقاله: محاسبات افزایشی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # محاسبات افزایشی | مقدمه: محاسبات افزایشی، یک ویژگی نرم‌افزاری است که هرگاه بخشی از داده‌ها تغییر می‌کند، با تنها محاسبه مجدد آن خروجی‌هایی که به داده‌های تغییر یافته بستگی دارد، اقدام به صرفه‌جویی در زمان می‌کند. | ## بخش 1: محاسبات افزایشی | هرگاه محاسبات افزایشی موفقیت‌آمیز باشد، می‌تواند به‌طور قابل توجهی سریعتر از محاسبه ساده انگارانه خروجی‌های جدید باشد. برای مثال، یک بسته نرم‌افزاری صفحه‌گسترده ممکن است از محاسبات افزایشی در ویژگی محاسبه مجدد خود استفاده کند تا فقط آن سلول‌هایی را که شامل فرمول‌های وابسته (مستقیم یا غیرمستقیم) به سلول‌های تغییر یافته هستند، به‌روزرسانی نماید. هنگامی که محاسبات افزایشی توسط ابزاری پیاده‌سازی می‌شود که می‌تواند آن را برای انواع کدهای مختلف به‌طور خودکار پیاده‌سازی کند، آن ابزار نمونه ای از ابزار تحلیل برنامه برای بهینه‌سازی است. برای انجام این کار، ΔP باید یک تغییر در ورودی را به یک تغییر در خروجی مرتبط کند. مصرف‌کننده نتیجه ممکن است به خروجی کامل به روز شده یا خروجی دلتا یا هر دو علاقه‌مند باشد. ایستا در مقابل پویا تکنیک‌های محاسبات افزایشی را می‌توان به‌طور کلی به دو نوع روش تقسیم کرد: رویکردهای ایستا تلاش می‌کنند تا یک برنامه افزایشی را از یک برنامه P معمولی با استفاده از، به عنوان مثال، طراحی دستی و بازآرایی یا تبدیل‌های خودکار برنامه استخراج کنند. رویکردهای پویا اطلاعات مربوط به اجرای برنامه P را روی یک ورودی خاص (I1) ثبت می‌کنند و از این اطلاعات زمانی که ورودی تغییر می‌کند (به I2) برای به‌روزرسانی خروجی (از O1 به O2) استفاده می‌کنند. | ## بخش 2: محاسبات افزایشی | شکل رابطه بین برنامه P، تابع محاسبه تغییر ΔP، که هسته برنامه افزایشی را تشکیل می‌دهد، و یک جفت ورودی و خروجی، I1، O1 و I2، O2 را نشان می‌دهد. رویکردهای تخصصی در مقابل رویکردهای همه منظوره برخی از روش‌های محاسبات افزایشی تخصصی هستند، در حالی که برخی دیگر کلی هستند. روش‌های تخصصی نیاز دارند که برنامه‌نویس الگوریتم‌ها و ساختارهای داده‌ای را که برای حفظ زیرمحاسبات بدون تغییر استفاده می‌شوند، به صراحت مشخص کند. از سوی دیگر، رویکردهای کلی از زبان، کامپایلر یا تکنیک‌های الگوریتمی برای دادن رفتار افزایشی به برنامه‌های غیرافزاینده استفاده می‌کنند. روش‌های ایستا مشتقات برنامه با توجه به یک محاسبات و یک تغییر بالقوه ، می‌توانیم کد را قبل از تغییر (پیش از مشتق) و بعد از تغییر (پس از مشتق) وارد کنیم تا مقدار سریعتر از اجرای مجدد به‌روز شود. نگهداری نمای افزایشی به‌طور ایستا جبر نسبی را تجزیه و تحلیل می‌کند تا قوانین به‌روز شده را ایجاد کند که در حضور به‌روز رسانی‌های کوچک، مانند درج یک ردیف، به سرعت نما را حفظ کند. روش‌های پویا محاسبات افزایشی را می‌توان با ساختن یک نمودار وابستگی از تمام اجزای داده‌ای که ممکن است نیاز به محاسبه مجدد داشته باشند و وابستگی‌شان به دست آورد. | ## بخش 3: محاسبات افزایشی | اجزایی که باید با تغییر یک عنصر به روز شوند، به کمک بستار تعدی رابطه وابستگی نمودار داده می‌شوند. به عبارت دیگر، اگر مسیری از جزء تغییر یافته به جزء دیگر وجود داشته باشد، امکان دارد دومی به روز شود (بسته به اینکه آیا تغییر در نهایت به جزء می‌رسد یا خیر). با تغییر وابستگی‌ها، یا افزوده شدن یا حذف اجزا به سیستم، نمودار وابستگی ممکن است نیاز به به‌روز رسانی داشته باشد. که به صورت داخلی توسط پیاده‌سازی استفاده می‌شود و معمولاً نیازی به نمایش به کاربر ندارد. به کمک شناسایی زیرمجموعه‌ای از مقادیر مهم (مثل نتایج تجمیع) که می‌توان وابستگی‌ها را در آن‌ها ردیابی کرد، و نیز محاسبه مجدد تدریجی سایر متغیرهای وابسته که مقدار اطلاعات وابستگی که باید با تغییر ورودی انجام شود، ردیابی شده و متعادل شود، از گرفتن وابستگی‌ها در تمام مقادیر ممکن اجتناب کرد. ارزیابی جزئی را می‌توان به عنوان یک روش برای خودکارسازی ساده‌ترین حالت ممکن محاسبات افزایشی در نظر گرفت، که در آن اقدام به تقسیم داده‌ها به دو دسته می‌کند: آنهایی که می‌توانند بر اساس ورودی برنامه متفاوت باشند، و آنهایی که نمی‌توانند (و کوچکترین واحد تغییر به سادگی "همه داده‌هایی است که می‌توانند متفاوت باشند"). با چرخه‌های موجود در نمودار وابستگی، یک عبور از نمودار ممکن است برای رسیدن به یک نقطه ثابت کافی نباشد. | ## جمع‌بندی | در برخی موارد، ارزیابی مجدد و کامل یک سیستم از نظر معنایی معادل ارزیابی افزایشی است و ممکن است در عمل کارآمدتر از درحالت تئوری باشد.