Padrão de gerador equivalente de C ++ para Python

Eu tenho alguns exemplos de código Python que preciso imitar em C ++. Não preciso de nenhuma solução específica (como soluções de rendimento baseadas em co-rotina, embora também sejam respostas aceitáveis), simplesmente preciso reproduzir a semântica de alguma maneira.

Pitão

Este é um gerador de sequência básico, claramente grande demais para armazenar uma versão materializada.

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

O objetivo é manter duas instâncias da sequência acima e iterar sobre elas em semi-lockstep, mas em blocos. No exemplo abaixo, o first_passusa a sequência de pares para inicializar o buffer e second_passregenera a mesma sequência exata e processa o buffer novamente.

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

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

C ++

A única coisa que posso encontrar para uma solução em C ++ é imitar yieldcom co-rotinas C ++, mas não encontrei nenhuma boa referência sobre como fazer isso. Também estou interessado em soluções alternativas (não gerais) para este problema. Não tenho orçamento de memória suficiente para manter uma cópia da sequência entre as passagens.

Existem geradores em C ++, apenas com outro nome: Iteradores de entrada . Por exemplo, ler de std::ciné semelhante a ter um gerador de char.

Você simplesmente precisa entender o que um gerador faz:

• há um blob de dados: as variáveis ​​locais definem um estado
• existe um método init
• existe um método "próximo"
• existe uma maneira de sinalizar o encerramento

Em seu exemplo trivial, é bastante fácil. Conceitualmente:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Claro, nós envolvemos isso como uma classe adequada:

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

Então, hum sim ... pode ser que C ++ seja um pouco mais prolixo :)

Em C ++ existem iteradores, mas implementar um iterador não é simples: é preciso consultar os conceitos do iterador e projetar cuidadosamente a nova classe do iterador para implementá-los. Felizmente, Boost tem um modelo iterator_facade que deve ajudar a implementar os iteradores e geradores compatíveis com iteradores.

Às vezes, uma co-rotina sem pilha pode ser usada para implementar um iterador .

PS Veja também este artigo que menciona um switchhack de Christopher M. Kohlhoff e Boost.Coroutine de Oliver Kowalke. O trabalho de Oliver Kowalke é uma continuação do Boost.Coroutine de Giovanni P. Deretta.

PS Acho que você também pode escrever uma espécie de gerador com lambdas :

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;

Ou com um functor:

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 Aqui está um gerador implementado com as corrotinas Mordor :

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

Como Boost.Coroutine2 agora o suporta muito bem (eu o encontrei porque queria resolver exatamente o mesmo yieldproblema), estou postando o código C ++ que corresponde à sua intenção original:

#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();
    //}
}

Neste exemplo, pair_sequencenão aceita argumentos adicionais. Se for necessário, std::bindou um lambda deve ser usado para gerar um objeto de função que leva apenas um argumento (de push_type), quando é passado para o coro_t::pull_typeconstrutor.

Todas as respostas que envolvem escrever seu próprio iterador estão completamente erradas. Essas respostas perdem totalmente o objetivo dos geradores Python (um dos maiores e únicos recursos da linguagem). O mais importante sobre geradores é que a execução continua de onde parou. Isso não acontece com iteradores. Em vez disso, você deve armazenar manualmente as informações de estado de forma que, quando o operador ++ ou o operador * for chamado novamente, as informações corretas estarão disponíveis no início da próxima chamada de função. É por isso que escrever seu próprio iterador C ++ é uma dor gigantesca; enquanto os geradores são elegantes e fáceis de ler e escrever.

Não acho que exista um bom análogo para geradores Python em C ++ nativo, pelo menos não ainda (há rumores de que o rendimento cairá em C ++ 17 ). Você pode obter algo semelhante recorrendo a terceiros (por exemplo, a sugestão de Boost de Yongwei) ou fazendo o seu próprio.

Eu diria que a coisa mais próxima em C ++ nativo são threads. Um thread pode manter um conjunto suspenso de variáveis ​​locais e pode continuar a execução de onde parou, muito parecido com os geradores, mas você precisa lançar um pouco de infraestrutura adicional para suportar a comunicação entre o objeto gerador e seu chamador. Por exemplo

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

No entanto, esta solução tem várias desvantagens:

1. Tópicos são "caros". A maioria das pessoas consideraria isso um uso "extravagante" de fios, especialmente quando seu gerador é tão simples.
2. Existem algumas ações de limpeza que você precisa lembrar. Eles poderiam ser automatizados, mas você precisaria de ainda mais infraestrutura, o que, novamente, pode ser visto como "muito extravagante". De qualquer forma, as limpezas de que você precisa são:
   1. out-> close ()
   2. generator.join ()
3. Isso não permite que você pare o gerador. Você pode fazer algumas modificações para adicionar essa capacidade, mas isso adiciona confusão ao código. Nunca seria tão claro quanto a declaração de rendimento do Python.
4. Além de 2, existem outros bits de texto clichê que são necessários cada vez que você deseja "instanciar" um objeto gerador:
   1. Parâmetro de saída de canal *
   2. Variáveis ​​adicionais em principal: pares, gerador

Você provavelmente deve verificar os geradores em std :: experimental no Visual Studio 2015, por exemplo: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Acho que é exatamente o que você está procurando. Geradores gerais devem estar disponíveis em C ++ 17, pois este é apenas um recurso experimental do Microsoft VC.

Se você só precisa fazer isso para um número relativamente pequeno de geradores específicos, você pode implementar cada um como uma classe, onde os dados do membro são equivalentes às variáveis ​​locais da função do gerador Python. Então você tem uma próxima função que retorna a próxima coisa que o gerador produziria, atualizando o estado interno enquanto o faz.

Isso é basicamente semelhante a como os geradores Python são implementados, eu acredito. A principal diferença é que eles podem se lembrar de um deslocamento no bytecode da função do gerador como parte do "estado interno", o que significa que os geradores podem ser escritos como loops contendo rendimentos. Em vez disso, você teria que calcular o próximo valor do anterior. No caso do seu pair_sequence, isso é bastante trivial. Pode não ser para geradores complexos.

Você também precisa de alguma forma de indicar a rescisão. Se o que você está retornando é "semelhante a um ponteiro", e NULL não deve ser um valor rendível válido, você pode usar um ponteiro NULL como um indicador de finalização. Caso contrário, você precisa de um sinal fora de banda.

Algo assim é muito semelhante:

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

Usar o operator () é apenas uma questão de o que você deseja fazer com este gerador, você também pode construí-lo como um fluxo e certificar-se de que ele se adapta a um istream_iterator, por exemplo.

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

Algo como este :

Exemplo de uso:

using ull = unsigned long long;

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

    return 0;
}

Irá imprimir os números de 0 a 99

Bem, hoje eu também estava procurando uma implementação de coleção fácil em C ++ 11. Na verdade, fiquei desapontado, porque tudo o que encontrei está muito longe de coisas como geradores de python ou operador de rendimento C # ... ou muito complicado.

O objetivo é fazer coleta que irá emitir seus itens apenas quando for necessário.

Eu queria que fosse assim:

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

Achei este post, a melhor resposta IMHO foi sobre boost.coroutine2, de Yongwei Wu . Por ser o mais próximo do que o autor queria.

Vale a pena aprender as rotinas de reforço. E talvez o faça nos fins de semana. Mas até agora estou usando minha implementação muito pequena. Espero que ajude outra pessoa.

Abaixo está um exemplo de uso e implementação.

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

Esta resposta funciona em C (e, portanto, acho que também funciona em 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;
}

Esta é uma maneira simples e não orientada a objetos de imitar um gerador. Isso funcionou conforme o esperado para mim.

Assim como uma função simula o conceito de pilha, os geradores simulam o conceito de fila. O resto é semântica.

Como uma observação lateral, você sempre pode simular uma fila com uma pilha usando uma pilha de operações em vez de dados. O que isso significa na prática é que você pode implementar um comportamento semelhante ao de fila, retornando um par, cujo segundo valor tem a próxima função a ser chamada ou indica que estamos sem valores. Mas isso é mais geral do que o rendimento versus retorno. Ele permite simular uma fila de quaisquer valores ao invés de valores homogêneos que você espera de um gerador, mas sem manter uma fila interna cheia.

Mais especificamente, como o C ++ não tem uma abstração natural para uma fila, você precisa usar construções que implementam uma fila internamente. Portanto, a resposta que deu o exemplo com iteradores é uma implementação decente do conceito.

O que isso significa na prática é que você pode implementar algo com funcionalidade de fila básica se quiser apenas algo rápido e, em seguida, consumir os valores da fila da mesma forma que consumiria os valores produzidos por um gerador.