2

フィールドの 1 つ (コスト属性など) に基づいて並べ替えられたアイテムの大きなベクトルがあり、これらの各アイテムに対して少し処理を行って、異なる属性の最大値を見つけたいと考えています... 制約ここで、アイテムのコストが任意の価格を超える場合、そのアイテムを使用して最大値を計算することはできません。

シングル スレッドの 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 に答える