我想计算n个工作人员之间任务的平均分配。一项任务包括成对比较;将m个项目中的每个项目与自身和其他项目进行比较。我想避免多余的比较。
例如,对于4个项目和3个工作人员,这将是(4 + 3 + 2 + 1 = 10)个任务,这些任务将分配给3个工作人员。每个工人最多获得ceil(10/3)
任务。它们的分布如下。我生成一个m * m矩阵,并取其下半部分(对角分隔),如下所示:
1 2 3 4
1 x - - -
2 x x - -
3 x x x -
4 x x x x
然后,我遍历矩阵,将任务分配给最大数量的工作人员,这时下一个工作人员将获得任务。
我在Perl中实现了这一点,效果很好:
my $total = 0;
for (my $i = 0; $i < $nitems; $i++) {
for (my $j = 0; $j <= $i; $j++) { $total++ }
}
my $tasksperworker = ceil($total / $nworkers);
my $worker = [ ];
push @$worker, { 'imin' => 1, 'imax' => 1, 'jmin' => 1, 'jmax' => 1 } for (1 .. $nworkers);
my $k = 0;
for (my $i = 0; $i < $nitems; $i++) {
for (my $j = 0; $j <= $i; $j++) {
# start a new worker if this one would be overloaded
if ($tasksforthisworker + 1 > $tasksperworker) {
$k++;
$$worker[$k]{'imin'} = $i;
$$worker[$k]{'imax'} = $i;
$$worker[$k]{'jmin'} = $j;
$$worker[$k]{'jmax'} = $j;
$tasksforthisworker = 1;
}
else {
$$worker[$k]{'imin'} = $i if $$worker[$k]{'imin'} > $i;
$$worker[$k]{'imax'} = $i if $$worker[$k]{'imax'} < $i;
$$worker[$k]{'jmin'} = $j if $$worker[$k]{'jmin'} > $j;
$$worker[$k]{'jmax'} = $j if $$worker[$k]{'jmax'} < $j;
$tasksforthisworker++;
}
}
}
我需要为更大的m计算这个值。Perl版本一直在计算整个周末的输入值n = 8和m =1397704。我意识到这会导致大量任务,但是仍然需要完成这些任务。因此,Perl版本仍在处理中,为了提高效率,我想在C ++中实现该功能。我想我把算法复制到了这里:
// populate the workers array
vector <map <string, int> > workers (nworkers);
for (int i = 0; i < nworkers; i++) {
map <string, int> worker;
worker["imin"] = 1;
worker["imax"] = 1;
worker["jmin"] = 1;
worker["jmax"] = 1;
workers[i] = worker;
}
// calculate total number of tasks and tasks per worker
int total = 0;
for (int i = 0; i < nitems; i++) {
for (int j = 0; j <= i; j++) total++;
}
int tasksperworker = ceil( total / nworkers );
// distribute tasks across workers
int tasksforthisworker = 0;
int i = 0;
int j = 0;
int k = 0;
for (i = 0; i < nitems; i++) {
for (j = 0; j <= i; j++) {
// start a new worker if this one would be overloaded
if (tasksforthisworker + 1 > tasksperworker) {
// this would exceed the number of workers!
assert(k + 1 > workers.size());
k++;
workers.at(k)["imin"] = i;
workers.at(k)["imax"] = i;
workers.at(k)["jmin"] = j;
workers.at(k)["jmax"] = j;
tasksforthisworker = 1;
}
else {
if (workers.at(k)["imin"] > i) workers.at(k)["imin"] = i;
if (workers.at(k)["imax"] < i) workers.at(k)["imax"] = i;
if (workers.at(k)["jmin"] > j) workers.at(k)["jmin"] = j;
if (workers.at(k)["jmax"] < j) workers.at(k)["jmax"] = j;
tasksforthisworker++;
}
}
}
这给了我一个错误,因为在某个时候k
超过workers.size()
了:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check
该assert()
标记发生错误的点。
我的问题是:为什么在C ++版本中而不在Perl版本中会发生这种情况?我在C ++实现中缺少什么(可能是)吗?
还赞赏用于更有效地计算该任务分布的指针。当我考虑这个问题时,这个算法是我脑海中浮现的第一个算法。
有两个问题:
您在整数算术运算的结果上调用ceil,该运算已经是一个下限,因此实际上是在获取ceil(floor(x / y))的结果。将行更改为:
// Ceiling of total divided by nworkers
int tasksperworker = (total + nworkers - 1)/ nworkers;
您的断言中的不平等应为<:
assert(k + 1 < workers.size());
这样就可以了。
有趣(但无关紧要)的事实:通过使用std :: generate_n进行矢量初始化,可以使其更像perl:
vector <map <string, int> > workers (nworkers);
std::generate_n(back_inserter(workers), nworkers, []{
return std::map<string, int>{
{ "imin", 1 },
{ "imax", 1 },
{ "jmin", 1 },
{ "jmax", 1 },
};});
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句