2

私の問題は次のとおりです。contaner X = {x 1 , x 2 , ...,x n } と functionを指定して、値 f(x i ) が最小値に達するfインデックスを見つけます。i

もちろん、ゼロから実装することもできますが、自転車を発明したような気がするので、標準アルゴリズムまたはブースト アルゴリズムを使用してより短いコードを探しています。私が得ることができた最高のものは

template <typename Val>
Val f(Val)
{
.........
}

template <typename It>
It find_minimum(It begin, It end)
{
return std::min_element(begin, end, 
   [](typename It::value_type val1, typename It::value_type val2)
  {
  return f(val1) < f(val2);
  });
}

fしかし、 2N-1 回評価されるという問題があります。

4

4 に答える 4

1

このアルゴリズムを使用するだけです（疑似コード、テンプレートを正しくする時間がありません）

It element= X.first()
Val min = f(element)
It min_el = element
while(element= element.next())
{
    Val temp = f(element);
    if( min > temp)
    {
        min_el = element;
        min = temp;
    }
}
return min_el
于 2013-01-31T10:48:52.403 に答える
0

私が見つけることができる短い答えは std::min_element と boost::transform_iterator を使用しています:

return std::min_element(
  boost::make_transform_iterator(begin, f), 
  boost::make_transform_iterator(end, f)).base();

ただし、std::min_element の実装によっては、2N-1 回の関数呼び出しが必要になる場合があります。

于 2013-02-01T23:16:19.437 に答える
0

all を計算して保存する追加の手順を使用してからf(x)、最小値を探してみませんか?

別のアイデア: x のすべての可能な値を反復処理し、以前の最小値のみを保存しますか?

于 2013-01-31T10:42:44.410 に答える
0

std::min_element の実装を知っている 場合は、状態でラムダを使用できます

auto minElt = std::min_element(data.begin(), data.end(), [f](const int& a, const int& b)->bool
                               {
                                   static int minValCash = f(b);
                                   int v2 = f(a);
                                   bool result = v2 < minValCash;
                                   if(!result)
                                    std::swap(v2, minValCash);
                                   return result;
                               });

于 2013-01-31T11:02:17.163 に答える