خوارزمية التوزيع المتوازن

Question

أنا أعمل على بعض التعليمات البرمجية لمجموعة مقترنة بشكل غير محكم.لتحقيق الأداء الأمثل أثناء المهام، أطلب من المجموعة إعادة رسم خريطة لبياناتها في كل مرة يدخل فيها الطفل أو يخرج منها.سيصبح هذا في النهاية اختياريًا، ولكنه في الوقت الحالي يقوم بموازنة البيانات بشكل افتراضي.إن التوازن الذي أقوم به هو في الأساس مجرد التأكد من أن كل طفل لن يكون لديه أكثر من متوسط ​​عدد الملفات لكل جهاز، بالإضافة إلى ملف واحد.والزائد هو للباقي إذا لم يكن القسم نظيفا.وبما أن الباقي سوف دائماً يكون أقل من عدد الأطفال [باستثناء 0 حالة، ولكن يمكننا استبعاد ذلك]، فإن الأطفال بعد الموازنة سيكون لديهم متوسط ​​+ 1 على الأكثر.

يبدو كل شيء على ما يرام، حتى أدركت أن الخوارزمية الخاصة بي هي O(n!).انتقل إلى قائمة الأطفال، واكتشف المتوسط، والباقي، ومن لديه عدد كبير جدًا ومن لديه عدد قليل جدًا.بالنسبة لكل طفل في قائمة العدد الكبير جدًا، راجع القائمة وأرسلها إلى كل طفل لديه عدد قليل جدًا.

هل هناك حل أفضل لهذا؟أشعر أنه يجب أن يكون هناك.

يحرر:إليك بعض الكود الكاذب لإظهار كيفية اشتقاق O(n!):

foreach ( child in children ) {
    if ( child.dataLoad > avg + 1 ) {
        foreach ( child2 in children ) {
            if ( child != child2 && child2.dataLoad < avg ) {
                sendLoad(child, child2)
            }
        }
    }
}

يحرر:يا (ن ^ 2).Foreach n، n => n*n => n^2.أعتقد أنني لم أتناول ما يكفي من القهوة هذا الصباح!;)

في المستقبل، أود الانتقال إلى طريقة توزيع أكثر مرونة ومرونة [الأوزان والاستدلالات]، ولكن في الوقت الحالي، يعمل التوزيع الموحد للبيانات.

Answer 1

@زفربا:ليس لديك حتى لفرز القائمة.عند اجتياز القائمة في المرة الثانية، ما عليك سوى نقل جميع العناصر ذات متوسط ​​عبء العمل الأقل إلى نهاية القائمة (يمكنك الاحتفاظ بمؤشر إلى العنصر الأخير عند اجتيازك الأول).ليس من الضروري أن يكون الترتيب مثاليًا، بل يتغير فقط عندما يتعين زيادة أو تقليل عدد التكرارات في خطوتك الأخيرة.

انظر الإجابة السابقة

ستبدو الخطوة الأخيرة كما يلي:

في الخطوة الثانية، احتفظ بمؤشر إلى العنصر الأول مع عبء عمل أقل من المتوسط ​​في Child2 (لتجنب ضرورة وجود قائمة ارتباطات مزدوجة).

for each child in list {
  if child2 == nil then assert("Error in logic");
  while child.workload > avg + 1 {
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1)))
    if child2.workload == avg + 1 then child2 = child2.next;
  }
}

Answer 2

أعتقد أن تحليلك غير صحيح:

• من خلال القائمة لمعرفة المتوسط ​​هو O(n)
• يعد إنشاء قوائم بالأطفال الذين لديهم عدد كبير جدًا أو قليل جدًا من مجموعات البيانات أيضًا O(n)
• نقل البيانات يتناسب مع كمية البيانات

كيف وصلت إلى O(n!)؟

يمكنك فرز القائمة [O(n lg n) في عدد الأطفال]، بحيث يكون لديك في المقدمة أطفال يقومون بالكثير من العمل، وفي النهاية أطفال لديهم القليل من العمل.ثم قم باجتياز القائمة من كلا الطرفين في وقت واحد:يشير أحد المكررين إلى طفل لديه بيانات زائدة، والآخر إلى طفل يعاني من نقص البيانات.قم بنقل البيانات، وحرك أحد المكررين للأمام أو الآخر للخلف.

Answer 3

قد ترغب في تجربة أسلوب مختلف تمامًا، مثل التجزئة المتسقة.

انظر هنا للحصول على مقدمة سهلة نسبيًا للموضوع:http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(توجد أيضًا أبحاث أعمق، بدءًا من كارجر وآخرين)

لقد قمت بإنشاء تطبيق عملي للتجزئة المتسقة في Erlang والتي يمكنك فحصها إذا كنت ترغب في ذلك:

http://distributerl.googlecode.com/svn/trunk/chash.erl

Answer 4

الكود الذي قمت بنشره له تعقيد O(n^2).ومع ذلك، من الممكن القيام بذلك في زمن خطي كما لاحظ مالاخ، حيث n هو عدد العناصر في القائمة الفرعية.

يعتبر:تحتوي الحلقة الداخلية على عدد n من التكرارات، ويتم تنفيذها في الغالب ن مرات.ن*ن = ن^2.