Алгоритм сбалансированного распределения

Question

Я работаю над некоторым кодом для слабосвязанного кластера. Для достижения оптимальной производительности во время работы у меня есть кластер переназначить свои данные каждый раз, когда ребенок входит или выходит. В конечном итоге это станет необязательным, но пока оно выполняет балансировку данных по умолчанию. Моя балансировка в основном заключается в том, чтобы убедиться, что каждый ребенок никогда не имеет больше, чем среднее количество файлов на машину, плюс один. Плюс один для остальных, если деление не чисто. А так как остаток будет всегда будет меньше, чем количество детей [кроме 0 случаев, но мы можем исключить это], дети после балансировки будут иметь максимум avg + 1.

Все кажется прекрасным, пока я не понял мой алгоритм O (n!). Спуститесь вниз по списку детей, узнайте о среднем весе, остальном, у которого слишком много, а у кого слишком мало. Для каждого ребенка в слишком большом списке перейдите по списку, отправьте каждому ребенку, у которого слишком мало.

Есть ли лучшее решение для этого? Я чувствую, что должно быть.

Edit: Вот некоторые psuedocode, чтобы показать, как я получен 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. Наверное, мне не хватило кофе этим утром! ;)

В будущем я хотел бы перейти к более гибкому и гибкому методу распределения [веса и hueristics], но на данный момент работает равномерное распределение данных.

Answer 1

@zvrba: Вам даже не нужно сортировать список. При переходе списка во второй раз просто перемещайте все элементы с меньшей средней рабочей нагрузкой до конца списка (вы можете удерживать указатель на последний элемент при первом обходе). Заказ не должен быть совершенным, он просто меняется, когда итераторы должны быть увеличены или уменьшены на вашем последнем шаге.

See previous answer

Последний шаг будет выглядеть примерно так:

На втором этапе держать указатель на первый элемент с менее средней нагрузки в 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 (п)
• делает списки детей слишком много или слишком мало фрагментов данных также O (п)
• перемещения данных пропорционально количеству данных

Как вы пришли к O (N!)?

Вы можете отсортировать список [O (n lg n) в количестве детей], так что на фронте у вас есть дети со слишком большой работой, а в конце дети с слишком маленькой работой. Затем перемещайте список с обоих концов одновременно: один итератор указывает на ребенка с избыточными данными, а другой - на ребенка с отсутствием данных. Передайте данные и переместите либо один итератор вперед, либо другой назад.

Answer 3

Код, который вы опубликовали, имеет сложность O (n^2). Тем не менее, это можно сделать в линейном времени, как заметил малач, где n - количество элементов в списке детей.

Рассмотрите: внутренний цикл имеет n итераций, и выполняется не более n раз. n * n = n^2.

Answer 4

Возможно, вы захотите попробовать совершенно другой подход, такой как последовательное хеширование.

Смотрите здесь для относительно легкого введения в тему: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(Есть более глубокие документы доступны, а также, начиная с Каргер и др)

Я создал рабочую реализацию последовательного хеширования в Erlang, что вы можете проверить, если вы хотите:

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