c++ - ループの高速範囲 (C++11)

Question

(多変量) 数値範囲を反復処理するコードがいくつかあります。

#include <array>
#include <limits>
#include <iostream>
#include <iterator>

template <int N>
class NumericRange : public std::iterator<double, std::input_iterator_tag>
{
public:
  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());
  }

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

  NumericRange<N> begin() const {
    NumericRange<N> result = *this;
    result.start();
    return result;
  }

  NumericRange<N> end() const {
    NumericRange<N> result = *this;
    result._state = _upper;
    return result;
  }

  bool operator !=(const NumericRange<N> & rhs) const {
    return in_range();
    //    return ! (*this == rhs);
  }

  bool operator ==(const NumericRange<N> & rhs) const {
    return _state == rhs._state && _lower == rhs._lower && _upper == rhs._upper && _delta == rhs._delta;
  }

  const NumericRange<N> & operator ++() {
    advance();
    if ( ! in_range() )
      _state = _upper;
    return *this;
  }

  const std::array<double, N> & operator *() 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);
      }
    }
  }
private:
  std::array<double, N> _lower, _upper, _delta, _state;
};

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()) {
    ++c;
  }
  std::cout << "took " << c << " steps" << std::endl;    
  return 0;
}

g++ -std=c++11 -O3(またはgcc < 4.7 を使用して)コンパイルすると-std=c++0x、私のコンピューターでは約 13.8 秒で実行されます。

main範囲ベースの for ループを使用するように関数を変更すると、次のようになります。

  for (const std::array<double, 7> & arr : nr) {
    ++c;
  }

実行時間は 29.8 秒に増加します。std::vector<double>偶然にも、この約 30 秒の実行時間は、代わりにを使用した場合のオリジナルの実行時間とほぼ同じであるため、範囲ベースの for ループによって生成されたコードをコンパイラが展開できないstd::array<double, N>と思われます。

元の速度を保ちながら、範囲ベースの for ループを使用する方法はありますか?

私が試したこと：

の 2 つのメンバー関数を変更することで、範囲ベースの for ループで目的の速度を得ることができますNumericRange。

bool operator !=(const NumericRange<N> & rhs) const {
  return in_range();
  //    return ! (*this == rhs);
}

const NumericRange<N> & operator ++() {
  advance();
  //    if ( ! in_range() )
  //      _state = _upper;
  return *this;
}

!= operatorただし、が期待どおりに機能しないため、このコードは設計が不十分に感じられます。通常、数値演算では、 .<ではなくループを終了するために使用します==。範囲外の最初の値を見つけることを考えましたが、解析的に行うと、数値エラーのために正確な答えが得られない可能性があります。

私のコードを見る他の人に誤解を与えることなく!= operator、をと同様に動作させるにはどうすればよいでしょうか? <begin()関数と関数を非公開にするだけend()ですが、範囲ベースの for ループでは公開する必要があります。

どうもありがとうございました。

score 13 · Accepted Answer

問題は、私に関する限り、range-for構文を適切に使用していないことです。

一歩後退しましょう：

void foo(std::vector<int> const& v) {
    for (int i: v) {
    }
}

range-forがベクトルを反復処理して整数を抽出する方法に注意してください。

beginいくつかの理由で、からにブリッジするイテレータを実装しないことを選択しましたendが、その代わりに、反復しているもののコピーを再利用しますが、それはごくわずかしか変化せず、大量の余分な作業を行っています（コピーでとチェック）...

注：はを返す必要があるstd::iterator<double, ...>ことを意味します。operator*double&

新しいイディオムを使用する場合は、その期待に準拠する必要があります。

元のオブジェクト（わずかに変更されたもの）を何度もコピーするのではなく、イテレーターで反復することが期待されます。これはC++のイディオムです。

これは、オブジェクトを半分にカットする必要があることを意味します。反復されるオブジェクトでの反復中に不変であるものと、イテレーターで変更されるものをすべて削除します。

私が見ることができるものから：

_lower、_upperおよび_delta固定されています
_state反復変数です

したがって、次のようになります。

template <typename> class NumericRangeIterator

template <unsigned N> // makes no sense having a negative here
class NumericRange {
public:
    template <typename> friend class NumericRangeIterator;

    typedef NumericRangeIterator<NumericRange> iterator;
    typedef NumericRangeIterator<NumericRange const> const_iterator;

    static unsigned const Size = N;

    // ... constructors

    iterator begin(); // to be defined after NumericRangeIterator
    iterator end();

    const_iterator begin() const;
    const_iterator end() const;

private:
    std::array<double, N> _lower, _upper, _delta;
}; // class NumericRange

template <typename T>
class NumericRangeIterator: public
    std::iterator< std::array<double, T::Size>,
                   std::forward_iterator_tag >
{
public:
    template <unsigned> friend class NumericRange;

    NumericRangeIterator(): _range(0), _state() {}

    NumericRangeIterator& operator++() {
        this->advance();
        return *this;
    }

    NumericRangeIterator operator++(int) {
        NumericRangeIterator tmp(*this);
        ++*this;
        return tmp;
    }

    std::array<double, T::Size> const& operator*() const {
        return _state;
    }

    std::array<double, T::Size> const* operator->() const {
        return _state;
    }

    bool operator==(NumericRangeIterator const& other) const {
        return _state != other._state;
    }

    bool operator!=(NumericRangeIterator const& other) const {
        return !(*this == other);
    }


private:
    NumericRangeIterator(T& t, std::array<double, T::Size> s):
        _range(&t), _state(s) {}

    void advance(unsigned index = T::Size - 1);  // as you did
    void in_range(unsigned index = T::Size - 1); // as you did

    T* _range;
    std::array<double, T::Size> _state;
}; // class NumericRangeIterator


template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this, _lower);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator(*this, _upper);
}

そして、このすべての設定で、次のように書くことができます。

for (auto const& state: nr) {
}

どこautoにあると推定されますstd::array<double, nr::Size>。

注：ある意味で誤った反復であるため、iteratorが有用かどうかはわかりません。const_iterator範囲オブジェクトに到達して、イテレータを介して変更することはできません。

編集： operator==遅すぎる、それをより良くする方法は？

私はごまかすことを提案します。

1/イテレータのコンストラクタを変更します

NumericRangeIterator(): _range(0), _state() {}               // sentinel value
NumericRangeIterator(T& t): _range(&t), _state(t._lower) {}

2 /反復を微調整して、最後に新しい「センチネル」値を作成します

void advance() {
    // ...

    if (not this->in_range()) {        // getting out of the iteration ?
       *this = NumericRangeIterator(); // then use the sentinel value
    }
}

3/それに応じbeginてend定義を変更します

template <unsigned N>
auto NumericRange<N>::begin() -> typename NumericRange<N>::iterator {
    return iterator(*this);
}

template <unsigned N>
auto NumericRange<N>::end() -> typename NumericRange<N>::iterator {
    return iterator();
}

4/==歩哨を使用してより平等にする

bool operator==(NumericRangeIterator const& other) const {
    return _range == other._range and _state == other._state;
}

これで、一方がnullで、もう一方がnullでないため、反復全体で==が短絡し_rangeます。最後の呼び出しでのみ、2つの_state属性の比較が実際に行われます。

c++ - ループの高速範囲 (C++11)

1 に答える 1

Related

Reference