7

これは、多次元の数値範囲を反復処理するための単純なクラスです。

#include <array>
#include <limits>

template <int N>
class NumericRange
{
public:
  //  typedef std::vector<double>::const_iterator const_iterator;
  NumericRange() {
    _lower.fill(std::numeric_limits<double>::quiet_NaN());
    _upper.fill(std::numeric_limits<double>::quiet_NaN());
    _delta.fill(std::numeric_limits<double>::quiet_NaN());
  }
  NumericRange(const std::array<double, N> & lower, const std::array<double, N> & upper, const std::array<double, N> & delta):
    _lower(lower), _upper(upper), _delta(delta) {
    _state.fill(std::numeric_limits<double>::quiet_NaN());
    _next_index_to_advance = 0;
  }

  const std::array<double, N> & get_state() const {
    return _state;
  }

  void start() {
    _state = _lower;
  }

  bool in_range(int index_to_advance = N-1) const {
    return ( _state[ index_to_advance ] - _upper[ index_to_advance ] ) < _delta[ index_to_advance ];
  }

  void advance(int index_to_advance = 0) {
    _state[ index_to_advance ] += _delta[ index_to_advance ];
    if ( ! in_range(index_to_advance) ) {
      if (index_to_advance < N-1) {
    // restart index_to_advance
    _state[index_to_advance] = _lower[index_to_advance];

    // carry
    index_to_advance;
    advance(index_to_advance+1);
      }
    }
  }

private:
  std::array<double, N> _lower, _upper, _delta, _state;
  int _next_index_to_advance;
};

int main() {
  std::array<double, 7> lower{0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0};
  std::array<double, 7> upper{1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
  std::array<double, 7> delta{0.03, 0.06, 0.03, 0.06, 0.03, 0.06, 0.03};

  NumericRange<7> nr(lower, upper, delta);
  int c = 0;
  for (nr.start(); nr.in_range(); nr.advance()) {
    const std::array<double, 7> & st = nr.get_state();
    ++c;
  }
  std::cout << "took " << c << " steps" << std::endl;

  return 0;
}

advance関数を非再帰的なバリアントに置き換えると、実行時間が長くなります。

void advance(int index_to_advance = 0) {
  bool carry;
  do {
    carry = false;
    _state[ index_to_advance ] += _delta[ index_to_advance ];
    if ( ! in_range(index_to_advance) ) {
      if (index_to_advance < N-1) {
    // restart index_to_advance
    _state[index_to_advance] = _lower[index_to_advance];

    // carry
    ++index_to_advance;
    carry = true;
    //    advance(index_to_advance);
      }
    }
  } while (carry);
}

ランタイムは、コマンドを介してUNIXユーザー時間を使用して取得されましたtime。コードはオプション付きのgcc-4.7を使用してコンパイルされました-std=c++11 -O3（ただし、gcc-4.6で動作するはずc++0xです）。再帰バージョンには13秒かかり、反復バージョンには30秒かかりました。どちらも終了するには同じ数のadvance呼び出しが必要です（ループnr.get_state()内に配列を出力する場合、どちらも同じことを行います）。for(ns.start()...)

これは楽しいなぞなぞです！再帰がより効率的/最適化可能である理由を理解するのを手伝ってください。

4

2 に答える 2

13

再帰バージョンは末尾再帰の例です。これは、コンパイラーが再帰を反復に変換できることを意味します。これで、変換が実行されると、再帰関数は次のようになります。

void advance(int index_to_advance = 0) {
    _state[ index_to_advance ] += _delta[ index_to_advance ];
    while ( !in_range(index_to_advance) && index_to_advance < N-1 ) {
        // restart index_to_advance
        _state[index_to_advance] = _lower[index_to_advance];

        // carry
        ++index_to_advance;
        _state[ index_to_advance ] += _delta[ index_to_advance ];
    }
  }

ご覧のとおり、バージョンには1つの追加のテストと条件変数が含まれています。よく見ると、ループは次のようになります。

for( ; index_to_advance < N-1 && !in_range(index_to_advance);++index_to_advance)

（最後にを削除します++index_to_advance）、オプティマイザーはそれを展開する可能性が高くなります。

そうは言っても、再帰バージョンが反復バージョンよりもそれほど遅くない理由は説明できますが、これが大きな時間差を説明しているとは思いません。生成されたアセンブリをチェックして、コンパイラが実際に何をしたかを確認します。

于 2012-06-03T01:10:26.017 に答える
3

デビッドロドリゲスが言ったことにさらに詳細を追加するだけです：

末尾再帰の最適化を使用すると、関数は次のようになります。

 void advance(int index_to_advance = 0) {
  top:
  _state[ index_to_advance ] += _delta[ index_to_advance ];
  if ( ! in_range(index_to_advance) ) {
    if (index_to_advance < N-1) {
      // restart index_to_advance
      _state[index_to_advance] = _lower[index_to_advance];

      // carry
      ++index_to_advance;
      goto top;
    }
  }
}

これは確かに私のシステムの再帰バージョンと同じパフォーマンスを持っています（g ++ 4.6.3 -std = c ++ 0x）

于 2012-06-03T01:22:44.387 に答える