Patrón generador de C ++ equivalente a Python

117

Tengo un código de Python de ejemplo que necesito imitar en C ++. No necesito ninguna solución específica (como soluciones de rendimiento basadas en co-rutinas, aunque también serían respuestas aceptables), simplemente necesito reproducir la semántica de alguna manera.

Pitón

Este es un generador de secuencias básico, claramente demasiado grande para almacenar una versión materializada.

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

El objetivo es mantener dos instancias de la secuencia anterior e iterar sobre ellas en semicerrado, pero en partes. En el siguiente ejemplo, el first_passusa la secuencia de pares para inicializar el búfer, y second_passregenera la misma secuencia exacta y procesa el búfer nuevamente.

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

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

C ++

Lo único que puedo encontrar para una solución en C ++ es imitar yieldcon corrutinas de C ++, pero no he encontrado ninguna buena referencia sobre cómo hacer esto. También estoy interesado en soluciones alternativas (no generales) para este problema. No tengo suficiente presupuesto de memoria para guardar una copia de la secuencia entre pasadas.

Noah Watkins
fuente
Como puede ver desde aquí, stackoverflow.com/questions/3864410/… coroutine no es una buena idea para implementar. ¿No puedes hacerlo con lectura en búfer? stackoverflow.com/questions/4685862/…
batbaatar
Los iteradores de C ++ deberían admitir algo como esto.
Lalaland
Relacionado: ¿ Equivalente en C ++ de rendimiento en C #?
Bernhard Barker

Respuestas:

79

Los generadores existen en C ++, con otro nombre: Iteradores de entrada . Por ejemplo, leer de std::cines similar a tener un generador de char.

Simplemente necesita comprender lo que hace un generador:

  • hay una masa de datos: las variables locales definen un estado
  • hay un método de inicio
  • hay un método "siguiente"
  • hay una manera de señalar la terminación

En su ejemplo trivial, es bastante fácil. Conceptualmente:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Por supuesto, envolvemos esto como una clase adecuada:

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

Así que hum, sí ... podría ser que C ++ es un poco más detallado :)

Matthieu M.
fuente
2
Acepté su respuesta (¡gracias!) Porque es técnicamente correcta para la pregunta que hice. ¿Tiene algún consejo para las técnicas en los casos en que la secuencia que debe generarse es más compleja, o simplemente estoy ganando un caballo muerto aquí con C ++ y realmente las corrutinas son la única forma de generalidad?
Noah Watkins
3
@NoahWatkins: las corrutinas facilitan la implementación cuando los idiomas las admiten. Desafortunadamente, C ++ no lo hace, por lo que la iteración es más fácil. Si realmente necesita corrutinas, en realidad necesita un hilo en toda regla para mantener la "pila" de su llamada de función al lado. Definitivamente es exagerado abrir una lata de gusanos solo por eso en este ejemplo, pero su kilometraje puede variar según sus necesidades reales.
Matthieu M.
1
Una implementación de corrutina no basada en subprocesos está disponible en Boost boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/index.html con una propuesta de estandarización aquí: open-std.org/jtc1/sc22/ wg21 / docs / papers / 2014 / n3985.pdf
boycy
2
@boycy: En realidad, existen múltiples propuestas para las corrutinas, en particular una sin pila y la otra con pila llena. Es un hueso duro de roer, así que por ahora estoy esperando. Mientras tanto, sin embargo, las corrutinas sin pila se pueden implementar casi directamente como iteradores de entrada (solo, sin el azúcar).
Matthieu M.
3
Sin embargo, de manera similar, los iteradores no son lo mismo que los generadores.
Огњен Шобајић
52

En C ++ hay iteradores, pero implementar un iterador no es sencillo: hay que consultar los conceptos del iterador y diseñar cuidadosamente la nueva clase de iterador para implementarlos. Afortunadamente, Boost tiene una plantilla iterator_facade que debería ayudar a implementar los iteradores y los generadores compatibles con iteradores.

A veces, se puede usar una corrutina sin pila para implementar un iterador .

PD: Consulte también este artículo que menciona un switchtruco de Christopher M. Kohlhoff y Boost.Coroutine de Oliver Kowalke. El trabajo de Oliver Kowalke es una continuación de Boost.Coroutine de Giovanni P. Deretta.

PD Creo que también puedes escribir una especie de generador con 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;

O con un 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;

PD Aquí hay un generador implementado con las corrutinas de 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;
}
ArtemGr
fuente
22

Dado que Boost.Coroutine2 ahora lo admite muy bien (lo encontré porque quería resolver exactamente el mismo yieldproblema), estoy publicando el código C ++ que coincide con su intención 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();
    //}
}

En este ejemplo, pair_sequenceno toma argumentos adicionales. Si es necesario, std::bindo se debe usar una lambda para generar un objeto de función que toma solo un argumento (de push_type), cuando se pasa al coro_t::pull_typeconstructor.

Yongwei Wu
fuente
Tenga en cuenta que Coroutine2 requiere c ++ 11, por lo que Visual Studio 2013 es insuficiente, ya que solo se admite parcialmente.
Weston
5

Todas las respuestas que implican escribir su propio iterador son completamente incorrectas. Tales respuestas pierden por completo el sentido de los generadores de Python (una de las características más grandes y únicas del lenguaje). Lo más importante sobre los generadores es que la ejecución se reanuda donde se detuvo. Esto no les sucede a los iteradores. En su lugar, debe almacenar manualmente la información de estado de modo que cuando se llame de nuevo al operador ++ o al operador *, la información correcta esté en su lugar al comienzo de la siguiente llamada a la función. Es por eso que escribir su propio iterador de C ++ es un dolor gigantesco; mientras que los generadores son elegantes y fáciles de leer + escribir.

No creo que haya un buen análogo para los generadores de Python en C ++ nativo, al menos no todavía (hay un rummor de que el rendimiento aterrizará en C ++ 17 ). Puede obtener algo similar recurriendo a un tercero (por ejemplo, la sugerencia de Boost de Yongwei) o lanzando el suyo.

Yo diría que lo más parecido en C ++ nativo son los hilos. Un subproceso puede mantener un conjunto suspendido de variables locales y puede continuar la ejecución donde se detuvo, de manera muy similar a los generadores, pero necesita un poco de infraestructura adicional para admitir la comunicación entre el objeto generador y su llamador. P.ej

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

Sin embargo, esta solución tiene varias desventajas:

  1. Los hilos son "caros". La mayoría de la gente consideraría que esto es un uso "extravagante" de hilos, especialmente cuando su generador es tan simple.
  2. Hay un par de acciones de limpieza que debe recordar. Estos podrían automatizarse, pero necesitaría aún más infraestructura, lo que, nuevamente, es probable que se considere "demasiado extravagante". De todos modos, las limpiezas que necesitas son:
    1. fuera-> cerrar ()
    2. generator.join ()
  3. Esto no le permite detener el generador. Puede hacer algunas modificaciones para agregar esa capacidad, pero agrega desorden al código. Nunca sería tan limpio como la declaración de rendimiento de Python.
  4. Además de 2, hay otros bits repetitivos que se necesitan cada vez que desee "instanciar" un objeto generador:
    1. Parámetro de canal * de salida
    2. Variables adicionales en principal: pares, generador
allyourcode
fuente
Estás confundiendo sintaxis con funcionalidad. Algunas respuestas anteriores realmente permiten que C ++ retome la ejecución desde donde se quedó durante la última llamada. No es nada mágico. De hecho, Python se implementa en C, por lo que todo lo que es posible en Python es posible en C, aunque no tan conveniente.
Edy
@edy ¿No está ya abordado en el primer párrafo? No está afirmando que no se pueda crear una funcionalidad equivalente en C ++ convencional, solo que es "un dolor gigantesco".
Kaitain
@Kaitain La pregunta aquí no es si es una molestia hacer un generador en C ++, sino si existe un patrón para hacerlo. Sus afirmaciones de que el enfoque "pierde el punto", que "lo más parecido" son los hilos ... son simplemente engañosas. Es un dolor Uno podría leer las otras respuestas y decidir por sí mismo.
Edy
@edy ¿Pero esto no termina siendo un punto vacío, dado que todos los lenguajes Turing-complete son finalmente capaces de la misma funcionalidad? "Todo lo que es posible en X es posible en Y" está garantizado para todos esos lenguajes, pero eso no me parece una observación muy esclarecedora.
Kaitain
@Kaitain Precisamente porque todos los lenguajes completos de Turing supuestamente deberían tener la misma capacidad, la cuestión de cómo implementar una característica en otro idioma es legítima. Nada de lo que Python tiene no se puede lograr con otro lenguaje; la cuestión es la eficiencia y la facilidad de mantenimiento. En ambos aspectos, C ++ sería una buena (r) elección.
Edy
2

Si solo necesita hacer esto para un número relativamente pequeño de generadores específicos, puede implementar cada uno como una clase, donde los datos de los miembros son equivalentes a las variables locales de la función del generador de Python. Luego, tiene una función siguiente que devuelve lo siguiente que produciría el generador, actualizando el estado interno a medida que lo hace.

Esto es básicamente similar a cómo se implementan los generadores de Python, creo. La principal diferencia es que pueden recordar un desplazamiento en el código de bytes para la función del generador como parte del "estado interno", lo que significa que los generadores se pueden escribir como bucles que contienen rendimientos. En su lugar, tendría que calcular el siguiente valor del anterior. En el caso de usted pair_sequence, eso es bastante trivial. Puede que no sea para generadores complejos.

También necesita alguna forma de indicar la terminación. Si lo que está devolviendo es "similar a un puntero", y NULL no debería ser un valor válido válido, puede usar un puntero NULL como indicador de terminación. De lo contrario, necesita una señal fuera de banda.

Ben
fuente
1

Algo como esto es muy similar:

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 el operador () es solo una cuestión de lo que quiere hacer con este generador, también puede construirlo como un flujo y asegurarse de que se adapte a un istream_iterator, por ejemplo.

labio
fuente
1

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;
}
Ingeniero
fuente
0

Algo como esto :

Ejemplo de uso:

using ull = unsigned long long;

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

    return 0;
}

Imprimirá los números del 0 al 99

smac89
fuente
0

Bueno, hoy también estaba buscando una implementación de colección fácil en C ++ 11. En realidad, me decepcionó, porque todo lo que encontré está demasiado lejos de cosas como los generadores de python o el operador de rendimiento de C # ... o demasiado complicado.

El propósito es realizar una colección que emitirá sus ítems solo cuando sea requerido.

Quería que fuera así:

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

Encontré esta publicación, en mi humilde opinión, la mejor respuesta fue sobre boost.coroutine2, de Yongwei Wu . Ya que es lo más cercano a lo que quería el autor.

Vale la pena aprender couroutines de impulso .. Y quizás lo haga los fines de semana. Pero hasta ahora estoy usando mi implementación muy pequeña. Espero que ayude a alguien más.

A continuación se muestra un ejemplo de uso y luego implementación.

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;
};      
Stepan Dyatkovskiy
fuente
0

Esta respuesta funciona en C (y, por lo tanto, creo que también funciona en 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 es una forma sencilla, no orientada a objetos, de imitar un generador. Esto funcionó como se esperaba para mí.

Sourav Kannantha B
fuente
-1

Así como una función simula el concepto de pila, los generadores simulan el concepto de cola. El resto es semántica.

Como nota al margen, siempre puede simular una cola con una pila utilizando una pila de operaciones en lugar de datos. Lo que eso significa en la práctica es que puede implementar un comportamiento similar a una cola devolviendo un par, cuyo segundo valor tiene la siguiente función a llamar o indica que no tenemos valores. Pero esto es más general que lo que hace el rendimiento frente al rendimiento. Permite simular una cola de cualquier valor en lugar de valores homogéneos que espera de un generador, pero sin mantener una cola interna completa.

Más específicamente, dado que C ++ no tiene una abstracción natural para una cola, debe utilizar construcciones que implementen una cola internamente. Entonces, la respuesta que dio el ejemplo con iteradores es una implementación decente del concepto.

Lo que esto significa en la práctica es que puede implementar algo con la funcionalidad de cola básica si solo desea algo rápido y luego consumir los valores de la cola de la misma manera que consumiría los valores generados por un generador.

Dmitry Rubanovich
fuente