6

テンプレート引数パックを使用した C++11 の機能はconstexpr、私の意見では、かなり複雑な計算を実行するのに十分強力である必要があります。私が実際に応用できる可能性のある例の 1 つは、コンパイル時の n 番目の素数の計算です。

この計算を実装する方法を求めています。複数のソリューションが提案されている場合は、それらを比較してみると面白いかもしれません。

私のパフォーマンスの期待値を示すために、適切なデスクトップ ハードウェアで 1 秒未満のコンパイル時間で 512 番目の素数 (つまり 3671) を見つけることができるコードを期待します。

4

4 に答える 4

8

テンプレートをまったく使用せずに、可能な限り簡単な方法を実装しましたが、機能します。

constexpr bool isPrimeLoop(int i, int k) {
    return (k*k > i)?true:(i%k == 0)?false:isPrimeLoop(i, k + 1);
}

constexpr bool isPrime(int i) {
    return isPrimeLoop(i, 2);
}

constexpr int nextPrime(int k) {
    return isPrime(k)?k:nextPrime(k + 1);
}

constexpr int getPrimeLoop(int i, int k) {
// i - nr of primes to advance
// k - some starting prime
    return (i == 0)?k:getPrimeLoop(i - 1, nextPrime(k + 1));
}

constexpr int getPrime(int i) {
    return getPrimeLoop(i, 2);
}

static_assert(getPrime(511) == 3671, "computed incorrectly");

constexpr-depth を少し増やす必要がありますが、簡単に間に合います。

$ time g++ -c -std=c++11 vec.cpp -fconstexpr-depth=600

real    0m0.093s
user    0m0.080s
sys 0m0.008s

次のトリックは、getPrimeLoop再帰の深さを対数に減らすため、g++ はデフォルトの深さで (測定可能な時間のペナルティなしで) 完了することができます。

constexpr int getPrimeLoop(int i, int k) {
    return (i == 0)?k:
        (i % 2)?getPrimeLoop(i-1, nextPrime(k + 1)):
        getPrimeLoop(i/2, getPrimeLoop(i/2, k));
}
于 2013-03-16T21:50:08.383 に答える
5

あなたの 1 秒の目標が、警備員のいないハードウェアに届くとは思えません。ただし、次のメタプログラムはそれを大幅に閉じることができると思います。

#include <type_traits>

template<unsigned N>
using boolean = std::integral_constant<bool,N>;

template<unsigned N>
constexpr bool is_co_prime()
{
    return true;
};

template<unsigned N, unsigned D>
constexpr bool is_co_prime()
{
    return N % D != 0;
};

template<unsigned N, unsigned D0, unsigned D1, unsigned ...Di>
constexpr bool is_co_prime()
{
    typedef typename std::conditional<
        is_co_prime<N,D1>(),
        typename std::conditional<
            is_co_prime<N,Di...>(),
            boolean<is_co_prime<N,D0>()>,
            std::false_type
        >::type,
        std::false_type
    >::type type;
    return type::value;
};

template<unsigned N>
constexpr unsigned inc()
{
    return N == 2 ? 3 : N + 2;
}

template<unsigned Counter, unsigned Candidate, unsigned ...Primes>
struct nth_prime;

template<unsigned Candidate, unsigned Prime, unsigned ...Primes>
struct nth_prime<0,Candidate,Prime,Primes...>
{
    static const unsigned value = Prime;
};

template<unsigned Counter, unsigned Candidate = 2, unsigned ...Primes>
struct nth_prime
{
    typedef typename std::conditional<
        is_co_prime<Candidate,Primes...>(),
        nth_prime<Counter - 1,inc<Candidate>(),Candidate,Primes...>,
        nth_prime<Counter,inc<Candidate>(),Primes...>
    >::type type;
    static const unsigned value = type::value;
};

#include <iostream>

using namespace std;

int main()
{
    cout << nth_prime<512>::value << endl;
    return 0;
}

このメタプログラムをMyNthPrimeと呼び、あなたのメタプログラムをYourNthPrimeと呼びます。

あなたのハードウェアは私のものよりもはるかに重く、メモリも確かに多いようです。私は、Lenovo ThinkPad T420、4 コア i5、8 GB RAM、8 GB スワップ、Linux Mint 14、カーネル 3.5.0 を実行しています。3分かかると報告します。YourNthPrimeを構築します。コマンドで測定すると、time35 分かかります。YourNthPrimeをビルドします。アプリは実行されていませんが、ターミナルとシステム モニターは実行されています。

コンパイラは GCC 4.7.2 で、コマンドラインのオプションは次のとおりです。

-Wall -O0 -std=c++11 -ftemplate-depth=1200

その経過時間は次のように分類されます。

real    34m2.534s
user    3m40.414s
sys     0m33.450s

MyNthPrimeをビルドするのに 1.5 分かかります。

-Wall -O0 -std=c++11 -ftemplate-depth=2100

経過時間は次のように分類されます。

real    1m27.832s
user    1m22.205s
sys     0m2.612s

それ-ftemplate-depth=2100は転置のタイプミスではありません。これについては後ほど。

MyNthPrimeは、 YourNthPrimeよりも 23 倍高速ではありません。細分化されたタイミングは、MyNthPrimeが実際にはユーザー時間でYourNthPrimeの約 2.75 倍高速であることを示唆しています。しかし、彼らはまた、YourNthPrimeのビルドがリアルタイムで実際にファームを失ったことも示しています。その存在の無益な 9/10 のために何をしていたのでしょうか? もちろん交換です。

どちらのビルドも 45 秒以内に 8GB のシステム RAM の 95% を消費しましたが、MyNthPrimeはそこら辺を超え てスワップしませんでした。YourNthPrimeはスワップ スペースをピーク時に 3.9 GB まで消費し続け、そのずっと前にすべての CPU が居眠りしていました。

この点は、 MyNthPrime がYourNthPrime の 2 倍の料金を支払う必要が-ftemplate-depthあるという事実を考慮すると注目に値します。一般的な知恵では、浪費-ftemplate-depthはメタプログラムのビルド時間にとって破滅への道であるというものです。しかし、YourNthPrimeとMyNthPrimeのランオフはこれを裏付けるものではなく、まったく逆です。私が得た教訓は、再帰テンプレートをインスタンス化しなければならない深さは、必ずしも量の良い尺度ではないということです実行する必要があるテンプレートのインスタンス化の数であり、メモリ リソースにとって重要なのはその量です。

表面的には似ていませんが、MyNthPrimeとYourNthPrimeはどちらも素数生成のための試行分割アルゴリズムを実装しています。MyNthPrime は、再帰的なテンプレートのインスタンス化とそれらがむさぼり食うメモリを節約するためにかなり巧妙にコーディングされているという理由だけで、これほど高速です。

YourNthPrimeフィールド 計算用の 4 つの再帰テンプレート。すべて同じ再帰可変個引数リストを使用します。 MyNthPrimeフィールド 2: コンパイラに膨大な数のインスタンス化を半分ほど与えるだけです。

YourNthPrime (私が読んだように) は、手元にある素数の昇順で試行分割を行うことの潜在的な効率を認識しています。手持ちの素数が分割される候補数の 1/2 を超えると、確率は 0 になります。最初に最も可能性の高い約数にヒットし、迅速な評決と終了の見込みを最適化します。 しかし、この効率を利用する際の障害は、手元にある素数が、常に先頭に最大のものを持つ可変個引数テンプレート引数リストによって表されるという事実です。この障害を克服するために、 YourNthPrimeは再帰的な可変個引数テンプレート関数を展開lastArg<>()し、手元の素数が分割で消費される順序を効果的に逆にします。

lastArg<>()手元の素数をテンプレート関数に提示します。

template<unsigned i, unsigned head, unsigned... tail>
constexpr bool isPrime() {
    return i % head && isPrime<i, tail...>();
}

i 素数 による次の候補の再帰試行分割の昇順head, tail...。それはここにあると思いますが、あなたがlastArg<>() その代償を払うことをhead期待していると思います&&.

しかし、これlastArg<>()自体を達成するには、呼び出しのたびに手元にある素数のリスト全体を再帰的にトラバースしますi。したがってisPrime<>() 、手元にある素数を必要なだけトラバースさせ、その過程でテストを行い、すべての再帰的なインスタンス化をi省いて保存する方が安上がりです。lastArg<>()

YourNthPrimeisPrime<>()で行われる仕事- 再帰的なトライアル部門 - は、MyNthPrimeで次のように行われます。

template<unsigned N, unsigned D0, unsigned D1, unsigned ...Di>
constexpr bool is_co_prime()
{
    typedef typename std::conditional<
        is_co_prime<N,D1>(),
        typename std::conditional<
            is_co_prime<N,Di...>(),
            boolean<is_co_prime<N,D0>()>,
            std::false_type
        >::type,
        std::false_type
    >::type type;
    return type::value;
};

is_co_prime<>()1 行でできることを行うには 10 行かかりますがis_prime<>()、1 行で行うこともできます。

return is_co_prime<N,D0>() && is_co_prime<N,D1,Di...>();

関数の本体である可能性があります。しかし、ここでは効率のために醜いものはきれいなものを打ち負かします。テールに再帰する必要があるたびis_prime<>()に、そのテールは以前よりも素数が 1 つだけ短くなります。同じことをしなければならないたび is_co_prime<>()に、テールは以前より2素数短くなります。その末尾再帰は、最悪の場合、 の末尾再帰よりも浅く、is_prime<>()半分しかありません。

is_co_prime<>()最初Nに、使用可能な除数のペアの中で最小かつ最も可能性の高い右辺で候補数を除算し、成功した場合は素数を返しません。それ以外の場合は、そのペアの右側にある除数に再帰し、成功するか使い果たされるまで、1 つ前の除数の試行を続けます。使い果たされた場合にのみ、元のペアの大きい方 (試行した中で最も可能性が低い除数) による試行分割に頼ります。同様に、介在する小さな再帰のそれぞれの中で、最も可能性が低い除数が最後に試行されます。

このアルゴリズムは の小さくて可能性の高い約数にすばやく到達するように見えますがN、最初にそれらの最小のものに直接到達し、 に従って真の降順確率でそれらを試すことは困難lastArg<>()です。リストの末尾にある場合、「最小のものに直接到達する」方法は、開始する前にリスト全体を再帰する必要があるメタ関数になるという認識で、このかゆみを鎮めなければなりませんトライアル部門あり。の実装でis_co_prime<>()は、「一度に 2 つのステップ」でリストを下に移動し、そのように試行分割を行います。

確かに、不運にも最初の最大の除数を「ステップオーバー」し、N それが底をつき、リストを逆方向に再帰するまで、再び見つけられないことがあります。しかしN、それが問題になるほど大きくなると、ほとんどの場合、少なくとも 1 つの小さい除数がさらに右にあり、それらすべてを見逃すのは本当に不運です。したがって、途中で最大のものをスキップするリスクは大したことではありません。 ポイントに到達するまで、途中で約数がないことも忘れないでくださいN/2。つまりN、途中でいくつかの唯一の除数をスキップすることによる再帰の最悪の場合の無駄は、その時点からリストの末尾に限定されます。

あなたはエラトステネスのふるいのメタプログラムの方がコンパイルが速いと推測していますが、その通りです。素数生成器として、Sieve は Trial Division よりも理論的な複雑さが優れています。2006 年以前のPeter Simonsによるエレガントなテンプレート メタプログラムの実装が ここにあります。(そして、Peter Wood がコメントしたように、エラトステネスのふるいメタプログラムは、C++ テンプレート システムがチューリング完全であるというニュースを伝えました。)はるかに効率的になったとは思わない。それだけで、Simons Sieve はコンパイル時に 512 番目までのすべての素数を 9 秒未満で生成できます。私のThinkPadで。が必要だ-ftemplate-depth=4000またはそれを行うには約 0.5GB のメモリしかありません。これは、大きなテンプレートの深さ == 大きなメモリ使用量であるという一般的な知恵に対するさらに顕著な反例です。

そのため、エラトステネスのふるいは、試験部門をほこりの中に置き去りにします。残念ながら、あなたのエクササイズの目的では、ふるいは役に立ちません。整数の上限を入力する必要があり、素数を残して2 と の間の合成数をふるいにかけるため、ふるいと呼ばれます。したがって、正確に N 番目の素数 = を見つけるために適用するには、他の方法ではなく、何らかの方法で計算する必要があります。すでに計算しただけを保持します。これはノーオペレーションです。UUPnPnPn + 1Pn + 2Pn > 2Pi, 2 <= Pi < PnPn

コメンターの何人かは、コンパイル時のメタプログラミングによって生成できる可能性のある N 番目の素数は、はるかに単純ではるかに高速な手段で事前に知られているか、事前に計算可能であると指摘しています。反対はできませんが、C++11 の機能を使用することで、TMP は実際のユーティリティに向けて大きく前進し、探索する価値があるというあなたの一般的な指摘を支持します。 10年で1秒。

一方、私たちの信じられないほど洗練された C++ コンパイラを離れなくても、このような TMP の問題で、K のクロック速度とメモリを備えた初期のコンピューターを、厳密にモデル化された「言語」でプログラミングする性質をまだ体験できますが、難解な制約の中で! - 古典的な再帰関数理論について。だからこそ、あなたは本当に彼らを愛さなければなりません!

于 2013-03-16T20:12:25.643 に答える
1

私はこれを自分で試してみて、次の実装を書きました:

template<unsigned... args> constexpr unsigned countArgs();
template<> constexpr unsigned countArgs() { return 0; }
template<unsigned head, unsigned... tail>
constexpr unsigned countArgs() { return 1 + countArgs<tail...>(); }

template<unsigned last>
constexpr unsigned lastArg() { return last; }
template<unsigned head, unsigned next, unsigned... tail>
constexpr unsigned lastArg() { return lastArg<next, tail...>(); }

template<unsigned i> constexpr bool isPrime() { return true; }
template<unsigned i, unsigned head, unsigned... tail>
constexpr bool isPrime()
{ return i % head && isPrime<i, tail...>(); }

template<bool found, unsigned i, unsigned... primesSoFar> struct nextPrime
{ static constexpr unsigned val =
    nextPrime<isPrime<i + 2, primesSoFar...>(), i + 2, primesSoFar...>::val; };
template<unsigned i, unsigned... primesSoFar> struct
nextPrime<true, i, primesSoFar...> { static constexpr unsigned val = i; };

template<unsigned n, unsigned... primesSoFar> struct nthPrimeImpl
{ static constexpr unsigned val = nthPrimeImpl<n - 1, primesSoFar...,
    nextPrime<false, lastArg<primesSoFar...>(), primesSoFar...>::val>::val; };
template<unsigned... primesSoFar> struct nthPrimeImpl<0, primesSoFar...>
{ static constexpr unsigned val = lastArg<primesSoFar...>(); };

template<unsigned n>
constexpr unsigned nthPrime() {
  return n == 1 ? 2 : nthPrimeImpl<n - 2, 3>::val;
}

constexpr unsigned p512 = nthPrime<512>();
static_assert(p512 == 3671, "computed incorrectly");

これにはgcc、たとえば-ftemplate-depth=1200. そして、遅すぎます。私のハードウェアでは約 3分かかります。したがって、別の回答でより効率的なコードが得られることを強く望んでいます。

計算方法に関しては、上記は試行分割のようなものです。エラトステネスのふるいの方がパフォーマンスが良いかもしれませんが、これまでのところ、constexpr 互換の方法でそれを記述する方法を思いつきませんでした。

于 2013-03-08T09:51:05.050 に答える
1

マイク・キンハンの答えは、私が以前は考えていなかった線に沿って考えさせられました. テンプレートのインスタンス化が深刻なメモリ消費を引き起こすような問題である場合、どうすればそれを減らすことができるでしょうか? 私は最終的に、これまでに見つかったすべての素数の引数パックの代わりに、型のチェーンを使用し、それぞれが前の型を参照し、型からのものを使用できるこれらの型の静的関数のチェーンを使用するスキームを思いつきました前。

以下に貼り付ける結果は、 zch によって提案されたものよりもまだかなり遅いですが、他のアプリケーションにとって有用なアプローチになる可能性があるため、共有するのに十分興味深いと思います。

template<unsigned N> struct NthPrime {
  typedef NthPrime<N - 1> previous;
  static constexpr unsigned prime = previous::nextPrime();
  static constexpr unsigned nextPrime() { return nextCoprime(prime + 2); }
  static constexpr unsigned nextCoprime(unsigned x) {
    // x is a candidate. We recurse to obtain a number which is
    // coprime to all smaller primes, then check that value against
    // the current prime.
    return checkCoprime(previous::nextCoprime(x));
  }
  static constexpr unsigned checkCoprime(unsigned x) {
    // if x is coprime to the current prime as well, then it is the
    // next prime. Otherwise we have to try the next candidate.
    return (x % prime) ? x : nextCoprime(x + 2);
  }
};

template<> struct NthPrime<1> {
  static constexpr unsigned prime = 2;
  static constexpr unsigned nextPrime() {
    return 3;
  }
  static constexpr unsigned nextCoprime(unsigned x) {
    return x; // x is guaranteed to be odd, so no need to check anything.
  }
};

template<unsigned n>
constexpr unsigned nthPrime() {
  return NthPrime<n>::prime;
}

constexpr unsigned p512 = nthPrime<512>();
static_assert(p512 == 3671, "computed incorrectly");

上記のビーストでは、constexpr の深さとテンプレートの深さの両方を変更する必要があります。次の値は、コンパイラの厳密な境界です。

time g++-4.7.2 -c -fconstexpr-depth=519 -ftemplate-depth=2042 -std=c++11 foo.cc

real    0m0.397s
user    0m0.368s
sys     0m0.025s
于 2013-03-16T22:50:26.720 に答える