جمع پیشوندی

نحوه پیاده‌سازی جمع پیشوندی در زبان‌های جاوا، پایتون و سی {به انگلیسی:به ترتیب: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 می‌باشد. ساخت جمع پیشوندی موازی ۲ مرحله دارد:

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

در این مرحله، درخت دودویی ساخته می‌شود که هر گرهٔ آن، جمع پیشوندی یک بازه مشخص را در خود نگه می‌دارد. ریشهٔ درخت، جمع پیشوندی بازهٔ کل اعداد ورودی را نگه می‌دارد. اگر گره‌ای، جمع پیشوندی بازهٔ ${\displaystyle (x,y)}$

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

هر گره یک دادهٔ اضافی به نام «از چپ» را نگه می‌دارد. به ریشهٔ درخت مقدار «از چپ» صفر داده می‌شود. فرزند چپ هر گره، مقدار «از چپ» را از پدر خود می‌گیرد، فرزند راست هر گره، مجموعی از مقادیر «از چپ» پدر و جمع پیشوندی بازهٔ ذخیره‌شده در فرزند چپ گره پدر را نگه می‌دارد. در نهایت، خروجی ${\displaystyle i}$

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