8

gcc 4.8.1 と clang 3.4.190255 の両方を使用して、多くの最適化レベルでアセンブリ出力を確認しました。この種のコードのテール コール最適化はありません。

collatz_auxテールコールの最適化が得られない特別な理由はありますか?

#include <vector>
#include <cassert>

using namespace std;

vector<unsigned> concat(vector<unsigned> v, unsigned n) {
    v.push_back(n);
    return v;
}

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) {
    return n == 1
        ? result
        : n % 2 == 0
            ? collatz_aux(n / 2, concat(move(result), n))
            : collatz_aux(3 * n + 1, concat(move(result), n));
}

vector<unsigned> collatz_vec(unsigned n) {
    assert(n != 0);
    return collatz_aux(n, {});
}

int main() {
    return collatz_vec(10).size();
}
4

3 に答える 3

12

パラメータのデストラクタはvector<unsigned>、リターン後に呼び出す必要があります。

于 2013-09-25T14:32:24.363 に答える
2

参考までに、末尾再帰を取得するために、再帰バージョンを次のように微調整しました。

#include <vector>
#include <cassert>

using namespace std;

template<class container>
container &&collatz_aux(unsigned n, container &&result) {
    static auto concat = [](container &&c, unsigned n) -> container &&{
        c.push_back(n);
        return forward<container>(c);
    };

    return n == 1
        ? forward<container>(result)
        : n % 2 == 0
            ? collatz_aux(n / 2, concat(forward<container>(result), n))
            : collatz_aux(3 * n + 1, concat(forward<container>(result), n));
}

vector<unsigned> collatz_vec(unsigned n) {
    assert(n != 0);
    return collatz_aux(n, vector<unsigned>{});
}

int main() {
    return collatz_vec(10).size();
}
于 2013-09-25T16:29:05.777 に答える
1

これをテールコールに頼るべきではありません。オプティマイザーが、両方の再帰呼び出しがテール最適化できることに気付く可能性は低いと思います。

これは非再帰的なバージョンです。

vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) {
  while(true){
    if(n == 1) return result;
    result = concat(move(result), n);
    if(n % 2 == 0)
    {
      n=n / 2;
    }else{
      n= 3 * n + 1;
    }
  }
}
于 2013-09-25T14:38:38.017 に答える