ما هي أفضل خوارزمية للعثور على مجموع جميع العناصر في مصفوفة فرعية عشوائية

Question

لدي مشكلة ، وحل موافق العش.آمل أن يكون هناك حل أفضل هناك.

المشكلة

لدي مجموعة مع حوالي 200 ، 000 الأعداد الصحيحة.بالنظر إلى مؤشرين ، أنا1 و أنا2 ، أحتاج إلى حساب مجموع كل العناصر بين أنا1 و أنا2.كل عدد صحيح في الصفيف ما بين 1 و 4 شاملة.على سبيل المثال:

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

سيتم تنفيذ هذه العملية حوالي 200000 مرة ، لذلك يجب أن تكون سريعة جدا.عداد بسيط في حلقة هو س (ن) ، وبطيئة جدا.لا يتم تعديل المصفوفة أبدا بعد الإنشاء ، لذلك لا بأس في الحصول على مرحلة معالجة مسبقة باهظة الثمن نسبيا.

أفضل حل لي حتى الآن

هذه الخوارزمية تعمل في س (سجل ن) الوقت:

أول لوحة الصفيف الأصلي مع الأصفار حتى طوله هو قوة اثنين.بعد ذلك ، تقسيم مجموعة إلى قسمين متساويين وتخزين مجموع كل منهما.ثم تقسيم الصفيف إلى أرباع وتخزين مجموع كل منها.ثم الثمان.استمر في القيام بذلك حتى يتم تقسيم المصفوفة إلى أقسام 2 عناصر طويلة.بالنسبة إلى المصفوفة المكونة من 8 عناصر أعلاه ، يستغرق ذلك خطوتين:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

ثم بالنظر إلى مؤشرين ، أصبح من الممكن الآن العمل على القسم الفرعي_المجموع في ا(سجل ن) زمن.على سبيل المثال ، القسم الفرعي_المجموع(أ ، 2 ، 7) == أرباع[1] + نصفين[1].

Answer 1

أدخل مصفوفة مساعدة تحتوي على المجموع التراكمي.هذا هو العنصر i من الصفيف المساعد لديه مجموع العناصر من 0 إلى i من الصفيف الأصلي.مجموع الصف الفرعي هو مجرد اختلاف عنصرين من المصفوفة المساعدة.هذا سيعطي نتيجة في وقت ثابت, O(1).

هذا يعتمد على ثابت في subsection_sum الوظيفة الواردة في السؤال,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2)

حيث أفترض i1 <= i2.إعادة ترتيب ، لدينا:

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1)

لاحظ أن المبالغ الموجودة على الجانب الأيمن تبدأ من 0.يمكن عرض الصفيف الإضافي على أنه تخزين مؤقت لقيم المبالغ من الصفر, subsection_sum(a, 0, i), ، للجميع i.

Answer 2

إذا كنت تستطيع O(n) تخزين إضافية ، يمكنك إنشاء جدول البحث الذي iالعنصر ال هو مجموع العناصر في المؤشرات 0 من خلال i (شامل) في صفيف الإدخال.في الكود الكاذب:

def computeLookupTable(arr):
    let n = arr.length
    let lookupTable = new Array()

    lookupTable[0] = arr[0]

    for i=1 to n:
        lookupTable[i] = arr[i] + lookupTable[i-1]

    return lookupTable

ثم يمكنك استخدام هذا الجدول لحساب مجموع جميع العناصر في array بين i1 و i2 عن طريق أخذ الفرق

lookupTable[i2] - lookupTable[i1]

الأمر الذي يستغرق وقتا ثابتا.