Ausgewogene Verteilung Algorithm

Question

Ich arbeite an einigen Code für eine lose gekoppelte Cluster. Für eine optimale Leistung bei Jobs, habe ich die Cluster ihre Daten jedes Mal neu zuordnen ein Kind betritt oder verlässt. Dies wird schließlich optional gemacht werden, aber jetzt führt er seine Daten standardmäßig ausgleicht. Mein Ausgleich ist im Grunde nur dafür sorgen, dass jedes Kind nie mehr als die durchschnittliche Anzahl von Dateien pro Maschine hat, plus eines. Das Plus ist für den Rest, wenn die Division nicht sauber ist. Und da der Rest wird immer kleiner sein als die Zahl der Kinder [außer 0 Fall, aber das können wir ausschließen], Kinder nach einem Ausgleich werden höchstens avg haben + 1.

Alles scheint in Ordnung, bis ich meine Algorithmus O realisiert (n!). Gehen Sie die Liste der Kinder unten, herauszufinden, die avg, Rest, der zu viele hat und wer zu wenig hat. Für jedes Kind in der zu viele Liste, gehen Sie durch die Liste, für jedes Kind schicken, die zu wenig hat.

Gibt es eine bessere Lösung für dieses? Ich fühle mich muss es sein.

Edit: (! N) Hier ist etwas psuedocode zu zeigen, wie i abgeleitet O:

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

Edit: O (n ^ 2). Foreach n, n => n * n => n ^ 2. Ich glaube, ich nicht an diesem Morgen hatte genug Kaffee! ;)

In der Zukunft möchte ich zu einer flexibleren und elastischen Verteilungsverfahren [Gewichte und hueristics] bewegen, aber für jetzt, eine gleichmäßige Verteilung von Daten funktioniert.

Answer 1

@zvrba: Sie haben nicht einmal die Liste zu sortieren. Wenn die Liste durchquert das zweite Mal bewegen nur alle Einzelteile mit weniger der durchschnittlichen Arbeitsbelastung bis zum Ende der Liste (Sie bei Ihrem ersten Traversal einen Zeiger auf das letzte Element halten). Die Reihenfolge ist nicht perfekt sein muss, es ändert sich nur, wenn die Iteratoren ergänzt oder in Ihrem letzten Schritt verringert werden müssen.

vorherige Antwort

Der letzte Schritt wäre in etwa so aussehen:

Im zweiten Schritt halten einen Zeiger auf das erste Element mit weniger als der Durchschnitt Arbeitsbelastung in child2 (die Notwendigkeit, zu verhindern, dass eine doppelte Linkliste haben).

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

Ich denke, dass Ihre Analyse ist falsch:

• Gehen Sie durch die Liste der Durchschnitt, um herauszufinden, ist O (n)
• Erstellen von Listen von Kindern mit zu vielen oder zu wenigen Datenblöcken ist auch O (n)
• Verschieben von Daten ist proportional zur Menge der Daten

Wie kam es zu O (n!)?

Sie können die Liste sortieren [O (n lg n) in der Anzahl der Kinder], so dass auf der Vorderseite Sie Kinder mit zu viel Arbeit haben, und am Ende Kinder mit zu wenig Arbeit. Dann durchläuft die Liste von beiden Enden gleichzeitig: ein Iterator zeigt auf ein Kind mit einem Überschuss an Daten, die andere, um ein Kind mit fehlenden Daten. Übertragen von Daten, und bewegen Sie entweder ein Iterator vorwärts oder das andere nach hinten.

Answer 3

Sie können einen völlig anderen Ansatz, wie konsistente Hashing versuchen.

Sehen Sie hier für eine relativ einfache Einführung in das Thema: http://www8.org/w8-papers/2a-webserver/ Caching / paper2.html

(Es gibt tiefere Papiere als auch ausgehend von Karger et al)

Ich habe eine funktionierende Implementierung von konsistentem Hashing in Erlang erstellt, die Sie untersuchen können, wenn Sie wollen:

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

Answer 4

Der Code, den Sie geschrieben haben hat Komplexität O (n ^ 2). Dennoch ist es möglich, sie in linearer Zeit zu tun, wie malach beobachtet hat, wobei n die Anzahl der Elemente in der Kinder-Liste ist.

Bedenken Sie: die innere Schleife n Iterationen hat, und es wird ausgeführt höchstens n-mal. n * n = n ^ 2.