Вот эта задача пришла ко мне из обзора кода. Я хочу выбрать минимальное значение из набора, основываясь на специальном предикате сравнения. Например:Поиск минимального элемента на основе преобразованного значения
struct Complex { ... };
float calcReduction(Complex elem);
Complex findMinValueWithPredicates(const std::vector<Complex>& values)
{
auto it = std::min_element(values.begin(), values.end(),
[](const Complex& a, const Complex& b) {
return calcReduction(a) < calcReduction(b);
});
if (it == values.end()) throw std::runtime_error("");
return *it;
}
Здесь я нахожу минимальный элемент, основанный на предикате. Этот предикат вычисляет уменьшение обоих значений до float
, а затем сравнивает эти поплавки. Отлично работает, выглядит аккуратно.
У вас проблема? Да, для набора N
элементов calcReduction()
называется 2N
раз, а его достаточно вычислить только N
раз - один раз для каждого элемента.
Одним из способов решения этой проблемы заключается в написании явных вычислений:
Complex findMinValueExplicit(const std::vector<Complex>& values)
{
float minReduction = std::numeric_limits<float>::max();
Complex minValue;
for (Complex value : values)
{
float reduction = calcReduction(value);
if (reduction < minReduction)
{
minReduction = reduction;
minValue = value;
}
}
if (minReduction == std::numeric_limits<float>::max()) throw std::runtime_error("");
return minValue;
}
Он отлично работает, и у нас есть только N
звонков на calcReduction()
. Однако он выглядит слишком многословным, и намерение не является таким ясным, по сравнению с явным вызовом min_element
. Потому что, когда вы звоните min_element
, действительно легко догадаться, что вы найдете минимальный элемент, знаете ли.
Единственная идея, которую я имею сейчас, - создать собственный алгоритм, такой как min_element_with_reduction
, принимая диапазон и функцию уменьшения. Звучит разумно, но мне интересно, есть ли готовые решения.
Любые идеи о том, как решить эту задачу с явным намерением и некоторыми готовыми решениями? Boost приветствуется. C++ 17 и диапазоны интересны.
Чтобы упростить код, я бы начал с проверки 'values.empty()' first. Затем инициализируйте первый элемент и введите цикл над оставшимися элементами. Нет, это, вероятно, не так очевидно, как ваш текущий код, но если вы оптимизируете этот код для максимальной скорости (вы профилировали это, правда?), Некоторые компромиссы приемлемы для IMHO, особенно если результирующий код правильно объясняется в комментариях. –
@UlrichEckhardt Я думаю, что вы правы, единственная разумная вещь - определить мой собственный алгоритм. Другие решения выглядят полностью ... сложными. – Mikhail