2

速度を上げるために、この Python コードを変換する必要があります。r と n は、ユーザー定義の整数変数です。

この関数は、次の基準ですべてのリストを生成することになっています。

listSum = n、長さ = r、値 (置換あり) は [0,1,2,...,n] にあります

def recurse(r,n):
    if r == 1:
        yield [n]
        return
    for i in range(n+1):
        for j in recurse(r-1,n-i):
            yield [i]+j

静的変数を使用してみましたが、間違った時間にインクリメントしています。必要な変数 (r、n、および i) をメイン関数から変更して、それらをジェネレーターの同等の関数に渡そうとしましたが、この解決策は、r と n の異なる初期値で機能するようには見えません。Boost がインストールされていないシステムで作業していますが、Boost をインストールするためのシステム権限がありません。では、再帰的な python リスト ジェネレーターを C++ に変換するにはどうすればよいでしょうか。

を反復するrecurse(r=3, n=4)と、次のようになります。

[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]
4

2 に答える 2

2

まず、アルゴリズムの詳細については、このスレッドを確認してください。生成するリストの数が (n+r-1)C(r-1) であることがわかります。これが役立つ場合があります。このコードを翻訳する方法は複数ありますが、ここでは 2 つ紹介します。

反復的な方法

まず、C++ では、ジェネレーター パターンはあまり一般的ではありません。何をしたいかにもよりますが、ほとんどの場合、最初にこのすべての出力に実際にメモリを割り当て、日付を計算してから、完全な行列を返します。第 2 に、C++ ではこのように再帰することはできません。スタックをすぐに台無しにしてしまいます。したがって、アルゴリズムの反復バージョンが必要です。これを行う方法は次のとおりです（C++で好きなイテレータを使用）。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/math/special_functions/binomial.hpp>
#include <boost/numeric/conversion/cast.hpp>

using namespace std;

vector<vector<size_t>> gen_matrix(unsigned int n, unsigned int r)
{
    vector<vector<size_t>> res;
    if(r < 1) return res;
    // reserve memory space
    // this will throw positive_overflow if size is too big to be represented as size_t
    // this can also throw out_of_memory if this is size_t-representable but memory is too small.
    double result_size = boost::math::binomial_coefficient<double>(n + r - 1, r - 1);
    res.reserve(boost::numeric_cast<size_t>(result_size));
    vector<size_t> current(r, 0);
    current.front() = n;
    res.push_back(current);
    vector<size_t>::iterator inc = next(current.begin()); // what we increment
    while(inc != current.end())
    {
        while(current.front() != 0)
        {
            (*inc)++;
            current.front()--;
            res.push_back(current);
            while(prev(inc) != current.begin())
                inc--;
        }
        swap(current.front(), *inc++);
    }
    return move(res);
}

int main()
{
    auto r = gen_matrix(6, 4);
    for(auto v : r)
    {
        copy(v.begin(), v.end(), ostream_iterator<int>(cout, ", "));
        cout << endl;
    }
}

注： C++コンテナを使用する場合、この方法ははるかに自然であるため（コンテナend()とのイテレータ比較のため）、生成はあなたの例と比較して逆に行われます。また、ブースト部分は、サイズを事前に計算し、早い段階で例外をスローしてメモリの枯渇を回避するために使用されます (および再割り当てを回避するためにメモリを予約します)。これは必須ではありません。この部分をコメントアウトすることもできます (自己責任で ^^)。

ジェネレーターの方法

しかし、Peta ディスクに保存された大きなファイルに整数リストのテラオクテットを書き込むプログラムをコーディングしている場合のように、ジェネレータが必要になる場合があります (よくわかりません)。または、n=100、r=80 で計算し、200 万または 300 万のベクトルをスキップして、それらの束を選択できるようにしたい場合があります。または、大量のメモリ使用を避けたいだけです。とにかく、ジェネレーターが役に立つかもしれません。ここにあります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <stdexcept>
#include <boost/math/special_functions/binomial.hpp>
#include <boost/numeric/conversion/cast.hpp>


struct sum_list_generator
{
    typedef vector<unsigned int> result_type;

    sum_list_generator(unsigned int n, unsigned int r):
        current(r, 0),
        inc(current.begin())
    {
        if(inc != current.end()) *inc++ = n;
    }

    result_type operator()()
    {
        if(inc == current.end())
            throw out_of_range("end of iteration");
        result_type res = current;
        if(current.front() == 0)
            swap(current.front(), *inc++);
        if(inc != current.end())
        {
            (*inc)++;
            current.front()--;
            if(current.front() != 0)
                while(prev(inc) != current.begin())
                    inc--;
        }
        return move(res);
    }

    // helper function : number of outputed vectors
    static size_t count(unsigned int n, unsigned int r)
    {
        return boost::numeric_cast<size_t>(
            boost::math::binomial_coefficient<double>(n + r - 1, r - 1)
            );
    }

    private:
        result_type current;
        result_type::iterator inc;
};

int main()
{
    sum_list_generator g(6, 4);
    try
    {
        while(true)
        {
            auto v = g();
            copy(v.begin(), v.end(), ostream_iterator<int>(cout, ", "));
            cout << endl;
        }
    }
    catch(out_of_range const&) {}
}

注:繰り返しますが、count メンバー関数は消去できます。また、通常、C++ では (Python とは対照的に) 予想される実行パスで例外をスローすることを避けます。ここで、ジェネレーターを使用して他の構造を埋めることができます。パラメーターが適切に選択されていれば、スローされません。使いすぎると当然アウトオブレンジ。最終的に、ここのメインのように例外をキャッチして黙らせるのは非常に悪い設計です。これは(100, 80) のような楽しいパラメータを試すために使用できる単なる例です。このcount()関数は、ベクトルの完全なリストが必要な場合に正確な境界を提供します: それを使用してください。

于 2013-07-02T23:59:58.623 に答える
0

多くの場合、コールバック関数は反復子としてうまく機能します。

#include <functional>
#include <iostream>

// manipulates the memory at `dest`, and calls `doNext()` each time it contains a new set of data
void recurseHelper(int r, int n, std::function<void()> doNext, int* dest) {    
    if(r == 1) {
        *dest = n;
        doNext();
    }
    else for(int i = 0; i <= n; i++) {
        *dest = i; 
        recurseHelper(r-1, n-i, doNext, dest + 1);
    }
}

void recurse(int r, int n, std::function<void(int*)> f) {
    int dest[r];
    recurseHelper(r, n, [&] () {
        f(dest);
    }, dest);
}

int main() {
    recurse(3, 4, [] (int* i) {
        std::cout << i[0] << i[1] << i[2] << std::endl;
    });
    return 0;
}
于 2013-07-02T21:58:04.213 に答える