gamma più veloce per il ciclo (C++ 11)

Question

ho qualche codice per iterare su una (multivariata) intervallo numerico:

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

Compilare con g++ -std=c++11 -O3 (o -std=c++0x con gcc < 4.7) viene eseguito in circa 13,8 secondi sul mio computer.

Se cambio la funzione main di utilizzare una gamma-based per ciclo:

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

runtime aumenta a 29,8 secondi. Per coincidenza, questo runtime di ~ 30 secondi è quasi lo stesso del runtime dell'originale quando si utilizza std::vector<double> anziché std::array<double, N>, che mi porta a credere che il compilatore non possa srotolare il codice prodotto dal ciclo basato su intervallo.

C'è un modo per avere la velocità dell'originale e utilizzare ancora i cicli basati su intervalli?

---

Quello che ho provato:

posso ottenere la velocità desiderata con una gamma basata su ciclo for modificando due funzioni membro in 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; 
} 

Tuttavia , questo codice si sente mal progettato perché il != operator non funziona come previsto Normalmente per le operazioni numeriche, io uso < per terminare un lo op piuttosto che ==. Ho pensato di trovare il primo valore fuori range, ma farlo analiticamente potrebbe non dare una risposta esatta a causa di un errore numerico.

Come si può forzare il != operator a comportarsi in modo simile a un < senza fuorviare gli altri che vedranno il mio codice? Farei semplicemente le funzioni begin() e end() private, ma devono essere pubbliche per il ciclo basato su intervallo.

Grazie mille per il vostro aiuto.

Answer 1

Il problema, per quanto mi riguarda, è che non si sta utilizzando l'intervallo-per costruire in modo appropriato.

---

Facciamo un passo indietro:

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

Nota come la gamma-for itera oltre il vettore per estrarre interi.

---

Per alcune ragioni si è scelto di non implementare iteratori per colmare da begin a end, ma invece ri-utilizzare una copia di quello che si effettua l'iterazione, anche se varia solo leggermente, e si sta facendo un ton di lavoro extra (nella copia e negli assegni) ...

Nota: std::iterator<double, ...> significa che operator* deve restituire un double&.

Se si desidera utilizzare il nuovo idioma, sarà necessario conformarsi alle sue aspettative.

L'aspettativa è che si itera con gli iteratori e non copiando l'oggetto originale (leggermente modificato) più e più volte. Questo è l'idioma C++.

Significa che è necessario tagliare a metà il proprio oggetto: estrarre tutto ciò che è immutabile durante l'iterazione nell'oggetto da iterare e cosa viene modificato nell'iteratore.

Da quello che posso vedere:

• _lower, _upper e _delta sono fissi
• _state è l'iterazione variabile

Pertanto, si avrebbe:

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

E con tutto questo l'installazione, è possibile scrivere:

for (auto const& state: nr) { 
} 

dove verranno dedurre auto di essere std::array<double, nr::Size>.

Nota: non sono sicuro che lo iterator sia utile, forse solo lo const_iterator poiché è una falsa iterazione in un modo; non è possibile raggiungere l'oggetto intervallo per modificarlo tramite l'iteratore.

EDIT:operator== è troppo lento, come ottenere di meglio?

Mi propongo di imbrogliare.

1/Modificare i costruttori dell'iteratore

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

2/modificare i iterazione per creare il nuovo valore "sentinella" alla fine

void advance() { 
    // ... 

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

3/Modificare la definizione begin e end di conseguenza

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/Marca == più uguali utilizzando la sentinella

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

Ora, lungo tutta la iterazione == è cortocircuitato perché una delle _range è nullo e l'altra no. Solo all'ultima chiamata si verificherà effettivamente il confronto tra i due attributi _state.