Как распределить вектор из n элементов на p процессоров

Question

Предположим, у меня есть вектор из n элементов, и я хочу распределить его по p-процессам, где n не обязательно кратно p.Каждый процесс имеет ранг от 0 до p-1.Как определить, сколько элементов будет в каждом процессе, чтобы данные распределялись как можно более равномерно?

Например, если n = 14 и p = 4, я хочу распределение, подобное [3, 3, 4, 4] или [3, 4, 3, 4], но не [3, 3, 3, 5] и [4, 4, 4, 2].

Я хочу функцию f (n,p, r), который возвращает мне количество элементов для процесса с рангом r.

Answer 1

ли

(n + r) / p

работаешь на тебя?

Answer 2

Это, кажется, частный случай проблемы Bin Packing . Есть несколько очень хороших алгоритмов аппроксимации, но в теории это NP-сложный.

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

Шаг 1: сортировка элементов по приоритету.
Шаг 2: возьмите элемент с наивысшим приоритетом и вставьте его в процесс с наименьшей нагрузкой.
Шаг 3: Если у вас есть больше элементов, перейдите к шагу 1. В противном случае возврат.