Odpowiednik C ++ do wzorca generatora Pythona

Mam przykładowy kod w Pythonie, który muszę naśladować w C ++. Nie potrzebuję żadnego konkretnego rozwiązania (np. Rozwiązania oparte na wspólnych rutynach wydajności, chociaż byłyby one również akceptowalnymi odpowiedziami), po prostu muszę w jakiś sposób odtworzyć semantykę.

Pyton

Jest to podstawowy generator sekwencji, wyraźnie zbyt duży, aby przechowywać zmaterializowaną wersję.

def pair_sequence():
    for i in range(2**32):
        for j in range(2**32):
            yield (i, j)

Celem jest zachowanie dwóch wystąpień powyższej sekwencji i iteracja po nich w pół-lockstep, ale w fragmentach. W poniższym przykładzie first_passużywa sekwencji par do zainicjowania bufora, a następnie second_passodtwarza tę samą dokładną sekwencję i ponownie przetwarza bufor.

def run():
    seq1 = pair_sequence()
    seq2 = pair_sequence()

    buffer = [0] * 1000
    first_pass(seq1, buffer)
    second_pass(seq2, buffer)
    ... repeat ...

C ++

Jedyną rzeczą, jaką mogę znaleźć dla rozwiązania w C ++, jest naśladowanie za yieldpomocą coroutines C ++, ale nie znalazłem żadnego dobrego odniesienia, jak to zrobić. Interesują mnie również alternatywne (nie ogólne) rozwiązania tego problemu. Nie mam wystarczającej ilości pamięci, aby zachować kopię sekwencji między przejściami.

Generatory istnieją w C ++, pod inną nazwą: Iteratory wejściowe . Na przykład czytanie z std::cinjest podobne do posiadania generatora char.

Musisz po prostu zrozumieć, co robi generator:

• jest blob danych: zmienne lokalne definiują stan
• istnieje metoda init
• istnieje metoda „następna”
• istnieje sposób na zakończenie sygnału

W twoim banalnym przykładzie jest to dość łatwe. Koncepcyjnie:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Oczywiście opakowujemy to jako odpowiednią klasę:

class PairSequence:
    // (implicit aliases)
    public std::iterator<
        std::input_iterator_tag,
        std::pair<unsigned, unsigned>
    >
{
  // C++03
  typedef void (PairSequence::*BoolLike)();
  void non_comparable();
public:
  // C++11 (explicit aliases)
  using iterator_category = std::input_iterator_tag;
  using value_type = std::pair<unsigned, unsigned>;
  using reference = value_type const&;
  using pointer = value_type const*;
  using difference_type = ptrdiff_t;

  // C++03 (explicit aliases)
  typedef std::input_iterator_tag iterator_category;
  typedef std::pair<unsigned, unsigned> value_type;
  typedef value_type const& reference;
  typedef value_type const* pointer;
  typedef ptrdiff_t difference_type;

  PairSequence(): done(false) {}

  // C++11
  explicit operator bool() const { return !done; }

  // C++03
  // Safe Bool idiom
  operator BoolLike() const {
    return done ? 0 : &PairSequence::non_comparable;
  }

  reference operator*() const { return ij; }
  pointer operator->() const { return &ij; }

  PairSequence& operator++() {
    static unsigned const Max = std::numeric_limts<unsigned>::max();

    assert(!done);

    if (ij.second != Max) { ++ij.second; return *this; }
    if (ij.first != Max) { ij.second = 0; ++ij.first; return *this; }

    done = true;
    return *this;
  }

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

private:
  bool done;
  value_type ij;
};

Więc hum yeah ... może być tak, że C ++ jest odrobinę bardziej rozwlekły :)

W C ++ są iteratory, ale implementacja iteratora nie jest prosta: należy zapoznać się z koncepcjami iteratorów i dokładnie zaprojektować nową klasę iteratora, aby je zaimplementować. Na szczęście Boost ma szablon iterator_facade, który powinien pomóc we wdrożeniu iteratorów i generatorów kompatybilnych z iteratorami.

Czasami do zaimplementowania iteratora można użyć programu bez stosu .

PS Zobacz także ten artykuł, który wspomina zarówno o switchwłamaniu Christophera M. Kohlhoffa, jak i Boost.Coroutine autorstwa Olivera Kowalke. Praca Oliver KOWALKE jest to nawiązanie na Boost.Coroutine Giovanni P. Deretta.

PS Myślę, że można też napisać coś w rodzaju generatora z lambdami :

std::function<int()> generator = []{
  int i = 0;
  return [=]() mutable {
    return i < 10 ? i++ : -1;
  };
}();
int ret = 0; while ((ret = generator()) != -1) std::cout << "generator: " << ret << std::endl;

Lub z funktorem:

struct generator_t {
  int i = 0;
  int operator() () {
    return i < 10 ? i++ : -1;
  }
} generator;
int ret = 0; while ((ret = generator()) != -1) std::cout << "generator: " << ret << std::endl;

PS Oto generator zaimplementowany w korektach Mordoru :

#include <iostream>
using std::cout; using std::endl;
#include <mordor/coroutine.h>
using Mordor::Coroutine; using Mordor::Fiber;

void testMordor() {
  Coroutine<int> coro ([](Coroutine<int>& self) {
    int i = 0; while (i < 9) self.yield (i++);
  });
  for (int i = coro.call(); coro.state() != Fiber::TERM; i = coro.call()) cout << i << endl;
}

Ponieważ Boost.Coroutine2 obsługuje go teraz bardzo dobrze (znalazłem go, ponieważ chciałem rozwiązać dokładnie ten sam yieldproblem), publikuję kod C ++, który pasuje do twojego pierwotnego zamiaru:

#include <stdint.h>
#include <iostream>
#include <memory>
#include <boost/coroutine2/all.hpp>

typedef boost::coroutines2::coroutine<std::pair<uint16_t, uint16_t>> coro_t;

void pair_sequence(coro_t::push_type& yield)
{
    uint16_t i = 0;
    uint16_t j = 0;
    for (;;) {
        for (;;) {
            yield(std::make_pair(i, j));
            if (++j == 0)
                break;
        }
        if (++i == 0)
            break;
    }
}

int main()
{
    coro_t::pull_type seq(boost::coroutines2::fixedsize_stack(),
                          pair_sequence);
    for (auto pair : seq) {
        print_pair(pair);
    }
    //while (seq) {
    //    print_pair(seq.get());
    //    seq();
    //}
}

W tym przykładzie pair_sequencenie przyjmuje dodatkowych argumentów. Jeśli to konieczne, std::bindlub należy użyć lambdy do wygenerowania obiektu funkcji, który przyjmuje tylko jeden argument (of push_type), kiedy jest przekazywany do coro_t::pull_typekonstruktora.

Wszystkie odpowiedzi, które wymagają napisania własnego iteratora, są całkowicie błędne. Takie odpowiedzi całkowicie pomijają sens generatorów Pythona (jedna z największych i unikalnych funkcji języka). Najważniejszą rzeczą dotyczącą generatorów jest to, że wykonanie rozpoczyna się tam, gdzie zostało przerwane. Nie dzieje się tak w przypadku iteratorów. Zamiast tego należy ręcznie przechowywać informacje o stanie w taki sposób, że gdy operator ++ lub operator * zostanie wywołany od nowa, właściwa informacja będzie umieszczona na samym początku następnego wywołania funkcji. Dlatego pisanie własnego iteratora C ++ jest gigantycznym problemem; podczas gdy generatory są eleganckie i łatwe do odczytania + zapisu.

Nie sądzę, że istnieje dobry analog dla generatorów Pythona w natywnym C ++, przynajmniej jeszcze nie teraz (istnieje rummor, że wydajność wyląduje w C ++ 17 ). Możesz uzyskać coś podobnego, odwołując się do strony trzeciej (np. Sugestii Yongwei's Boost) lub tocząc własną.

Powiedziałbym, że najbliższą rzeczą w natywnym C ++ są wątki. Wątek może utrzymywać zawieszony zestaw zmiennych lokalnych i może kontynuować wykonywanie od miejsca, w którym został przerwany, podobnie jak generatory, ale musisz rzucić trochę dodatkowej infrastruktury, aby obsługiwać komunikację między obiektem generatora a jego wywołującym. Na przykład

// Infrastructure

template <typename Element>
class Channel { ... };

// Application

using IntPair = std::pair<int, int>;

void yield_pairs(int end_i, int end_j, Channel<IntPair>* out) {
  for (int i = 0; i < end_i; ++i) {
    for (int j = 0; j < end_j; ++j) {
      out->send(IntPair{i, j});  // "yield"
    }
  }
  out->close();
}

void MyApp() {
  Channel<IntPair> pairs;
  std::thread generator(yield_pairs, 32, 32, &pairs);
  for (IntPair pair : pairs) {
    UsePair(pair);
  }
  generator.join();
}

To rozwiązanie ma jednak kilka wad:

1. Wątki są „drogie”. Większość ludzi uznałaby to za „ekstrawaganckie” użycie wątków, zwłaszcza gdy generator jest tak prosty.
2. Jest kilka czynności porządkujących, o których musisz pamiętać. Mogłyby być zautomatyzowane, ale potrzebowałbyś jeszcze większej infrastruktury, która znowu może być postrzegana jako „zbyt ekstrawagancka”. W każdym razie porządki, których potrzebujesz, to:
   1. out-> close ()
   2. generator.join ()
3. Nie pozwala to na zatrzymanie generatora. Możesz wprowadzić pewne modyfikacje, aby dodać tę możliwość, ale dodaje to bałaganu do kodu. Nigdy nie byłaby tak czysta, jak instrukcja yield w Pythonie.
4. Oprócz 2, istnieją inne bity schematu, które są potrzebne za każdym razem, gdy chcesz „utworzyć instancję” obiektu generatora:
   1. Parametr kanał * wyjście
   2. Dodatkowe zmienne w main: pary, generator

Prawdopodobnie powinieneś sprawdzić generatory w std :: experimental w Visual Studio 2015 np .: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Myślę, że to jest dokładnie to, czego szukasz. Ogólnie generatory powinny być dostępne w C ++ 17, ponieważ jest to tylko eksperymentalna funkcja Microsoft VC.

Jeśli musisz to zrobić tylko dla stosunkowo niewielkiej liczby określonych generatorów, możesz zaimplementować każdy z nich jako klasę, w której dane składowe są równoważne zmiennym lokalnym funkcji generatora w języku Python. Następnie masz następną funkcję, która zwraca następną rzecz, którą wygenerowałby generator, aktualizując stan wewnętrzny, gdy to robi.

Wydaje mi się, że jest to zasadniczo podobne do sposobu implementacji generatorów Pythona. Główną różnicą jest to, że potrafią zapamiętać przesunięcie w kodzie bajtowym funkcji generatora jako część „stanu wewnętrznego”, co oznacza, że ​​generatory można zapisać jako pętle zawierające plony. Zamiast tego musiałbyś obliczyć następną wartość z poprzedniej. W przypadku twojego pair_sequencejest to dość trywialne. Może to nie być dla złożonych generatorów.

Potrzebujesz również sposobu wskazania zakończenia. Jeśli to, co zwracasz, jest „podobne do wskaźnika”, a NULL nie powinno być prawidłową wartością uzyskiwaną, możesz użyć wskaźnika NULL jako wskaźnika zakończenia. W przeciwnym razie potrzebny jest sygnał poza pasmem.

Coś takiego jest bardzo podobne:

struct pair_sequence
{
    typedef pair<unsigned int, unsigned int> result_type;
    static const unsigned int limit = numeric_limits<unsigned int>::max()

    pair_sequence() : i(0), j(0) {}

    result_type operator()()
    {
        result_type r(i, j);
        if(j < limit) j++;
        else if(i < limit)
        {
          j = 0;
          i++;
        }
        else throw out_of_range("end of iteration");
    }

    private:
        unsigned int i;
        unsigned int j;
}

Używanie operatora () to tylko kwestia tego, co chcesz zrobić z tym generatorem, możesz również zbudować go jako strumień i upewnić się, że dostosowuje się na przykład do istream_iterator.

Korzystanie z range-v3 :

#include <iostream>
#include <tuple>
#include <range/v3/all.hpp>

using namespace std;
using namespace ranges;

auto generator = [x = view::iota(0) | view::take(3)] {
    return view::cartesian_product(x, x);
};

int main () {
    for (auto x : generator()) {
        cout << get<0>(x) << ", " << get<1>(x) << endl;
    }

    return 0;
}

Coś jak to :

Przykładowe zastosowanie:

using ull = unsigned long long;

auto main() -> int {
    for (ull val : range_t<ull>(100)) {
        std::cout << val << std::endl;
    }

    return 0;
}

Drukuje liczby od 0 do 99

Cóż, dzisiaj również szukałem łatwej implementacji kolekcji w C ++ 11. Właściwie byłem rozczarowany, ponieważ wszystko, co znalazłem, jest zbyt dalekie od takich rzeczy, jak generatory Pythona lub operator C # wydajności ... lub zbyt skomplikowane.

Celem jest wykonanie kolekcji, która będzie emitować swoje przedmioty tylko wtedy, gdy jest to wymagane.

Chciałem, żeby było tak:

auto emitter = on_range<int>(a, b).yield(
    [](int i) {
         /* do something with i */
         return i * 2;
    });

Znalazłem ten post, najlepsza odpowiedź IMHO dotyczyła boost.coroutine2 autorstwa Yongwei Wu . Ponieważ jest najbliżej tego, czego chciał autor.

Warto się uczyć kurtyn doładowania .. I chyba będę robić w weekendy. Ale póki co używam mojej bardzo małej implementacji. Mam nadzieję, że pomoże to komuś innemu.

Poniżej przykład użycia, a następnie realizacji.

Przykład.cpp

#include <iostream>
#include "Generator.h"
int main() {
    typedef std::pair<int, int> res_t;

    auto emitter = Generator<res_t, int>::on_range(0, 3)
        .yield([](int i) {
            return std::make_pair(i, i * i);
        });

    for (auto kv : emitter) {
        std::cout << kv.first << "^2 = " << kv.second << std::endl;
    }

    return 0;
}

Generator.h

template<typename ResTy, typename IndexTy>
struct yield_function{
    typedef std::function<ResTy(IndexTy)> type;
};

template<typename ResTy, typename IndexTy>
class YieldConstIterator {
public:
    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;

    typedef YieldConstIterator<ResTy, IndexTy> mytype_t;
    typedef ResTy value_type;

    YieldConstIterator(index_t index, yield_function_t yieldFunction) :
            mIndex(index),
            mYieldFunction(yieldFunction) {}

    mytype_t &operator++() {
        ++mIndex;
        return *this;
    }

    const value_type operator*() const {
        return mYieldFunction(mIndex);
    }

    bool operator!=(const mytype_t &r) const {
        return mIndex != r.mIndex;
    }

protected:

    index_t mIndex;
    yield_function_t mYieldFunction;
};

template<typename ResTy, typename IndexTy>
class YieldIterator : public YieldConstIterator<ResTy, IndexTy> {
public:

    typedef YieldConstIterator<ResTy, IndexTy> parent_t;

    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;
    typedef ResTy value_type;

    YieldIterator(index_t index, yield_function_t yieldFunction) :
            parent_t(index, yieldFunction) {}

    value_type operator*() {
        return parent_t::mYieldFunction(parent_t::mIndex);
    }
};

template<typename IndexTy>
struct Range {
public:
    typedef IndexTy index_t;
    typedef Range<IndexTy> mytype_t;

    index_t begin;
    index_t end;
};

template<typename ResTy, typename IndexTy>
class GeneratorCollection {
public:

    typedef Range<IndexTy> range_t;

    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;
    typedef YieldIterator<ResTy, IndexTy> iterator;
    typedef YieldConstIterator<ResTy, IndexTy> const_iterator;

    GeneratorCollection(range_t range, const yield_function_t &yieldF) :
            mRange(range),
            mYieldFunction(yieldF) {}

    iterator begin() {
        return iterator(mRange.begin, mYieldFunction);
    }

    iterator end() {
        return iterator(mRange.end, mYieldFunction);
    }

    const_iterator begin() const {
        return const_iterator(mRange.begin, mYieldFunction);
    }

    const_iterator end() const {
        return const_iterator(mRange.end, mYieldFunction);
    }

private:
    range_t mRange;
    yield_function_t mYieldFunction;
};

template<typename ResTy, typename IndexTy>
class Generator {
public:
    typedef IndexTy index_t;
    typedef ResTy res_t;
    typedef typename yield_function<res_t, index_t>::type yield_function_t;

    typedef Generator<ResTy, IndexTy> mytype_t;
    typedef Range<IndexTy> parent_t;
    typedef GeneratorCollection<ResTy, IndexTy> finalized_emitter_t;
    typedef  Range<IndexTy> range_t;

protected:
    Generator(range_t range) : mRange(range) {}
public:
    static mytype_t on_range(index_t begin, index_t end) {
        return mytype_t({ begin, end });
    }

    finalized_emitter_t yield(yield_function_t f) {
        return finalized_emitter_t(mRange, f);
    }
protected:

    range_t mRange;
};      

Ta odpowiedź działa w C (i dlatego myślę, że działa również w C ++)

#include <stdio.h>

const uint64_t MAX = 1ll<<32;

typedef struct {
    uint64_t i, j;
} Pair;

Pair* generate_pairs()
{
    static uint64_t i = 0;
    static uint64_t j = 0;
    
    Pair p = {i,j};
    if(j++ < MAX)
    {
        return &p;
    }
        else if(++i < MAX)
    {
        p.i++;
        p.j = 0;
        j = 0;
        return &p;
    }
    else
    {
        return NULL;
    }
}

int main()
{
    while(1)
    {
        Pair *p = generate_pairs();
        if(p != NULL)
        {
            //printf("%d,%d\n",p->i,p->j);
        }
        else
        {
            //printf("end");
            break;
        }
    }
    return 0;
}

Jest to prosty, niezorientowany obiektowo sposób naśladowania generatora. To działało zgodnie z oczekiwaniami.

Podobnie jak funkcja symuluje koncepcję stosu, tak generatory symulują koncepcję kolejki. Reszta to semantyka.

Na marginesie, zawsze można symulować kolejkę ze stosem, używając stosu operacji zamiast danych. W praktyce oznacza to, że można zaimplementować zachowanie podobne do kolejki, zwracając parę, której druga wartość ma następną funkcję do wywołania lub wskazuje, że nie mamy już żadnych wartości. Ale to jest bardziej ogólne niż to, co robi wydajność vs zwrot. Pozwala na symulację kolejki dowolnych wartości zamiast jednorodnych wartości, których oczekujesz od generatora, ale bez utrzymywania pełnej kolejki wewnętrznej.

Dokładniej, ponieważ C ++ nie ma naturalnej abstrakcji dla kolejki, musisz użyć konstrukcji, które wewnętrznie implementują kolejkę. Zatem odpowiedzią, która podała przykład z iteratorami, jest przyzwoita implementacja koncepcji.

W praktyce oznacza to, że możesz zaimplementować coś z funkcjonalnością kolejki bare-bones, jeśli chcesz tylko czegoś szybkiego, a następnie konsumujesz wartości kolejki tak, jak zużywałbyś wartości uzyskane z generatora.