Algoritmo di distribuzione bilanciato

Question

Sto lavorando su un codice per un cluster liberamente accoppiato. Per ottenere prestazioni ottimali durante i lavori, ho il cluster rimappare i suoi dati ogni volta che un bambino entra o esce. Questo alla fine sarà reso opzionale, ma per ora esegue il bilanciamento dei dati per impostazione predefinita. Il mio bilanciamento consiste fondamentalmente nel fare in modo che ogni bambino non abbia mai più del numero medio di file per macchina, più uno. Il più uno è per il resto se la divisione non è pulita. E dal momento che il resto sarà sempre essere inferiore al numero di bambini [ad eccezione di 0 caso, ma possiamo escludere che], bambini dopo un bilanciamento avranno al massimo avg + 1.

Tutto sembra in ordine, fino a quando mi sono reso conto il mio algoritmo è O (n!). Scendi nell'elenco dei bambini, scopri la media, il resto, chi ne ha troppi e chi ne ha troppo pochi. Per ogni bambino nella troppa lista, scorrere l'elenco, inviare ad ogni bambino che ne ha troppo pochi.

Esiste una soluzione migliore? Sento che deve esserci.

Edit: Ecco alcune psuedocodarlo di mostrare come ho derivato O (n!):

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. Immagino di non aver bevuto abbastanza caffè stamattina! ;)

In futuro mi piacerebbe passare a un metodo di distribuzione più flessibile e resiliente [pesi e hueristics], ma per ora funziona una distribuzione uniforme dei dati.

Answer 1

@zvrba: Non è nemmeno necessario ordinare l'elenco. Quando attraversi la lista la seconda volta sposta semplicemente tutti gli elementi con meno carico di lavoro medio alla fine dell'elenco (puoi mantenere un puntatore all'ultimo oggetto al tuo primo attraversamento). L'ordine non deve essere perfetto, cambia solo quando gli iteratori devono essere aumentati o diminuiti nell'ultimo passaggio.

See previous answer

L'ultimo passo sarebbe simile:

Nella seconda fase mantenere un puntatore al primo elemento con meno carico di lavoro medio in child2 (per evitare la necessità di avere una lista doppia maglia).

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

penso che la tua analisi non è corretta:

• a ripercorrere la lista per scoprire la media è O (n)
• fare liste di bambini con troppi o troppo pochi blocchi di dati è anche O (n)
• spostamento dei dati è proporzionale alla quantità di dati

Come sei arrivato a O (n!)?

È possibile ordinare l'elenco [O (n lg n) nel numero di bambini], in modo che sul lato anteriore ci siano bambini con troppo lavoro e alla fine i bambini con poco lavoro. Quindi attraversa contemporaneamente la lista da entrambe le estremità: un iteratore punta a un bambino con dati in eccesso, l'altro a un bambino con mancanza di dati. Trasferisci dati e sposta un iteratore in avanti o l'altro all'indietro.

Answer 3

Il codice che hai postato ha complessità O (n^2). Tuttavia, è possibile farlo in tempo lineare come osservato da malach, dove n è il numero di elementi nell'elenco dei bambini.

Considerare: il ciclo interno ha n iterazioni ed è eseguito al massimo n volte. n * n = n^2.

Answer 4

Si consiglia di provare un approccio completamente diverso, come l'hashing coerente.

Vedi qui per un tempo relativamente facile introduzione al tema: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(ci sono carte più profondi disponibili pure, a partire da Karger et al)

ho creato un'implementazione di lavoro di hashing coerente in Erlang che è possibile esaminare se lo si desidera:

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