1

私が開発しているプログラムは、次の関数を呼び出すと 3 倍遅くなります。数百万回呼び出されなくても悪くないでしょう。

double obterNormLarguraBanda(const std::vector<double>& v, int periodos)
{
    int aa; 
    double maximo, minimo, valor;
    std::vector<double>::const_iterator inicio;
    if (v.size() < periodos)
    {   
        inicio = v.begin();
    }   
    else
    {   
        inicio = v.end() - periodos;
    }   
    maximo = *max_element(inicio, v.end(), excludeWrong);
    minimo = *min_element(inicio, v.end(), excludeWrong);
    return (v.back()-minimo)/(maximo - minimo);
}

bool excludeWrong(double i, double j)
{
    if (i==-1 || j==-1) return false;
    return i<j;
}

periodosこの関数を大幅に高速化する別の方法はありますか?

ルイス

4

5 に答える 5

3

他の人が言うこととは反対に、1 つの操作で 2*n 回反復するか、2 つの操作で n 回反復するかの違いはほとんどまたはまったくないため、std::max_element()andの 2 つの呼び出しをstd::min_element()1つの呼び出しに置き換えても、パフォーマンスが大幅に向上するとは思いません。minmax_element()

ただし、違いを生むのは、アルゴリズムから 2 つの呼び出しを完全に削除することです。つまり、コンテナ全体に対して新しいデータを再度比較するのではなく、最小要素と最大要素を見つけてから、新しいデータが入ってきたときにそれらをチェックします。

 double obterNormLarguraBanda(const std::vector<double>& v,
                              double maximo, double minimo)
{
    return (v.back()-minimo)/(maximo - minimo);
}

bool excludeWrong(double i, double j)
{
    if (i==-1 || j==-1) return false;
    return i<j;
}

// usage example
void f()
{
    std::vector<double> v;
    // ...
    double maximo = *max_element(inicio, v.end(), excludeWrong);
    double minimo = *min_element(inicio, v.end(), excludeWrong);
    for( int i = 0; i != 1000; ++i ) {
        // if( ! excludeWrong(new_datum, maximo) ) maximo = new_datum;
        // if( excludeWrong(new_datum, minimo) ) minimo = new_datum;
        double d = obterNormLarguraBanda(...);
    }
}
于 2011-02-24T15:27:31.623 に答える
3

編集：述語の使用に気づきませんでした（スペイン語は私を少し驚かせました！）数分間書き直させてください...

max_elementmin_elementステップ全体を1つの関数で実行できる場合、両方とも範囲を反復しています。

一部のコンパイラはminmax_elementSTL に関数を持っていると思いますが、それが標準にあるとは思いません。自分で書くことができます。私はもともとこれをテンプレート化されていないバージョンとして書きましたが、優れたコンパイラがあれば違いはありません。

このようなことを試してください（テストされていません）

template <typename Iter, typename Pred>
void minmax_element(Iter begin, Iter end, Iter& min, Iter& max, const Pred& comp)
{
    min = begin;
    max = begin;

    typedef std::iterator_traits<Iter>::value_type T;
    for (++begin; begin != end; ++begin)
    {
        if (comp(*max, *begin))
            max = begin;
        else if (comp(*begin, *min))
            min = begin;
    }
}

template <typename Iter>
void minmax_element(Iter begin, Iter end, Iter& min, Iter& max)
{
    minmax_element(begin, end, min, max, std::less<std::iterator_traits<Iter>::value_type>());
}
于 2011-02-24T15:24:25.647 に答える
1

これら 2 つの呼び出しを 1 つの に置き換えることができますstd::minmax_element()。

于 2011-02-24T15:24:04.260 に答える
0

これは、パフォーマンスに関する特定の質問に対する回答ではないため、価値がない可能性があります。しかし、excludeWrongcompare 関数は、予期しない、または実装に依存する可能性のある結果を引き起こすようです。比較された最初の値が-1である場合、すべてのケースの最小値と最大値の両方として計算されます。gcc v4.0.2 と Microsoft のコンパイラ v15.00.21022.08 の両方でテストしました。たとえば、次のようになります。

   std::vector<double> v;
   v.push_back( -1 );
   v.push_back( 1 );
   v.push_back( 2 );
   cout << "min: " << *min_element( v.begin(), v.end(), excludeWrong ) << endl;
   cout << "max: " << *max_element( v.begin(), v.end(), excludeWrong ) << endl;

プリント:

min: -1
max: -1

多分それは望ましい結果ですが、少し奇妙に思えます。

于 2011-02-24T15:56:00.920 に答える
0

何に関して「3倍遅い」-別の実装、またはこの関数を呼び出さないだけですか? 2 番目のケースでは、アルゴリズムの複雑さが原因で遅くなる可能性があります。

コードがどのように使用されるかを正確に説明していませんでした。場合によっては、ループで実行する代わりに、最小/最大の計算をキャッシュできます。たとえば、入力ベクトルがめったに変更されない場合、毎回再計算するのは意味がありません。また、変更された場合でも、periodos要素を調べずに最小/最大を更新できます (動的プログラミングが役立つ場合があります)。

生成されたアセンブリをチェックして、奇妙な関数呼び出し (イテレータのセキュア チェックなど) をチェックすることもできます。少なくとも MSVC 2005/2008 では、リリース モードでもデフォルトで有効になっていることがわかっています (_SCL_SECURE マクロを参照)。

于 2011-02-24T15:42:14.840 に答える