Прервать подзадачу из 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); 
    });

Оператор return внутри parallel_for ощущается неэффективным, поскольку он все еще выполняется для каждого элемента, и в этом случае вполне возможно, что параллель_for может закончиться итерацией по нескольким частям вектора, которые слишком высоки.

Как я могу воспользоваться тем, что вектор уже отсортирован по стоимости?

Я рассмотрел использование токена отмены, но этот подход кажется неправильным, так как он может привести к отмене всех подзадач с функцией parallel_for, что означает, что я могу получить неправильное максимальное значение.

Есть ли что-то вроде токена отмены, который может отменить эту конкретную подзадачу therallel_for, или в этом случае есть лучший инструмент, чем parallel_for?

Answer 1

Если вектор отсортирован по стоимости, вы можете перебирать только те элементы, стоимость которых ниже предела стоимости.

Если стоимость х. найти первый элемент итератор, который равен или больше, чем х. Вы можете использовать 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); 
    });