2

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

单线程 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 更好的工具？

4

1 回答 1

1

如果向量按成本排序，那么您可以仅迭代成本低于成本限制的项目。

如果成本是 x。找到第一个等于或大于 x 的项迭代器。您可以使用 std::lower_bound。然后你使用你的 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); 
    });
于 2015-08-25T06:34:35.673 回答