在工作线程之间几乎平均分配数据集

Question

我有n个元素和p个线程。我试图在线程之间尽可能平均地划分元素。

例如：

If n = 8 and p = 1, then [8]
If n = 8 and p = 2, then [4, 4]
If n = 8 and p = 3, then [2, 3, 3]
If n = 8 and p = 4, then [2, 2, 2, 2]
If n = 8 and p = 5, then [1, 1, 2, 2, 2]
If n = 8 and p = 6, then [1, 1, 1, 1, 2, 2]
If n = 8 and p = 7, then [1, 1, 1, 1, 1, 1, 2]
If n = 8 and p = 8, then [1, 1, 1, 1, 1, 1, 1, 1]

我制定了一个几乎有效但不完全有效的解决方案。

#include <vector>
#include <stdio.h>
#include <cmath>

int main(int argc, char **argv)
{
    int p = 5;
    const int SIZE = 8;
    int i = 0;
    int num = 0;

    std::vector<int> iter;

    if (p == 1)
        iter.push_back(SIZE);
    else
    {
        if (SIZE % p == 0)
        {
            num = SIZE / p;

            for (i = 0; i < p; ++i)
                iter.push_back(num);
        }
        else
        {
            num = (int)floor((float)SIZE / (float)p);

            for (i = 0; i < p - 1; ++i)
                iter.push_back(num);

            iter.push_back((SIZE - (num * (p - 1))));
        }
    }

    for (unsigned int j = 0; j < iter.size(); ++j)
        printf("[%d] = %d\n", j, (int)iter[j]);

    return 0;
}

我的解决方案产生的结果：

If n = 8 and p = 1, then [8]
If n = 8 and p = 2, then [4, 4]
If n = 8 and p = 3, then [2, 2, 4]
If n = 8 and p = 4, then [2, 2, 2, 2]
If n = 8 and p = 5, then [1, 1, 1, 1, 4]
If n = 8 and p = 6, then [1, 1, 1, 1, 1, 3]
If n = 8 and p = 7, then [1, 1, 1, 1, 1, 1, 2]
If n = 8 and p = 8, then [1, 1, 1, 1, 1, 1, 1, 1]

Answer 1

试着想想这个。如果您的对象少于线程，那么每个线程将获得一个对象。如果您有更多的物体然后是线程（桶），那么请考虑如何将 100 个网球分成 8 个桶。您可以一次取 1 个球并将其放入下一个桶中，一旦您通过了从第一个桶开始的所有桶，这将确保每个桶大小之间的差异最多为 1。

#include <vector>
#include <stdio.h>

int main(int argc, char **argv)
{
    int p = 5;
    const int SIZE = 8;

    int p_size = SIZE > p ? p : SIZE;

    std::vector<int> iter(p_size);

    for (int i = 0; i < SIZE; i++)
    {
        iter[i%p_size] += 1;
    }


    for (unsigned int j = 0; j < iter.size(); ++j)
        printf("[%d] = %d\n", j, (int)iter[j]);

    return 0;
}