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

Question

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

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

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

Редактировать:Вот некоторый псевдокод, показывающий, как я получил O(n!):

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

Редактировать:О(п^2).Foreach n, n => n*n => n^2.Кажется, сегодня утром мне не хватило кофе!;)

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

Answer 1

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

См. предыдущий ответ

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

На втором этапе сохраните указатель на первый элемент с рабочей нагрузкой ниже средней в дочернем элементе2 (чтобы избежать необходимости иметь двойной список ссылок).

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

Как вы попали в O(n!)?

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

Answer 3

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

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

(Существуют также более глубокие статьи, начиная с Каргера и др.)

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

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

Answer 4

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

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