中断parallel_for_each的子任务

Question

我有一个大的项目向量，根据它们的一个字段排序，例如成本属性，我想对这些项目中的每一个做一点处理，以找到不同属性的最大值…这里的约束是，如果某项商品的成本超过某个任意价格，我们就不能使用该商品计算其最大值。

单线程for循环是这样的:

auto maxValue = -MAX_FLT;
for(const auto& foo: foos) {
    // Break if the cost is too high.
    if(foo.cost() > 46290) { 
        break;
    }
    maxValue = max(maxValue , foo.value()); 
}

我已经能够某种程度上将其转换为parallel_for_each。(免责声明:我是PPL的新手。)

combinable<float> localMaxValue([]{ return -MAX_FLT; });
parallel_for_each(begin(foos), end(foos), [&](const auto& foo) {
    // Attempt to early out if the cost is too high.
    if(foo.getCost() > 46290) {
        return; 
    }
    localMaxValue.local() = max(localMaxValue.local(), foo.getValue());
}
auto maxValue = localMaxValue.combine(
    [](const auto& first, const auto& second) { 
        return max<float>(first, second); 
    });

parallel_for内部的return语句感觉效率很低，因为它仍然在每个项上执行，在这种情况下，parallel_for很可能最终迭代向量的多个部分，而这些部分的开销太高。

如何利用向量已经按代价排序的事实呢?

我考虑使用取消令牌，但这种方法似乎不正确，因为它会导致parallel_for的所有子任务被取消，这意味着我可能会得到错误的最大值。

是否有类似于取消令牌的东西可以取消parallel_for的特定子任务，或者在这种情况下是否有比parallel_for更好的工具?

Answer 1

如果vector按成本排序，则只能遍历成本低于成本限制的项。

如果成本是x。找到第一个等于或大于x的元素迭代器。您可以使用std::lower_bound。然后从vector的开头到找到的迭代器使用parallel_for_each。

combinable<float> localMaxValue([]{ return -MAX_FLT; });
//I'm assuming foos is std::vector.
int cost_limit = 46290;
auto it_end = std::lower_bound(foos.begin(), foos.end(), cost_limit, [](const auto& foo, int cost_limit)
{
    return foo.getCost() < cost_limit;
});
parallel_for_each(foos.begin(), foos.end(), [&](const auto& foo) {    
    localMaxValue.local() = max(localMaxValue.local(), foo.getValue());
}
auto maxValue = localMaxValue.combine(
    [](const auto& first, const auto& second) { 
        return max<float>(first, second); 
    });