Pregunta Patrón de generador equivalente de C ++ a Python


Tengo un ejemplo de código de Python que necesito imitar en C ++. No requiero ninguna solución específica (como las 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 secuencia básica, 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 semi-bloqueos, pero en fragmentos. En el siguiente ejemplo, first_pass usa la secuencia de pares para inicializar el buffer, y second_pass regenera el 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 yield con corutinas en 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 mantener una copia de la secuencia entre los pases.


74
2018-01-30 03:58


origen


Respuestas:


Los generadores existen en C ++, solo bajo otro nombre: Iteradores de entrada. Por ejemplo, leyendo de std::cin es similar a tener un generador de char.

Simplemente necesita comprender lo que hace un generador:

  • hay una masa de datos: las variables locales definen una estado
  • hay un método init
  • hay un "próximo" método
  • hay una manera de señalizar la terminación

En tu 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 :)


50
2018-01-30 07:34



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

A veces una corotine apilada se puede utilizar para implementar un iterador.

PD Ver también Este artículo que menciona tanto un switch piratear por Christopher M. Kohlhoff y Boost.Coroutine por Oliver Kowalke. El trabajo de Oliver Kowalke es un seguimiento en Boost.Coroutine por Giovanni P. Deretta.

PD Creo que también puedes escribir un tipo 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 el Mordor corutinas:

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

36
2017-10-04 21:08



Ya que Boost.Coroutine2 ahora lo soporta muy bien (lo encontré porque quería resolver exactamente lo mismo yield problema), estoy publicando el código de 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_sequence no toma argumentos adicionales. Si es necesario, std::bind o una lambda debería usarse para generar un objeto de función que toma solo un argumento (de push_type), cuando se pasa al coro_t::pull_typeconstructor.


15
2017-08-06 08:51



Probablemente debería verificar los generadores en std :: experimental en Visual Studio 2015, por ejemplo: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Creo que es exactamente lo que estás buscando. Los generadores generales deberían estar disponibles en C ++ 17 ya que esta es solo una característica experimental de Microsoft VC.


3
2018-02-08 05:30



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 generaría el generador, actualizando el estado interno a medida que lo hace.

Esto es básicamente similar a cómo se implementan los generadores Python, creo. La principal diferencia es que pueden recordar una compensación en el bytecode 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, debería calcular el siguiente valor del anterior. En el caso de su pair_sequenceeso 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 "como un puntero", y NULL no debe ser un valor válido y legible, podría usar un puntero NULL como indicador de finalización. De lo contrario, necesita una señal fuera de banda.


2
2018-01-30 04:43



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 una transmisión y asegurarse de que se adapte a istream_iterator, por ejemplo.


1
2017-07-03 00:17



Todas las respuestas que implican escribir su propio iterador son completamente incorrectas. Esas respuestas se pierden por completo en el caso de los generadores de Python (una de las características más importantes y exclusivas del lenguaje). Lo más importante acerca de los generadores es que la ejecución continúa donde lo dejó. Esto no sucede con los iteradores. En su lugar, debe almacenar manualmente la información de estado de modo que cuando el operador ++ o el operador * se llame de nuevo, la información correcta esté en su lugar Al principio de la próxima llamada de función. Es por eso que escribir tu 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 Python en C ++ nativo, al menos no todavía (hay un rummor que el rendimiento aterrizará en C ++ 17) Puedes obtener algo similar recurriendo a terceros (por ejemplo, la sugerencia de Yongwei's Boost) o haciendo tu propia versión.

Yo diría que lo más parecido en C ++ nativo son los hilos. Un hilo puede mantener un conjunto suspendido de variables locales, y puede continuar la ejecución donde lo dejó, muy parecido a los generadores, pero necesita tirar 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 las personas consideraría que se trata de 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 ser automatizados, pero necesitaría aún más infraestructura, que de nuevo, es probable que sea vista como "demasiado extravagante". De todos modos, las limpiezas que necesitas son:
    1. fuera-> cerrar ()
    2. generator.join ()
  3. Esto no le permite detener el generador. Podría hacer algunas modificaciones para agregar esa habilidad, pero agrega desorden al código. Nunca sería tan limpio como el enunciado de rendimiento de Python.
  4. Además de 2, hay otros bits de repetitivo que se necesitan cada vez que quiere "crear instancias" de un objeto generador:
    1. Parámetro Channel * out
    2. Variables adicionales en principal: pares, generador

1
2018-01-01 00:09



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

Como nota al margen, siempre puedes simular una cola con una pila usando una pila de operaciones en lugar de datos. Lo que significa prácticamente es que puede implementar un comportamiento similar a una cola devolviendo un par, cuyo segundo valor tiene la siguiente función para llamar o indica que no tenemos valores. Pero esto es más general que lo que rinde vs retorno. Permite simular una cola de cualquier valor en lugar de los 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 usar 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 prácticamente es que puede implementar algo con la funcionalidad básica de la cola si solo quiere algo rápido y luego consume los valores de la cola del mismo modo que consumiría los valores obtenidos de un generador.


0
2018-01-01 02:16



Algo como esta:

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


0
2018-05-09 02:20



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

0
2017-07-26 19:14