Algoritmo de distribución equilibrada

Question

Estoy trabajando en algún código para un clúster débilmente acoplado. Para lograr un rendimiento óptimo durante los trabajos, el clúster reasigna sus datos cada vez que un niño ingresa o sale. Eventualmente, esto se convertirá en opcional, pero por ahora realiza su balance de datos de manera predeterminada. Mi equilibrio es básicamente asegurarme de que cada niño nunca tenga más que el número promedio de archivos por máquina, más uno. El más uno es para el resto si la división no está limpia. Y puesto que el resto se siempre será menor que el número de niños [0, excepto el caso, pero podemos excluir esa], los niños después de un equilibrado tendrán en la mayoría de avg + 1.

Todo parece estar bien, hasta que me di cuenta mi algoritmo es O (n!). Vaya a la lista de niños, descubra el promedio, el resto, que tiene demasiados y que tiene muy pocos. Para cada niño en la lista de demasiados, revise la lista y envíela a cada niño que tenga muy pocos.

¿Hay una mejor solución para esto? Siento que debe haberlo.

Editar: Aquí hay alguna psuedocode para mostrar cómo I derivado O (n!):

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

Editar: O (n^2). Foreach n, n => n * n => n^2. ¡Supongo que no tuve suficiente café esta mañana! ;)

En el futuro, me gustaría pasar a un método de distribución más flexible y resistente [ponderaciones y características], pero por ahora, una distribución uniforme de datos funciona.

Answer 1

@zvrba: Ni siquiera tiene que ordenar la lista. Al recorrer la lista por segunda vez, mueva todos los elementos con menos carga de trabajo promedio al final de la lista (puede mantener un puntero al último elemento en su primer recorrido). El orden no tiene que ser perfecto, simplemente cambia cuando los iteradores deben aumentarse o disminuirse en su último paso.

See previous answer

El último paso sería algo como:

En el segundo paso mantener un puntero al primer elemento con menos carga de trabajo promedio en child2 (para evitar la necesidad de tener una lista de enlaces dobles)

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

creo que su análisis es incorrecto:

• caminando a través de la lista para averiguar el promedio es O (n)
• hacer listas de los niños con demasiados o demasiado pocos fragmentos de datos también es O (n)
• datos en movimiento es proporcional a la cantidad de datos

¿Cómo llegó a O (n!)?

Puede ordenar la lista [O (n lg n) en el número de niños], de modo que en la parte frontal tenga niños con demasiado trabajo, y al final niños con muy poco trabajo. Luego recorra la lista desde ambos extremos simultáneamente: un iterador apunta a un niño con datos en exceso y el otro a un niño con falta de datos. Transfiera datos y mueva un iterador hacia adelante o hacia atrás.

Answer 3

El código que ha publicado tiene complejidad O (n^2). Aún así, es posible hacerlo en tiempo lineal como ha observado malach, donde n es el número de elementos en la lista de niños.

Considere: el ciclo interno tiene n iteraciones, y se ejecuta a lo sumo n veces. n * n = n^2.

Answer 4

Es posible que desee probar un enfoque completamente diferente, como el hash consistente.

Ver aquí para una relativamente fácil introducción al tema: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(Hay papeles más profundos disponibles, así, a partir de Karger et al)

He creado una aplicación de trabajo de hash consistente en Erlang que puede examinar si lo desea:

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