태그 보관물: coroutine

coroutine

Python 생성기 패턴에 해당하는 C ++

C ++에서 모방해야하는 Python 코드의 예가 있습니다. 특정 솔루션 (예 : co-routine 기반 yield 솔루션은 허용 가능한 답변이기는하지만)이 필요하지 않습니다. 단순히 어떤 방식 으로든 의미를 재현하면됩니다.

파이썬

이것은 구체화 된 버전을 저장하기에 너무 큰 기본 시퀀스 생성기입니다.

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

목표는 위의 시퀀스의 두 인스턴스를 유지하고 반 잠금 단계로 반복하지만 청크 단위로 반복하는 것입니다. 아래 예에서는 first_pass쌍의 시퀀스를 사용하여 버퍼를 초기화 second_pass하고 동일한 정확한 시퀀스를 재생성 하고 버퍼를 다시 처리합니다.

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

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

C ++

C ++에서 해결책을 찾을 수있는 유일한 방법은 yieldC ++ 코 루틴 을 모방 하는 것입니다.하지만이 작업을 수행하는 방법에 대한 좋은 참조를 찾지 못했습니다. 이 문제에 대한 대체 (일반적이지 않은) 솔루션에도 관심이 있습니다. 패스 사이에 시퀀스 사본을 보관할 메모리 예산이 충분하지 않습니다.



답변

생성기는 C ++에 다른 이름 인 Input Iterators 바로 아래에 있습니다. 예를 들어,에서 읽는 std::cin것은 char.

생성기가 수행하는 작업을 이해하기 만하면됩니다.

  • 데이터 덩어리가 있습니다. 지역 변수는 상태를 정의합니다.
  • 초기화 방법이 있습니다
  • “다음”방법이 있습니다
  • 종료 신호를 보내는 방법이 있습니다.

사소한 예에서는 충분히 쉽습니다. 개념적으로 :

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

물론, 우리는 이것을 적절한 클래스로 래핑합니다.

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

그래서 흥얼 거려 … C ++가 좀 더 장황 할 수 있습니다. 🙂


답변

C ++에는 반복기가 있지만 반복기를 구현하는 것은 간단하지 않습니다. 반복기 개념 을 참조하고 이를 구현하기 위해 새 반복기 클래스를 신중하게 디자인해야합니다. 고맙게도 Boost에는 반복기 및 반복기 호환 생성기를 구현하는 데 도움 이되는 iterator_facade 템플릿이 있습니다.

때때로 스택리스 코 루틴을 사용하여 반복자를 구현할 수 있습니다 .

PS Christopher M. Kohlhoff 의 해킹과 Oliver Kowalke의 Boost.Coroutine 을 모두 언급하는 이 기사 를 참조하십시오 . 올리버 Kowalke의 작품은 후속작 인Boost.Coroutine 조반니 P. Deretta에 의해.switch

추신 : 람다 로 일종의 생성기 작성할 수도 있다고 생각합니다 .

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;

또는 펑터로 :

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 다음은 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;
}


답변

이후 Boost.Coroutine2는 지금 매우 잘 지원 (I 정확히 같은 해결 싶었 기 때문에 나는 그것을 발견 yield원래의 의도와 일치, 나는 C를 게시하고 ++ 코드 문제를)

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

이 예에서는 pair_sequence추가 인수를 사용하지 않습니다. 필요한 경우 std::bind또는 람다를 사용 push_type하여 coro_t::pull_type생성자에 전달 될 때 하나의 인수 (of ) 만받는 함수 개체를 생성해야합니다 .


답변

자신의 반복자를 작성하는 것과 관련된 모든 답변은 완전히 잘못되었습니다. 이러한 답변은 Python 생성기 (언어의 가장 크고 독특한 기능 중 하나)의 요점을 완전히 놓칩니다. 제너레이터에서 가장 중요한 점은 실행이 중단 된 부분에서 시작된다는 것입니다. 이것은 반복자에게는 발생하지 않습니다. 대신 operator ++ 또는 operator *가 새로 호출 될 때 올바른 정보가 다음 함수 호출 의 맨 처음 에 제자리 에 있도록 상태 정보를 수동으로 저장해야합니다 . 이것이 바로 C ++ 반복자를 직접 작성하는 것이 엄청난 고통 인 이유입니다. 반면 생성기는 우아하고 읽기와 쓰기가 쉽습니다.

적어도 아직까지는 네이티브 C ++에서 Python 생성기에 대한 좋은 아날로그가 있다고 생각하지 않습니다 ( 수익률이 C ++ 17에 도달 할 것이라는 소문이 있습니다 ). 타사 (예 : Yongwei의 Boost 제안)에 의존하거나 직접 롤링하여 유사한 것을 얻을 수 있습니다.

네이티브 C ++에서 가장 가까운 것은 스레드라고 말할 수 있습니다. 스레드는 일시 중단 된 로컬 변수 집합을 유지할 수 있으며 생성기와 매우 유사하게 중단 된 위치에서 실행을 계속할 수 있지만 생성기 개체와 호출자 간의 통신을 지원하려면 약간의 추가 인프라를 롤링해야합니다. 예

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

이 솔루션에는 몇 가지 단점이 있습니다.

  1. 스레드는 “비싸다”. 대부분의 사람들은 특히 생성기가 너무 단순 할 때 스레드를 “과도한”사용으로 간주합니다.
  2. 기억해야 할 몇 가지 정리 작업이 있습니다. 이는 자동화 될 수 있지만 더 많은 인프라가 필요합니다. 다시 말하면 “너무 사치스러운”것으로 보일 수 있습니다. 어쨌든, 필요한 정리는 다음과 같습니다.
    1. out-> close ()
    2. generator.join ()
  3. 이로 인해 발전기를 중지 할 수 없습니다. 이 기능을 추가하기 위해 약간의 수정을 가할 수 있지만 코드가 복잡해집니다. 파이썬의 yield 문만큼 깨끗하지 않을 것입니다.
  4. 2 외에도 생성기 객체를 “인스턴스화”하려고 할 때마다 필요한 상용구의 다른 비트가 있습니다.
    1. 채널 * 출력 매개 변수
    2. 메인의 추가 변수 : 쌍, 생성기

답변

Visual Studio 2015의 std :: experimental에서 생성기를 확인해야합니다. 예 : https://blogs.msdn.microsoft.com/vcblog/2014/11/12/resumable-functions-in-c/

정확히 당신이 찾고있는 것이라고 생각합니다. 전체 생성기는 실험적인 Microsoft VC 기능 일 뿐이므로 C ++ 17에서 사용할 수 있습니다.


답변

비교적 적은 수의 특정 생성기에 대해서만이 작업을 수행해야하는 경우 각 생성기를 클래스로 구현할 수 있습니다. 여기서 멤버 데이터는 Python 생성기 함수의 로컬 변수와 동일합니다. 그런 다음 생성기가 생성 할 다음 항목을 반환하는 다음 함수를 사용하여 내부 상태를 업데이트합니다.

이것은 기본적으로 Python 생성기가 구현되는 방식과 유사합니다. 가장 큰 차이점은 생성기가 “내부 상태”의 일부로 생성기 함수의 바이트 코드에 대한 오프셋을 기억할 수 있다는 것입니다. 이는 생성기가 수율을 포함하는 루프로 작성 될 수 있음을 의미합니다. 대신 이전 값에서 다음 값을 계산해야합니다. 귀하의 경우 pair_sequence, 그것은 매우 사소합니다. 복잡한 발전기가 아닐 수도 있습니다.

또한 종료를 나타내는 방법이 필요합니다. 반환하는 것이 “포인터와 유사”하고 NULL이 유효한 양보 가능한 값이 아니어야하는 경우 NULL 포인터를 종료 표시기로 사용할 수 있습니다. 그렇지 않으면 대역 외 신호가 필요합니다.


답변

이와 같은 것은 매우 유사합니다.

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

operator ()를 사용하는 것은이 생성기로 무엇을 하려는지에 대한 질문 일뿐입니다. 예를 들어 스트림으로 빌드하고 istream_iterator에 적응하는지 확인할 수도 있습니다.