Переупорядочить массив так, чтобы части заданной длины имели почти равную сумму ⇐ C++

[Anonymous]

У меня проблема с балансировкой строк матрицы CSR. Мне нужно разделить матрицу по строкам на несколько графических процессоров, чтобы каждый графический процессор имел почти одинаковое количество ненулевых элементов.
Для ясности: у меня есть std::vector row_sizes - он описывает количество ненулевых элементов в каждой строке, а std::vector размеры - он описывает, сколько строк должно принадлежать графическому процессору, размер массива равен количеству графических процессоров.
Теперь я застрял, как найти такую ​​перестановку. Все, что я нашел, это разделение массива почти на одну и ту же сумму, но ограничений на размеры частей не было. Моя реализация также сейчас не учитывает размеры деталей, поэтому результат лучше, чем вообще без балансировки, но все равно недостаточно хорош.
Может быть, это можно улучшить, но я думаю, что это необходимо полностью переделано.
std::vector balanceRowSizes(const std::vector &sizes, const std::vector &row_sizes)
{
std::size_t row_number = std::accumulate(sizes.begin(), sizes.end(), 0);
std::vector row_permutation(row_number);

std::vector indices(row_number);
std::iota(indices.begin(), indices.end(), 0);
std::sort(indices.begin(), indices.end(), [&](std::size_t a, std::size_t b)
{ return row_sizes[a] > row_sizes; });

std::vector partitions(deviceCount);
std::vector current_sums(deviceCount, 0);
for (const auto &index : indices)
{
std::size_t value = row_sizes[index];
std::size_t min_index = 0;
for (std::size_t i = 0; i < deviceCount; ++i)
{
if (current_sums < current_sums[min_index])
{
min_index = i;
}
}
partitions[min_index].push_back(index);
current_sums[min_index] += value;
}

std::size_t index = 0;
for (std::size_t i = 0; i < deviceCount; ++i)
{
for (const auto &idx : partitions)
{
row_permutation[index++] = idx;
}
}

return row_permutation;
}


Подробнее здесь: https://stackoverflow.com/questions/791 ... -equal-sum