Объединение нескольких циклов for в один итератор - PullRequest
0 голосов
/ 15 октября 2018

Скажем, у меня есть гнездо для цикла типа

for (int x = xstart; x < xend; x++){
    for (int y = ystart; y < yend; y++){
        for (int z = zstart; z < zend; z++){
            function_doing_stuff(std::make_tuple(x, y, z));
        }
    }
}

и я хотел бы преобразовать его в

MyRange range(xstart,xend,ystart,yend, zstart,zend);
for (auto point : range){
    function_doing_stuff(point);
}

Как бы я написал класс MyRange, чтобы он был таким же эффективным, как и вложенныйдля петель?Мотивация для этого заключается в том, чтобы иметь возможность использовать стандартные алгоритмы (такие как преобразование, накопление и т. Д.) И создавать код, который в значительной степени не зависит от размерности.

Имея итератор, было бы легко создавать шаблонныефункции, которые работают в диапазоне 1d, 2d или 3d точек.

База кода в настоящее время C ++ 14.

РЕДАКТИРОВАТЬ:

Трудно писать четкие вопросы.Я постараюсь уточнить.Моя проблема не в написании итератора, что я могу сделать.Вместо этого проблема заключается в производительности: возможно ли создать итератор с такой же скоростью, что и для вложенных циклов?

Ответы [ 7 ]

0 голосов
/ 17 октября 2018

Просто очень упрощенная версия, которая будет столь же эффективной, как и цикл for:

#include <tuple>

struct iterator{
  int x;
  int x_start;
  int x_end;
  int y;
  int y_start;
  int y_end;
  int z;
  constexpr auto
  operator*() const{
    return std::tuple{x,y,z};
    }
  constexpr iterator&
  operator++ [[gnu::always_inline]](){
    ++x;
    if (x==x_end){
      x=x_start;
      ++y;
      if (y==y_end) {
        ++z;
        y=y_start;
        }
      }
    return *this;
    }
  constexpr iterator
  operator++(int){
    auto old=*this;
    operator++();
    return old;
    }
  };
struct sentinel{
  int z_end;
  friend constexpr bool
  operator == (const iterator& x,const sentinel& s){
    return x.z==s.z_end;
    }
  friend constexpr bool
  operator == (const sentinel& a,const iterator& x){
    return x==a;
    }
  friend constexpr bool
  operator != (const iterator& x,const sentinel& a){
    return !(x==a);
    }
  friend constexpr bool
  operator != (const sentinel& a,const iterator& x){
    return !(x==a);
    }
  };

struct range{
  iterator start;
  sentinel finish;
  constexpr auto
  begin() const{
    return start;
    }
  constexpr auto
  end()const{
    return finish;
    }
  };

void func(int,int,int);

void test(const range& r){
  for(auto [x,y,z]: r)
    func(x,y,z);
  }
void test(int x_start,int x_end,int y_start,int y_end,int z_start,int z_end){
  for(int z=z_start;z<z_end;++z)
    for(int y=y_start;y<y_end;++y)
      for(int x=x_start;x<x_end;++x)
        func(x,y,z);
  }

Преимущество перед ответом 1201ProgramAlarm заключается в более быстром тесте, выполняемом на каждой итерации благодаря использованию часового.

0 голосов
/ 19 октября 2018

Поскольку вы заботитесь о производительности, вы должны забыть о комбинировании итераторов в обозримом будущем.Центральная проблема заключается в том, что компиляторы еще не могут распутать беспорядок и выяснить, что в нем есть 3 независимые переменные, а тем более выполнить любой обмен циклами, развертывание или объединение.

Если вы должны использовать диапазоны, используйте простые, которыекомпилятор может видеть:

for (int const x : boost::irange<int>(xstart,xend))
    for (int const y : boost::irange<int>(ystart,yend))
        for (int const z : boost::irange<int>(zstart,zend))
            function_doing_stuff(x, y, z);

Кроме того, вы можете фактически передать свой функтор и диапазоны усиления в шаблон:

template <typename Func, typename Range0, typename Range1, typename Range2>
void apply_ranges (Func func, Range0 r0, Range1 r1, Range2 r2)
{
     for (auto const i0 : r0)
         for (auto const i1 : r1)
             for (auto const i2 : r2)
                 func (i0, i1, i2);
}

Если вы действительно заботитесьчто касается производительности, то вам не следует искажать ваш код сложными диапазонами, потому что они затрудняют распутывание позже, когда вы захотите переписать их в свойствах AVX.

0 голосов
/ 17 октября 2018

Вот базовая реализация, которая не использует никаких дополнительных языковых функций или других библиотек.Производительность должна быть очень близка к версии цикла for.

#include <tuple>

class MyRange {
public:
    typedef std::tuple<int, int, int> valtype;
    MyRange(int xstart, int xend, int ystart, int yend, int zstart, int zend): xstart(xstart), xend(xend), ystart(ystart), yend(yend), zstart(zstart), zend(zend) {
    }

    class iterator {
    public:
        iterator(MyRange &c): me(c) {
            curvalue = std::make_tuple(me.xstart, me.ystart, me.zstart);
        }
        iterator(MyRange &c, bool end): me(c) {
            curvalue = std::make_tuple(end ? me.xend : me.xstart, me.ystart, me.zstart);
        }
        valtype operator*() {
            return curvalue;
        }
        iterator &operator++() {
            if (++std::get<2>(curvalue) == me.zend) {
                std::get<2>(curvalue) = me.zstart;
                if (++std::get<1>(curvalue) == me.yend) {
                    std::get<1>(curvalue) = me.ystart;
                    ++std::get<0>(curvalue);
                }
            }
            return *this;
        }
        bool operator==(const iterator &other) const {
            return curvalue == other.curvalue;
        }
        bool operator!=(const iterator &other) const {
            return curvalue != other.curvalue;
        }
    private:
        MyRange &me;
        valtype curvalue;
    };

    iterator begin() {
        return iterator(*this);
    }

    iterator end() {
        return iterator(*this, true);
    }

private:
    int xstart, xend;
    int ystart, yend;
    int zstart, zend;
};

И пример использования:

#include <iostream>

void display(std::tuple<int, int, int> v) {
    std::cout << "(" << std::get<0>(v) << ", " << std::get<1>(v) << ", " << std::get<2>(v) << ")\n";
}

int main() {
    MyRange c(1, 4, 2, 5, 7, 9);
    for (auto v: c) {
        display(v);
    }
}

Я остановился на таких вещах, как константные итераторы, возможно operator+=, уменьшение, постинкремент и т. д. Они были оставлены в качестве упражнения для читателя.

Он сохраняет начальные значения, затем увеличивает каждое значение по очереди, откатывая его назад и увеличивая следующее, когда оно достигаетконечное значение.Это похоже на увеличение числа из нескольких цифр.

0 голосов
/ 16 октября 2018

Еще одна опция, которая напрямую трансплантирует любой код зацикливания, - это использование Coroutine .Это эмулирует yield из Python или C #.

using point = std::tuple<int, int, int>;
using coro = boost::coroutines::asymmetric_coroutine<point>;

coro::pull_type points(
    [&](coro::push_type& yield){
        for (int x = xstart; x < xend; x++){
            for (int y = ystart; y < yend; y++){
                for (int z = zstart; z < zend; z++){
                    yield(std::make_tuple(x, y, z));
                }
            }
        }
    });

for(auto p : points)
    function_doing_stuff(p);
0 голосов
/ 15 октября 2018

С range / v3 , вы можете сделать

auto xs = ranges::view::iota(xstart, xend);
auto ys = ranges::view::iota(ystart, yend);
auto zs = ranges::view::iota(zstart, zend);
for (const auto& point : ranges::view::cartesian_product(xs, ys, zs)){
    function_doing_stuff(point);
}
0 голосов
/ 15 октября 2018

Используя boost::iterator_facade для простоты, вы можете прописать все необходимые элементы.

Сначала у нас есть класс, который итерирует N-мерные индексы как std::array<std::size_t, N>

template<std::size_t N>
class indexes_iterator : public boost::iterator_facade<indexes_iterator, std::array<std::size_t, N>>
{
public:
    template<typename... Dims>
    indexes_iterator(Dims... dims) : dims{ dims... }, values{} {}

private:
    friend class boost::iterator_core_access;

    void increment() { advance(1); }
    void decrement() { advance(-1); }

    void advance(int n) 
    { 
        for (std::size_t i = 0; i < N; ++i)
        { 
            int next = ((values[i] + n) % dims[i]); 
            n = (n \ dims[i]) + (next < value); 
            values[i] = next;
        }
    }

    std::size_t distance(indexes_iterator const & other) const
    {
        std::size_t result = 0, mul = 1;
        for (std::size_t i = 0; i < dims; ++i)
        {
             result += mul * other[i] - values[i];
             mul *= ends[i];
        }
    }

    bool equal(indexes_iterator const& other) const
    {
        return values == other.values;
    }

    std::array<std::size_t, N> & dereference() const { return values; }

    std::array<std::size_t, N> ends;
    std::array<std::size_t, N> values;
}

Затеммы используем это, чтобы сделать что-то похожее на boost::zip_iterator, но вместо того, чтобы продвигаться все вместе, мы добавляем наши индексы.

template <typename... Iterators>
class product_iterator : public boost::iterator_facade<product_iterator<Iterators...>, const std::tuple<decltype(*std::declval<Iterators>())...>, boost::random_access_traversal_tag>
{
    using ref = std::tuple<decltype(*std::declval<Iterators>())...>;
public:
    product_iterator(Iterators ... ends) : indexes() , iterators(std::make_tuple(ends...)) {}
    template <typename ... Sizes>
    product_iterator(Iterators ... begins, Sizes ... sizes) 
      : indexes(sizes...), 
        iterators(begins...) 
    {}
private:
    friend class boost::iterator_core_access;

    template<std::size_t... Is>
    ref dereference_impl(std::index_sequence<Is...> idxs) const
    {
        auto offs = offset(idxs);
        return { *std::get<Is>(offs)... };
    }

    ref dereference() const
    { 
        return dereference_impl(std::index_sequence_for<Iterators...>{}); 
    }

    void increment() { ++indexes; }
    void decrement() { --indexes; }
    void advance(int n) { indexes += n; }

    template<std::size_t... Is>
    std::tuple<Iterators...> offset(std::index_sequence<Is...>) const
    {
        auto idxs = *indexes;
        return { (std::get<Is>(iterators) + std::get<Is>(idxs))... };
    }

    bool equal(product_iterator const & other) const 
    {
        return offset(std::index_sequence_for<Iterators...>{}) 
            == other.offset(std::index_sequence_for<Iterators...>{}); 
    }

    indexes_iterator<sizeof...(Iterators)> indexes;
    std::tuple<Iterators...> iterators;
};

Затем мы заключаем это в boost::iterator_range

template <typename... Ranges>
auto make_product_range(Ranges&&... rngs)
{
    product_iterator<decltype(begin(rngs))...> b(begin(rngs)..., std::distance(std::begin(rngs), std::end(rngs))...);
    product_iterator<decltype(begin(rngs))...> e(end(rngs)...);
    return boost::iterator_range<product_iterator<decltype(begin(rngs))...>>(b, e);
}

int main()
{
    using ranges::view::iota;
    for (auto p : make_product_range(iota(xstart, xend), iota(ystart, yend), iota(zstart, zend)))
        // ...
    return 0;
}

Посмотри на Годболт

0 голосов
/ 15 октября 2018

Вы можете представить свой собственный класс как

class myClass {
  public:
    myClass (int x, int y, int z):m_x(x) , m_y(y), m_z(z){};
  private: 
    int m_x, m_y, m_z;

}

и затем инициализировать std::vector<myClass> с помощью вашего тройного цикла

std::vector<myClass> myVec;
myVec.reserve((xend-xstart)*(yend-ystart)*(zend-zstart)); // alloc memory only once;
for (int x = ystart; x < xend; x++){
    for (int y = xstart; y < yend; y++){ // I assume you have a copy paste error here
        for (int z = zstart; z < zend; z++){
            myVec.push_back({x,y,z})
        }
    }
}

Наконец, вы можете использовать все хорошие алгоритмы std сstd::vector<myClass> myVec.С синтаксическим сахаром

using MyRange = std::vector<MyClass>;

и

MyRange makeMyRange(int xstart, int xend, int ystart, int yend, int zstart,int zend) {
    MyRange myVec;
    // loop from above
    return MyRange;
}

вы можете написать

const MyRange range = makeMyRange(xstart, xend, ystart, yend, zstart, zend);
for (auto point : range){
    function_doing_stuff(point);
}

С новой семантикой перемещения это не приведет к созданию ненужных копий.Обратите внимание, что интерфейс к этой функции довольно плохой.Возможно, лучше использовать 3 пары типа int, обозначая интервал x, y, z.

Возможно, вы измените имена на что-то осмысленное (например, myClass может быть Point).

...