الدرس 24: المسح المتوازي (Parallel Scan / Prefix Sum) — الفكرة
المسح (scan)، أو مجموع البادئات (prefix sum)، يحوّل مصفوفة إلى متتالية من مجاميعها المتراكمة. في المسح الشامل (inclusive) يكون الخرج في الموضع i هو مجموع كل العناصر من 0 حتى i شاملًا: output[i] = in[0] + in[1] + ... + in[i]. مثلًا [3,1,2,4] يصبح [3,4,6,10]. وهناك أيضًا نوع حصري (exclusive) يبدأ من ا
تخيّل صفًا من الناس، كل واحد يحمل رقمًا، وعلى كل واحد أن ينتهي وهو يحمل مجموع كل من قبله، بما في ذلك نفسه. بدلًا من الهمس من جار إلى جار ببطء، في كل جولة يضيف كل واحد رقم الشخص الذي يبعد عنه خطوة واحدة إلى يساره، ثم خطوتين، ثم أربعًا. القفزات تتضاعف — وينتهي الصف بأكمله في بضع جولات فقط.
- مجموع البادئات (prefix sum / scan)
- تحويل مصفوفة إلى مجاميعها المتراكمة. في المسح الشامل، يكون output[i] هو مجموع in[0..i] شاملًا.
- الشامل مقابل الحصري (inclusive vs exclusive)
- الشامل: كل خرج يشمل العنصر في موضعه ([3,1,2,4]->[3,4,6,10]). الحصري: يبدأ من الصفر ويزيح نحو اليمين ([0,3,4,6]).
- فكرة المضاعفة (doubling)
- في كل جولة يضيف كل عنصر الجار على بُعد d، و d يتضاعف (1,2,4,...). بعد log2(n) جولة يكون كل موضع قد راكم كل الأسلاف.
- المجموع المتراكم (running total)
- المجموع المتراكم حتى نقطة معينة. النسخة التسلسلية تحسبه في حلقة واحدة في O(n) خطوة.
