У нас есть N серверов. На каждом лежит Bi записей (i=1..N). На них нужно выложить новых U записей. Надо распределить нагрузку равномерно.
Например: есть 4 сервера, на них — 20, 18, 12 и 0 записей (всего 50). Нужно распределить 10 записей. Ответ — 20, 18, 12 и 10.
А в общем случае?

Здравствуйте, Alexan, Вы писали:

A>У нас есть N серверов. На каждом лежит Bi записей (i=1..N). На них нужно выложить новых U записей. Надо распределить нагрузку равномерно.
A>Например: есть 4 сервера, на них — 20, 18, 12 и 0 записей (всего 50). Нужно распределить 10 записей. Ответ — 20, 18, 12 и 10.
A>А в общем случае?

Хм. Вообще говоря, если не критично местоположение каждой записи в отдельности и можно последовательно добавлять по одной записи, тогда всё просто.

Пусть Bi -- количество записей на i-том сервере. B -- общее колчисетво записей. Тогда фактор загруженности сервера вычисляется как Bi/B.

Находим сервер с наименьшим фактором и добавляем туда запись. пересчитываем факторы загруженнсоти и повторяем добавление записи.

Таким образом, пока не добавим все записи.

Здравствуйте, PSP, Вы писали:

PSP>Хм. Вообще говоря, если не критично местоположение каждой записи в отдельности и можно последовательно добавлять по одной записи, тогда всё просто.

PSP>Пусть Bi -- количество записей на i-том сервере. B -- общее колчисетво записей. Тогда фактор загруженности сервера вычисляется как Bi/B.

PSP>Находим сервер с наименьшим фактором и добавляем туда запись. пересчитываем факторы загруженнсоти и повторяем добавление записи.

PSP>Таким образом, пока не добавим все записи.

Добавлять записи по одной не есть хорошо. Решение задачи предполагает, что мы получим число выгружаемых записей для каждого сервера сразу. Число должно быть >=0.

Здравствуйте, Alexan, Вы писали:


A>Добавлять записи по одной не есть хорошо. Решение задачи предполагает, что мы получим число выгружаемых записей для каждого сервера сразу. Число должно быть >=0.

Считаем среднее арифметическое количество записей на сервер. Для каждого из серверов, где количесиво записей меньше среднего, назначаем количество записей, равное разности среднего числа записей и реального числа. Начинаем с того сервера, у которого количество храняшихся записей минимально. Если после этого остались нераспределенные записи, то можно повторить процедуру. Если получилась ситуация, когда на всез серверах поровну записей, и еще остались нераспределенные — то на все поровну.
Например твой пример:
20, 18, 12 и 0 , добавить 10.
Сред. ар. = 12.5 -> 13. макс. разность дает сервер 4.
13 — 0 == 13, значит на 4-й сервер надо 13 записей. Но поскольку из у нас всего 10, то передаем ему все 10.

добавить еще 10.
Сред. ар. = 15.
для 4-го сервера 5 записей
для 3-го сервера 3 записи

Остальсь 2 записи.
Новое Сред. ар. = 17.
для 4-го (или для 3-го) сервера 2 записи.

Здравствуйте, Alexan, Вы писали:

PSP>>Пусть Bi -- количество записей на i-том сервере. B -- общее колчисетво записей. Тогда фактор загруженности сервера вычисляется как Bi/B.

PSP>>Находим сервер с наименьшим фактором и добавляем туда запись. пересчитываем факторы загруженнсоти и повторяем добавление записи.

PSP>>Таким образом, пока не добавим все записи.

A>Добавлять записи по одной не есть хорошо. Решение задачи предполагает, что мы получим число выгружаемых записей для каждого сервера сразу. Число должно быть >=0.

Да господи. Вариантов куча. Можешь добавлять не по одному, а скажем сразу по 10. Работать будет быстро по любому.

Собственно, не понимаю смысл слова сразу в данном контексте.

Здравствуйте, Bell, Вы писали:

B>Например твой пример:
B>20, 18, 12 и 0 , добавить 10.
B>Сред. ар. = 12.5 -> 13. макс. разность дает сервер 4.
B>13 — 0 == 13, значит на 4-й сервер надо 13 записей. Но поскольку из у нас всего 10, то передаем ему все 10.

Есть более интересный пример, когда 3 сервера, а на них записей — 0, 1 и 1000. Надо загрузить 300 записей. По предложенному выше алгоритму получится, что все 300 записей перейдут на первый сервер, а хочется по 150...

Здравствуйте, Alexan, Вы писали:

A>У нас есть N серверов. На каждом лежит Bi записей (i=1..N). На них нужно выложить новых U записей. Надо распределить нагрузку равномерно.
A>Например: есть 4 сервера, на них — 20, 18, 12 и 0 записей (всего 50). Нужно распределить 10 записей. Ответ — 20, 18, 12 и 10.
A>А в общем случае?

Проверьте следующий алгоритм (а то коньячку принял не по децки, не поручусь до конца)

Не ограничивая общности положим что Вi упорялоченны по возрастанию i. Тогда
найдем такое наименьшее К = 1..N-1, что
( Sum( B[i], i = 1..K ) + U ) / B[i+1] <= K;
Если нет такого К, то К = N;

Далее для каждого сервера i = 1..K кол-во новых записей U[i] будет равна
U[i] = ( Sum( B[i], i = 1..K ) + U ) / K — B[i];

Если U[i] получится не целое, добавить единицу к U[K] и отбросить дробные части для U[1..K-1]. Так мы должны сохранить упорядоченность B[i].

Здравствуйте, Alexan, Вы писали:

PSP>>Пусть Bi -- количество записей на i-том сервере. B -- общее колчисетво записей. Тогда фактор загруженности сервера вычисляется как Bi/B.

PSP>>Находим сервер с наименьшим фактором и добавляем туда запись. пересчитываем факторы загруженнсоти и повторяем добавление записи.

PSP>>Таким образом, пока не добавим все записи.

A>Добавлять записи по одной не есть хорошо. Решение задачи предполагает, что мы получим число выгружаемых записей для каждого сервера сразу. Число должно быть >=0.

Никто не предлагает физически пересылать по одной записи. Заводим сначала массив М нулей размерностью в количество серверов, выполняем этот алгоритм n раз, каждый раз добавляя единичку в тот элемент, куда он укажет и корректируем соответственно загрузку, получаем массив с количеством добавляемых записей к каждому серверу.

Можно, конечно, оптимизировать: если на сервере с минимальной нагрузкой X записей, а у следующего Y записей, то первые Y-X записей пойдут на первый. Точнее, даже Y-X+1. Более обще, если минимальная загрузка (X записей) совпадает у К серверов, а у следующего Y записей, то первые (Y-X+1)*K записей пойдут на эти K серверов (по (Y-X+1) на каждый).

Здравствуйте, Gaperton, Вы писали:

G>Не ограничивая общности положим что Вi упорялоченны по возрастанию i. Тогда
G>найдем такое наименьшее К = 1..N-1, что
G>( Sum( B[i], i = 1..K ) + U ) / B[i+1] <= K;

Нагляднее и проще это же условие выглядит так:
Sum(B[K]-B[i])<=U (i=1..K)
Особенно хорошо это представляется графически.

G>Если нет такого К, то К = N;

С учетом вышесказанного, это ненужно.

G>Далее для каждого сервера i = 1..K кол-во новых записей U[i] будет равна
G>U[i] = ( Sum( B[i], i = 1..K ) + U ) / K — B[i];

Ага.

Все же принципиально нового решения получить не удается. Самое простое из известных мне решений озвучено Gaperton(ом).

Здравствуйте, Alexan, Вы писали:

A>Есть более интересный пример, когда 3 сервера, а на них записей — 0, 1 и 1000. Надо загрузить 300 записей. По предложенному выше алгоритму получится, что все 300 записей перейдут на первый сервер, а хочется по 150...

Кроме итерационного, ничего в голову не пришло:
Допустим, имеется N серверов. k = N-1
Необходимо добавить z записей.
1) Сортируем массив по возрастанию
2) Далее по тексту

...
var i,j : Integer;
    razn,prom : Integer;
...
i := 1;
while (z > 0) and (i <= k) do begin 
    razn := (serv[i] - serv[0]) * i;
    for j := 0 to i-1 do begin
        // перераспределение записей
        prom := razn div (i-j)
        inc(serv[j],prom); //или положить на j-й сервер prom записей
        dec(razn,prom);
        dec(z,prom);
    end;
    inc(i);
end;

3)После этого если количество оставшихся записей все еще больше 0, их можно разделить между всеми серверами поровну

P.S.Погрешность в данном методе (как, собственно, и во многих других) есть и равна она k-1.

P.P.S. Сразу извиняюсь, если что-то не работает, не проверял, надеюсь, сам принцип понятен

У нас есть N серверов. На каждом лежит Bi записей (i=1..N). На них нужно выложить новых U записей. Надо распределить нагрузку равномерно.
Например: есть 4 сервера, на них — 20, 18, 12 и 0 записей (всего 50). Нужно распределить 10 записей. Ответ — 20, 18, 12 и 10.
А в общем случае?

Задача усложняется. Сервера имеют ограничение на число выгруженных записей: V1... VN, естественно, что Bi<=Vi.

A>У нас есть N серверов. На каждом лежит Bi записей (i=1..N). На них нужно выложить новых U записей. Надо распределить нагрузку равномерно.
A>Например: есть 4 сервера, на них — 20, 18, 12 и 0 записей (всего 50). Нужно распределить 10 записей. Ответ — 20, 18, 12 и 10.
A>А в общем случае?

A>Задача усложняется. Сервера имеют ограничение на число выгруженных записей: V1... VN, естественно, что Bi<=Vi.

Ну что, никто не может предложить решения?