ループの高速化の範囲（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; 
} 

は（GCC < 4.7または-std=c++0x）g++ -std=c++11 -O3してコンパイルは約13.8秒で実行します私のコンピューターで。

私は範囲ベースのforループを使用するmain機能を変更する場合：29.8秒に

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

ランタイム増加を。 std::vector<double>代わりのstd::array<double, N>を使用しているとき偶然にも、この〜30秒ランタイムコンパイラを信じるために私をリードし、ほぼ元の実行時と同じであるは範囲ベースのforループにより生成されたコードをアンロールすることはできません。

元の速度を持っているし、まだループの範囲ベースを使用する方法はありますか？私は範囲ベースNumericRangeに2つのメンバ関数を変更することにより、forループで所望の速度を得ることができます

を：私が試した

---

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; 
} 

しかし、数値演算のために通常予想されるように、このコードはあまり私はLOを終了するために<を使用し、動作しない!= operatorために設計されて感じていますopではなく==です。私は最初の範囲外の値を見つけることを考えましたが、分析的には数値誤差のために正確な答えを得られないかもしれません。

!= operatorは、コードを表示する他の人を誤解させることなく、<と同様に動作するようにするにはどうすればよいですか？私は単にプライベートbegin()とend()機能を作ると思いますが、彼らは範囲ベースのforループのための公開する必要があります。

おかげであなたの助けのためにたくさん。

Answer 1

問題は、私に関する限り、あなたは適切な範囲-ための構築物を使用していないということです。

---

は、私たちはバックステップを見てみましょう：レンジ用ベクトルを反復処理整数を抽出する方法を

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

注意。あなたはそれが非常にわずかしか変化しても、繰り返し処理され、そしてあなたが何をしているかのコピーをbeginからendに橋渡しするイテレータを実装し、代わりに再使用しないことを選択したいくつかの理由から

---

トン余分な仕事（コピーとチェックで）...

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

新しいイディオムを使いたい場合は、その期待に従わなければなりません。

イテレーターで繰り返し、元のオブジェクト（わずかに変更されている）を何度も何度も繰り返してコピーすることではありません。これはC++イディオムです。

これは、オブジェクトを半分にカットする必要があることを意味します。反復処理されるオブジェクト内の反復処理中のすべてと、反復処理部で変更された処理を取り除きます。私が見ることができるものから、

：

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); 
} 

：

• _lower、_upperと_deltaが固定されている
• _stateしたがって、あなたが持っているでしょう

変数の繰り返しでありますそして、このすべてでセットアップは、次のように記述することができます：

autoは std::array<double, nr::Size>なると推定されます

for (auto const& state: nr) { 
} 

を。

注：iteratorが有用であるかどうか、ちょうどconst_iteratorであるかどうかは、偽の反復であるためです。範囲オブジェクトに到達してイテレータで変更することはできません。

EDIT：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/Make の一方がヌルであり、他方ではないため、すべての==反復に沿って、今センチネル

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

を使用することによって、より均等が短絡です。最後の呼び出しでのみ、2つの属性の比較が実際に行われます。