جمع پیشوندی

در علوم کامپیوتر، جمع پیشوندی به آرایه‌ای گفته می‌شود که هر عنصر آن ($y_{0},y_{1},y_{2},...$) از جمع چند عدد ورودی متوالی به صورت زیر حاصل می‌شود.

$y_{0}=x_{0}$

$y_{1}=x_{0}+x_{1}$

$y_{2}=x_{0}+x_{1}+x_{2}$

$...$

برای نمونه، به جدول زیر توجه کنید.

اعداد ورودی	۱	۵	۱۰	۳	۷	۹
جمع پیشوندی	۱	۶	۱۶	۱۹	۲۶	۳۵

همچنین می‌توان با درنظرگرفتن $y_{0}=x_{0}$, $y_{i}$ را با استفاده از فرمول $y_{i}=y_{i-1}+x_{i}$ بدست آورد. علی‌رغم سادگی در پیاده‌سازی، جمع پیشوندی در الگوریتم‌های خاص همچون مرتب‌سازی شمارشی، در زبان‌های برنامه‌نویسی تابعی در تشکیل پایه‌ای برای اسکن توابع مرتبه بالا و در الگوریتم‌های موازی مورد مطالعه قرار گرفته‌است. زمان صرف‌شده برای محاسبهٔ جمع پیشوندی از مرتبهٔ (O(n می‌باشد، حافظه‌ای که برای ساختن آن صرف می‌شود نیز (O(n می‌باشد اما در جمع پیشوندی موازی می‌توان حافظهٔ استعمال‌شده را به (O(logn کاهش داد.

جمع پیشوندی یک آرایهٔ ۴تایی

پیاده‌سازی

نحوه پیاده‌سازی جمع پیشوندی در زبان‌های جاوا، پایتون و سی {به انگلیسی:به ترتیب:C, python, java} نشان داده شده‌است.

پیاده‌سازی با کد C

int* prefixSums(int[] input, int[] output, int length) {
    output[0] = input[0];
    int i;
    for (i = 1; i <length; i++)
        output[i] = output[i - 1] + input[i];

    return output;

پیاده‌سازی با کد جاوا

static int[] prefixSums(int[] input, int[] output) {
    output[0] = input[0];
    for(int i = 0; i <input.length; i++)
        output[i] = output[i - 1] + input[i];
    return output;
}

پیاده‌سازی پایتون

def prefixSums(input, output):
    output[0] = input[0];
    for i in range(1, len(input)):
        output[i] = output[i - 1] + input[i]

کاربردها

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

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

یکی از داده ساختارهای پرکاربرد برای ذخیره‌سازی مجموعه‌ای از اطلاعات که به‌طور پیوسته به‌روزرسانی می‌شود یا به آن اطلاعات جدیدی اضافه می‌شود، درخت فنویک است. درخت فنویک مجموع چند عدد اول یک آرایه، به همراه به‌روزرسانی کردن عناصر آن آرایه را در مرتبه زمانی (O(logn انجام می‌دهد. این درخت برای محاسبهٔ مجموع چند عدد اول یک آرایه به همراه به‌روزرسانی، از جمع پیشوندی استفاده می‌کند.

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

همچنین در پیشوندهای موازی (استفاده از ضرب به عنوان عملیات متداول پایه) می‌تواند برای ساخت الگوریتم‌های سریع برای درون‌یابی چندجمله‌ای موازی استفاده شود. به‌طور خاص، می‌توان از آن برای محاسبهٔ ضرایب تقسیم فرم نیوتن در چندجمله‌ای‌های درون‌یابی استفاده کرد.

اسکن توابع مرتبه بالا

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

اعداد ورودی	۲۵۲۰	۵	۷	۹	۸	۱
تقسیم پیشوندی	۲۵۲۰	۵۰۴	۷۲	۸	۱	۱

جمع پیشوندی موازی

مزیتی که جمع پیشوندی موازی نسبت به غیر موازی دارد، حافظه به کارگرفته‌شده می‌باشد. حافظهٔ جمع پیشوندی موازی از مرتبه (O(logn می‌باشد در حالی‌که حافظهٔ به کارگرفته‌شده در حالت غیرموازی از مرتبهٔ (O(n می‌باشد. ساخت جمع پیشوندی موازی ۲ مرحله دارد:

مرحله ۱:ساخت یک درخت دودویی

در این مرحله، درخت دودویی ساخته می‌شود که هر گرهٔ آن، جمع پیشوندی یک بازه مشخص را در خود نگه می‌دارد. ریشهٔ درخت، جمع پیشوندی بازهٔ کل اعداد ورودی را نگه می‌دارد. اگر گره‌ای، جمع پیشوندی بازهٔ $(x,y)$ را در خود نگه دارد، فرزند چپ آن بازهٔ $(x,(x+y)/2)$ و فرزند راست آن بازهٔ $((x+y)/2,y)$ را نگه می‌دارد. همچنین هر برگ این درخت، بازهٔ $[i,i+1)$را نگه می‌دارد که برابر است با ورودی عنصر $i$ام. همان‌طور که ملاحظه می‌شود برای ساخت این درخت دودویی از الگوریتم تقسیم و حل استفاده می‌شود.

نحوهٔ ساخت جمع پیشوندی موازی در مرحلهٔ اول، با توجه به مثال آورده‌شده در شکل

مرحله ۲: پاس دادن مقدار «از چپ» {انگلیسی: from left} و ساخت آرایهٔ خروجی

هر گره یک دادهٔ اضافی به نام «از چپ» را نگه می‌دارد. به ریشهٔ درخت مقدار «از چپ» صفر داده می‌شود. فرزند چپ هر گره، مقدار «از چپ» را از پدر خود می‌گیرد، فرزند راست هر گره، مجموعی از مقادیر «از چپ» پدر و جمع پیشوندی بازهٔ ذخیره‌شده در فرزند چپ گره پدر را نگه می‌دارد. در نهایت، خروجی $i$ام آرایهٔ جمع پیشوندی از جمع مقادیر «از چپ» برگ $i$ام با جمع پیشوندی بازهٔ ذخیره‌شده در آن برگ (بازهٔ $[i,i+1)$) حاصل می‌شود.

نحوهٔ ساخت جمع پیشوندی در مرحلهٔ دوم

جستارهای وابسته

• الگوریتم‌های موازی
• درخت دودویی
• توابع مرتبه بالا
• الگوریتم تقسیم و حل
• مرتب‌سازی شمارشی