gama más rápido para el bucle (C++ 11)

Question

tengo algo de código para iterar sobre un (multivariante) rango numérico:

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

Compilar con g++ -std=c++11 -O3 (o -std=c++0x con gcc < 4.7) discurre en unos 13,8 segundos en mi computadora.

Si cambio de la función de main para utilizar un bucle basado en la gama:

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

el tiempo de ejecución se incrementa a 29,8 segundos. Casualmente, este ~ 30 segundos de tiempo de ejecución es casi el mismo que el tiempo de ejecución del original al usar std::vector<double> en lugar de std::array<double, N>, lo que me lleva a creer que el compilador no puede desenrollar el código producido por el bucle for-based.

¿Hay alguna manera de tener la velocidad del original y aún usar bucles basados ​​en rangos?

---

Lo que he intentado:

que pueda obtener la velocidad deseada con un bucle for cambiando dos funciones miembro en NumericRange a base de gama: Sin embargo

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

, este código se siente mal diseñado porque el != operator no funciona como se esperaba. Normalmente para las operaciones numéricas, uso < para terminar un lo op en lugar de ==. Pensé en encontrar el primer valor fuera de rango, pero hacerlo analíticamente puede no dar una respuesta exacta debido a un error numérico.

¿Cómo se fuerza al != operator a comportarse de manera similar a un < sin engañar a otros que verán mi código? Simplemente haría que las funciones begin() y end() fueran privadas, pero deben ser públicas para el bucle for basado en rango.

Muchas gracias por su ayuda.

Answer 1

El problema, en lo que a mí respecta, es que no está utilizando la construcción range-for adecuadamente.

---

Tomemos un paso atrás:

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

Nota cómo el rango de itera sobre el vector para extraer enteros.

---

Para algunas razones por las que optó por no implementar iteradores para tender un puente entre begin a end, pero en su lugar volver a utilizar una copia de lo que está interactuando sobre, a pesar de que sólo se varía muy poco, y que está haciendo una ton de trabajo extra (en las copias y cheques) ...

Nota: std::iterator<double, ...> significa que operator* debería devolver un .

Si desea utilizar la nueva expresión idiomática, deberá cumplir con sus expectativas.

La expectativa es que itere con los iteradores y no copie el objeto original (ligeramente modificado) una y otra vez. Esta es la expresión C++.

Significa que tendrá que cortar su objeto a la mitad: sacar todo lo que es inmutable durante la iteración en el objeto que se va a iterar y lo que se modifica en el iterador.

Por lo que puedo ver:

• _lower, _upper y _delta se fijan
• _state es la variable de iteración

Por lo tanto, tendría que:

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

Y con todo esto configuración, puede escribir:

for (auto const& state: nr) { 
} 

Cuando se deducirá auto para ser std::array<double, nr::Size>.

Nota: no estoy seguro de que el iterator sea útil, tal vez solo el const_iterator, ya que es una iteración falsa en cierto modo; no puede alcanzar el objeto rango para modificarlo a través del iterador.

EDITAR:operator== es demasiado lento, ¿cómo hacerlo mejor?

Propongo hacer trampa.

1/Modificar los constructores del iterador

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

2/Tweak la iteración para crear el nuevo valor "centinela" al final

void advance() { 
    // ... 

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

3/Cambiar la definición begin y end en consecuencia

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 == más iguales utilizando el centinela

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

Ahora, todo a lo largo de iteración la == está cortocircuitado porque uno de los _range es nulo y el otro no lo es. Solo en la última llamada se producirá la comparación de los dos atributos _state.