Algoritmo de distribución equilibrada

Question

Estoy trabajando en un código para un clúster acoplado libremente. Para lograr un rendimiento óptimo durante los trabajos, hago que el clúster reasigne sus datos cada vez que un niño ingresa o sale. Esto eventualmente se hará opcional, pero por ahora realiza su balance de datos por defecto. 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 dado que el resto siempre será menor que el número de niños [excepto 0 casos, pero podemos excluirlo], los niños después de un balance tendrán como máximo avg + 1.

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

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

Editar: Aquí hay algunos psuedocódigo para mostrar cómo obtuve O (n!):

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

Edición: O (n ^ 2). Para cada n, n = > n * n = > n ^ 2. ¡Supongo que no tomé suficiente café esta mañana! ;)

En el futuro me gustaría pasar a un método de distribución más flexible y resistente [pesos y huerística], 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, simplemente 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, solo cambia cuando los iteradores deben aumentarse o disminuirse en su último paso.

Ver respuesta anterior

El último paso se vería algo así como:

En el segundo paso, mantenga un puntero al primer elemento con una carga de trabajo inferior al 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:

• recorriendo la lista para averiguar el promedio es O (n)
• hacer listas de niños con demasiados o muy pocos fragmentos de datos también es O (n)
• mover datos es proporcional a la cantidad de datos

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

Puede ordenar la lista [O (n lg n) en el número de niños], de modo que en el frente 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, el otro a un niño con falta de datos. Transfiera datos y mueva un iterador hacia adelante o el otro hacia atrás.

Answer 3

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

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

(También hay documentos más profundos disponibles, comenzando con Karger et al)

He creado una implementación funcional de hashing consistente en Erlang que puede examinar si lo desea:

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

Answer 4

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

Considere: el bucle interno tiene n iteraciones y se ejecuta como máximo n veces. n * n = n ^ 2.