Pola generator C ++ ke Python yang setara

Saya punya beberapa contoh kode Python yang perlu saya tiru di C ++. Saya tidak memerlukan solusi khusus apa pun (seperti solusi hasil berbasis rutin bersama, meskipun itu akan menjadi jawaban yang dapat diterima juga), saya hanya perlu mereproduksi semantik dengan beberapa cara.

Python

Ini adalah generator urutan dasar, yang jelas terlalu besar untuk menyimpan versi material.

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

Tujuannya adalah untuk mempertahankan dua contoh dari urutan di atas, dan mengulanginya dalam semi-lockstep, tetapi dalam potongan. Pada contoh di bawah ini first_passmenggunakan urutan pasangan untuk menginisialisasi buffer, dan second_passmeregenerasi urutan yang sama persis dan memproses buffer lagi.

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

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

C ++

Satu-satunya hal yang dapat saya temukan untuk solusi di C ++ adalah meniru yielddengan C ++ coroutines, tetapi saya belum menemukan referensi yang bagus tentang cara melakukan ini. Saya juga tertarik dengan solusi alternatif (non umum) untuk masalah ini. Saya tidak memiliki cukup anggaran memori untuk menyimpan salinan urutan di antara gerakan printhead.

Generator ada di C ++, tepat di bawah nama lain: Input Iterators . Misalnya, membaca dari std::cinmirip dengan memiliki generator char.

Anda hanya perlu memahami apa yang dilakukan generator:

• ada gumpalan data: variabel lokal menentukan status
• ada metode init
• ada metode "selanjutnya"
• ada cara untuk memberi sinyal penghentian

Dalam contoh sepele Anda, itu cukup mudah. Secara konseptual:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Tentu saja, kami membungkus ini sebagai kelas yang tepat:

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

So hum yeah ... mungkin C ++ sedikit lebih bertele-tele :)

Di C ++ ada iterator, tetapi mengimplementasikan iterator tidaklah mudah: kita harus berkonsultasi dengan konsep iterator dan dengan hati-hati merancang kelas iterator baru untuk mengimplementasikannya. Untungnya, Boost memiliki template iterator_facade yang akan membantu mengimplementasikan iterator dan generator yang kompatibel dengan iterator.

Terkadang coroutine tanpa tumpukan dapat digunakan untuk mengimplementasikan iterator .

PS Lihat juga artikel ini yang menyebutkan switchperetasan oleh Christopher M. Kohlhoff dan Boost.Coroutine oleh Oliver Kowalke. Karya Oliver Kowalke adalah tindak lanjut dari Boost.Coroutine oleh Giovanni P. Deretta.

PS Saya pikir Anda juga dapat menulis semacam generator dengan lambda :

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;

Atau dengan 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 Berikut adalah generator yang diimplementasikan dengan coroutines 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;
}

Sejak Boost.Coroutine2 sekarang mendukungnya dengan sangat baik (saya menemukannya karena saya ingin menyelesaikan masalah yang persis sama yield), saya memposting kode C ++ yang sesuai dengan niat asli Anda:

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

Dalam contoh ini, pair_sequencetidak mengambil argumen tambahan. Jika perlu, std::bindatau lambda harus digunakan untuk menghasilkan objek fungsi yang hanya membutuhkan satu argumen push_type, ketika diteruskan ke coro_t::pull_typekonstruktor.

Semua jawaban yang melibatkan penulisan iterator Anda sendiri sepenuhnya salah. Jawaban seperti itu sepenuhnya kehilangan inti dari generator Python (salah satu fitur bahasa terbesar dan unik). Hal yang paling penting tentang generator adalah eksekusi melanjutkan dari bagian yang ditinggalkannya. Ini tidak terjadi pada iterator. Sebagai gantinya, Anda harus menyimpan informasi status secara manual sedemikian rupa sehingga ketika operator ++ atau operator * dipanggil lagi, informasi yang benar sudah ada di awal. pemanggilan fungsi berikutnya. Inilah sebabnya mengapa menulis iterator C ++ Anda sendiri sangat merepotkan; padahal, generator itu elegan, dan mudah dibaca + ditulis.

Saya tidak berpikir ada analog yang baik untuk generator Python di C ++ asli, setidaknya belum (ada rumor bahwa hasil akan mendarat di C ++ 17 ). Anda bisa mendapatkan sesuatu yang serupa dengan menggunakan pihak ketiga (misalnya saran Peningkatan Yongwei), atau menggulirkan milik Anda sendiri.

Saya akan mengatakan hal terdekat dalam bahasa asli C ++ adalah utas. Sebuah utas dapat mempertahankan sekumpulan variabel lokal yang ditangguhkan, dan dapat melanjutkan eksekusi di tempat yang ditinggalkannya, sangat mirip dengan generator, tetapi Anda perlu menggulung sedikit infrastruktur tambahan untuk mendukung komunikasi antara objek generator dan pemanggilnya. Misalnya

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

Solusi ini memiliki beberapa kelemahan:

1. Benang itu "mahal". Kebanyakan orang akan menganggap ini sebagai penggunaan utas yang "boros", terutama jika generator Anda sangat sederhana.
2. Ada beberapa tindakan pembersihan yang perlu Anda ingat. Ini dapat dilakukan secara otomatis, tetapi Anda akan membutuhkan lebih banyak infrastruktur, yang sekali lagi, kemungkinan akan dilihat sebagai "terlalu boros". Pokoknya, pembersihan yang Anda butuhkan adalah:
   1. keluar-> tutup ()
   2. generator.join ()
3. Ini tidak memungkinkan Anda untuk menghentikan generator. Anda dapat membuat beberapa modifikasi untuk menambahkan kemampuan itu, tetapi itu menambah kekacauan pada kode. Itu tidak akan pernah sebersih pernyataan hasil Python.
4. Selain 2, ada bit boilerplate lain yang diperlukan setiap kali Anda ingin "membuat instance" objek generator:
   1. Parameter saluran * keluar
   2. Variabel tambahan utama: pasangan, generator

Anda mungkin harus memeriksa generator di std :: eksperimental di Visual Studio 2015 misalnya: https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

Saya pikir itulah yang Anda cari. Generator keseluruhan harus tersedia dalam C ++ 17 karena ini hanya fitur Microsoft VC eksperimental.

Jika Anda hanya perlu melakukan ini untuk sejumlah kecil generator tertentu, Anda dapat mengimplementasikan masing-masing sebagai kelas, di mana data anggotanya setara dengan variabel lokal dari fungsi generator Python. Kemudian Anda memiliki fungsi berikutnya yang mengembalikan hal berikutnya yang akan dihasilkan generator, memperbarui status internal saat melakukannya.

Ini pada dasarnya mirip dengan bagaimana generator Python diimplementasikan, saya percaya. Perbedaan utamanya adalah mereka dapat mengingat offset ke dalam bytecode untuk fungsi generator sebagai bagian dari "status internal", yang berarti generator dapat ditulis sebagai loop yang berisi hasil. Anda harus menghitung nilai berikutnya dari sebelumnya. Dalam kasus Andapair_sequence , itu sangat sepele. Ini mungkin bukan untuk generator yang kompleks.

Anda juga membutuhkan cara untuk menunjukkan penghentian. Jika apa yang Anda kembalikan adalah "seperti penunjuk", dan NULL seharusnya bukan nilai hasil yang valid, Anda dapat menggunakan penunjuk NULL sebagai indikator penghentian. Jika tidak, Anda memerlukan sinyal out-of-band.

Sesuatu seperti ini sangat mirip:

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

Menggunakan operator () hanyalah pertanyaan tentang apa yang ingin Anda lakukan dengan generator ini, Anda juga dapat membuatnya sebagai aliran dan memastikannya menyesuaikan dengan istream_iterator, misalnya.

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

Sesuatu seperti ini :

Contoh penggunaan:

using ull = unsigned long long;

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

    return 0;
}

Akan mencetak angka dari 0 hingga 99

Nah, hari ini saya juga sedang mencari implementasi pengumpulan yang mudah di bawah C ++ 11. Sebenarnya saya kecewa, karena semua yang saya temukan terlalu jauh dari hal-hal seperti generator python, atau operator C # yield ... atau terlalu rumit.

Tujuannya adalah untuk membuat koleksi yang akan mengeluarkan itemnya hanya jika diperlukan.

Saya ingin menjadi seperti ini:

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

Saya menemukan posting ini, jawaban terbaik IMHO adalah tentang boost.coroutine2, oleh Yongwei Wu . Karena itu paling dekat dengan apa yang diinginkan penulis.

Layak untuk mempelajari kursus dorongan .. Dan saya mungkin akan melakukannya pada akhir pekan. Tapi sejauh ini saya menggunakan implementasi saya yang sangat kecil. Semoga bisa membantu orang lain.

Di bawah ini adalah contoh penggunaan, dan kemudian implementasi.

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

Jawaban ini berfungsi di C (dan karenanya saya pikir berfungsi di c ++ juga)

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

Ini adalah cara sederhana dan tidak berorientasi objek untuk meniru generator. Ini bekerja seperti yang diharapkan untuk saya.

Sama seperti fungsi yang mensimulasikan konsep tumpukan, generator mensimulasikan konsep antrian. Sisanya adalah semantik.

Sebagai catatan tambahan, Anda selalu dapat mensimulasikan antrian dengan tumpukan menggunakan tumpukan operasi alih-alih data. Apa artinya secara praktis adalah bahwa Anda dapat mengimplementasikan perilaku seperti antrian dengan mengembalikan pasangan, nilai keduanya memiliki fungsi selanjutnya untuk dipanggil atau menunjukkan bahwa kita kehabisan nilai. Tapi ini lebih umum daripada apa hasil vs pengembalian. Ini memungkinkan untuk mensimulasikan antrian nilai apa pun daripada nilai homogen yang Anda harapkan dari generator, tetapi tanpa menjaga antrian internal penuh.

Lebih khusus lagi, karena C ++ tidak memiliki abstraksi alami untuk antrian, Anda perlu menggunakan konstruksi yang mengimplementasikan antrian secara internal. Jadi jawaban yang memberi contoh dengan iterator adalah implementasi konsep yang layak.

Artinya secara praktis adalah bahwa Anda dapat mengimplementasikan sesuatu dengan fungsionalitas antrian tanpa tulang jika Anda hanya menginginkan sesuatu yang cepat dan kemudian menggunakan nilai antrian sama seperti Anda akan menggunakan nilai yang dihasilkan dari generator.