16

これが、コードレビューから私にもたらされたタスクです。特別な種類の比較述語に基づいて、セットから最小値を選択したいと考えています。このような：

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を計算し、それらの float を比較します。うまく機能し、きれいに見えます。

問題が見えますか？はい、N要素のセットは時間calcReduction()と呼ばれますが、要素ごとに1回2Nだけ計算するだけで十分です。N

この問題を解決する 1 つの方法は、明示的な計算を記述することです。

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、範囲と縮小関数を受け入れるような独自のアルゴリズムを作成することです。合理的に聞こえますが、すぐに使える解決策があるかどうか疑問に思います。

明確な意図といくつかの準備が整ったソリューションでこのタスクを解決する方法についてのアイデアはありますか? ブースト大歓迎です。C++17 と範囲は興味深いものです。

4

5 に答える 5

4

を使用したソリューションを次に示します (すでにrange-v3 ライブラリで動作し、今後の Ranges TS の作成者による実装)

#include <range/v3/all.hpp>
#include <iostream>
#include <limits>

using namespace ranges::v3;

int main()
{
    auto const expensive = [](auto x) { static int n; std::cout << n++ << " "; return x; };
    auto const v = view::closed_iota(1,10) | view::transform(expensive); 

    auto const m1 = *min_element(v);
    std::cout << "\n" << m1 << "\n";

    auto const inf = std::numeric_limits<int>::max();    
    auto const min = [](auto x, auto y) { return std::min(x, y); };

    auto const m2 = accumulate(v, inf, min);
    std::cout << "\n" << m2 << "\n";    
}

Live On Coliru出力付き：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1
19 20 21 22 23 24 25 26 27 28 
1

ご覧のとおり、 usingmin_elementは2N比較を行いますが、accumulateのみを使用しNます。

于 2016-01-02T20:18:45.753 に答える
2

別のオプションがありますが、これは実質的に 2 番目のソリューションです。正直なところ、はっきりとは見えませんが、誰かが好きかもしれません。(std::pair<float, Complex>削減結果と削減された値を保存するために使用します。)

std::pair<float, Complex> result{std::numeric_limits<float>::max(), {}};
auto output_function = [&result](std::pair<float, Complex> candidate) {
    if (candidate.first < result.first)
        result = candidate;
};
std::transform(values.begin(), values.end(), 
               boost::make_function_output_iterator(output_function),
               [](Complex x) { return std::make_pair(calcReduction(x), x); });

PSコストが高い場合は、結果をオブジェクトcalcReductionにキャッシュすることを検討しましたか? Complex少し複雑な実装になりますが、プレーンを使用できるためstd::min_element、意図が明確になります。

于 2015-10-18T01:31:44.103 に答える