根据转换后的值查找最小元素 [英] Finding minimum element based on a transformed value
问题描述
这是代码审查给我带来的任务。我想根据一种特殊的比较谓词从集合中选择一个最小值。像这样：
结构体{...};
float calcReduction（复杂元素）;
复杂的findMinValueWithPredicates（const std :: vector&& 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 次就足够了-每个元素一次。
一个解决此问题的方法是编写显式计算：
复杂findMinValueExplicit（const std :: vector< Complex>&值）
{
float minReduction = std :: numeric_limits< float> :: max（）;
Complex minValue;
的（复数值：值）
{
浮点数减少= calcReduction（值）;
，如果（减少量＜minReduction）
{
minReduction =减少量；
minValue =值；
}
}
if（minReduction == std :: numeric_limits< float> :: max（））throw std :: runtime_error（）;
返回minValue;
}
工作正常，我们只有 N 调用 calcReduction（）。但是，与显式调用 min_element 相比，它看起来太冗长，意图也不是很清楚。因为当您调用 min_element 时，很容易猜到您将要找到一个最小元素。
我目前唯一的想法是创建自己的算法，例如 min_element_with_reduction ，接受范围和缩小功能。听起来很合理，但我想知道是否有任何现成的解决方案。欢迎使用Boost。 C ++ 17和范围很有趣。
您可以使用 boost :: range 库
auto reductionLambda = []（const Complex& a）{return calcReduction（a）; };
auto it = boost :: range :: min_element（values | boost :: adaptors :: transformed（
std :: ref（reductionLambda））;
范围本身也应该成为C ++ 17的标准C ++。
编辑
正如我们在评论中指出的那样，这也会使转换两次。
所以这里有些有趣：
#include< boost / iterator / iterator_adaptor.hpp>
#include< ; boost / assign.hpp>
#include< algorithm>
#include< iostream>
#include< vector>
#include< functional>
模板< class Iterator，class UnaryFunction>
class memoizing_transform_iterator
：public boost :: iterator_adaptor<
memoizing_transform_iterator< Iterator，UnaryFunction> //派生
，迭代器//基本
，std :: decay_t< decltype（std :: declval< UnaryFunction>（）（std :: declval< typename Iterator :: value_type>（）））> //值
，boost :: forward_traversal_tag // CategoryOrTraversal
>
{
public：
memoizing_transform_iterator（）{}
显式memoizing_transform_iterator（迭代器iter，UnaryFunction f）
：memoizing_transform_iterator :: iterator_adaptor_（iter）， fun（f）{}
静态整数总计；
私人：
朋友课程提升：: iterator_core_access;
voidcrement（）{++ this-> base_reference（）;记忆=假; }
使用MemoType = std :: decay_t< decltype（std :: declval< UnaryFunction>（）（std :: declval< typename Iterator :: value_type>（）））> ;;
MemoType& dereference（）const
{
if（！memoized）{
++ total;
memoized = true;
memo = fun（* this-> base（））;
}
退货通知单；
}
UnaryFunction乐趣；
可变的布尔值记忆=假;
可变的MemoType备忘录；
};
模板<类迭代器，类UnaryFunction>
auto make_memoizing_transform_iterator（Iterator i，UnaryFunction& f）
{
return memoizing_transform_iterator< Iterator，UnaryFunction>（i，f）;
}
模板<类别I，类别U>
int memoizing_transform_iterator< I，U> :: total = 0;
//这是从LIBSTDC ++复制的
template< typename _ForwardIterator>
_ForwardIterator
min_el（_ForwardIterator __first，_ForwardIterator __last）
{
if（__first == __last）
return __first;
_ForwardIterator __result = __first;
而（++ __ first！= __last）
if（* __ first< * __ result）
__result = __first;
返回__result;
}
int main（int argc，const char * argv []）
{
使用命名空间boost :: assign;
std :: vector< int>输入
输入+ = 2,3,4,1,5,6,7,8,9,10;
auto transformLambda = []（const int& a）{return a * 2; };
auto begin_it = make_memoizing_transform_iterator（input.begin（），std :: ref（transformLambda））;
auto end_it = make_memoizing_transform_iterator（input.end（），std :: ref（transformLambda））;
std :: cout<< * min_el（begin_it，end_it）.base（）<< \n;
std :: cout<< begin_it.total;
返回0;
}
基本上，我实现了一个迭代器，该迭代器可记忆调用转换函子的结果。不过，奇怪的是，至少在联机编译器中，在比较迭代器的解引用值之前先将其复制（这样就破坏了记忆的目的）。但是，当我简单地从libstdc ++复制实现时，它可以按预期工作。也许您可以在真实的机器上尝试一下？实时示例为此处。
小编辑：
我在VS2015上进行了测试，它与 std :: min_element 一样工作。
Here is the task came to me from a code review. I want to select a minimum value from a set, based on a special kind of compare predicate. Like this:
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;
}
Here I find the minimum element based on a predicate. This predicate computes a reduction of both values to float and then compares those floats. Works fine, looks neat.
Can you see the problem? Yes, for a set of N elements calcReduction() is called 2N times, while it is enough to compute it only N times - once for each element.
One way to solve this problem is to write explicit computations:
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;
}
It works fine and we only have N calls to calcReduction(). However, it looks too verbose and the intent is not such clear, as compared to explicit call of min_element. Because when you call min_element it is really easy to guess you are going to find a minimum element, you know.
The only idea I have for now is to create my own algorithm like min_element_with_reduction, accepting a range and a reduction function. Sounds reasonable, but I wonder whether there are any ready solutions.
Any ideas on how to solve this task with clear intent and some ready solutions? Boost is welcomed. C++17 and ranges are interesting to see.
You could use boost::range library.
auto reductionLambda = [](const Complex& a) { return calcReduction(a); };
auto it = boost::range::min_element(values | boost::adaptors::transformed(
std::ref(reductionLambda));
Ranges themselves should be coming to the standard C++ with C++17 as well.
Edit
As we figured out in comments, this would also make the conversion twice.
So here's something fun:
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/assign.hpp>
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
template <class Iterator, class UnaryFunction>
class memoizing_transform_iterator
: public boost::iterator_adaptor<
memoizing_transform_iterator<Iterator, UnaryFunction> // Derived
, Iterator // Base
, std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))> // Value
, boost::forward_traversal_tag // CategoryOrTraversal
>
{
public:
memoizing_transform_iterator() {}
explicit memoizing_transform_iterator(Iterator iter, UnaryFunction f)
: memoizing_transform_iterator::iterator_adaptor_(iter), fun(f) {}
static int total;
private:
friend class boost::iterator_core_access;
void increment() { ++this->base_reference(); memoized = false; }
using MemoType = std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))>;
MemoType& dereference() const
{
if (!memoized) {
++total;
memoized = true;
memo = fun(*this->base());
}
return memo;
}
UnaryFunction fun;
mutable bool memoized = false;
mutable MemoType memo;
};
template <class Iterator, class UnaryFunction>
auto make_memoizing_transform_iterator(Iterator i, UnaryFunction&& f)
{
return memoizing_transform_iterator<Iterator, UnaryFunction>(i, f);
}
template<class I, class U>
int memoizing_transform_iterator<I, U>::total = 0;
// THIS IS COPIED FROM LIBSTDC++
template<typename _ForwardIterator>
_ForwardIterator
min_el(_ForwardIterator __first, _ForwardIterator __last)
{
if (__first == __last)
return __first;
_ForwardIterator __result = __first;
while (++__first != __last)
if (*__first < *__result)
__result = __first;
return __result;
}
int main(int argc, const char* argv[])
{
using namespace boost::assign;
std::vector<int> input;
input += 2,3,4,1,5,6,7,8,9,10;
auto transformLambda = [](const int& a) { return a*2; };
auto begin_it = make_memoizing_transform_iterator(input.begin(), std::ref(transformLambda));
auto end_it = make_memoizing_transform_iterator(input.end(), std::ref(transformLambda));
std::cout << *min_el(begin_it, end_it).base() << "\n";
std::cout <<begin_it.total;
return 0;
}
Basically I implemented an iterator that memoizes the result of calling the transformation functor. The weird part though is that at least in online compilers, the iterators are copied before their dereferenced values are compared (thus defeating the purpose of memoizing). However when I simply copied the implementation from libstdc++, it works as expected. Perhaps you could try it out on a real machine? The live example is here.
Small edit:
I tested on VS2015 and it works as expected with std::min_element.
这篇关于根据转换后的值查找最小元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
