0

特定の n と k の第 2 種スターリング数を計算する次のコードがあります。

#include <cstdint>
#include <map>

#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;


mp::cpp_int stirlingS2(unsigned n, unsigned k)
{
    if (n == 0 && k == 0) {
        return 1;
    }

    if (n == 0 || k == 0) {
        return 0;
    }

    static auto memo = std::map<std::pair<unsigned, unsigned>, mp::cpp_int>();
    auto nKPair = std::pair<unsigned, unsigned>(n, k);

    if (memo.count(nKPair) > 0) {
        return memo[nKPair];
    }

    auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1);

    memo[nKPair] = val;

    return val;
}

残念ながら、このコードを実行するとセグメンテーション違反が発生します。に挿入された最初の 87795 の値では正常に動作しているように見えますmemoが、その後すぐにクラッシュします。具体的には、セグメンテーション違反はmap::count、行の で発生しif (memo.count(nKPair) > 0) {ます。多分これはサイズ不足の問題だと思ったmemoので、 への割り当てに次の警告を追加しましたmemo。

if (memo.size() < memo.max_size()) {
    memo[nKPair] = val;
}

しかし、それは役に立ちませんでした。また、87795 の値は、これがいつクラッシュするかを示していないことにも気付きました。いくつかの小さな変更を加えて、最初の if ステートメントを次のように変更します。

if (n <= k) {
    return 1;
}

その値を 66453 に変更します。

ここで何が起こっているか知っている人はいますか？

4

1 に答える 1

1

わかりましたので、何時間も混乱した後、これを式テンプレートの問題に絞り込みました。理由はよくわかりませんが、すべてはautoラインのその小さなことに関係していました

auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1)

基本的に、それを変更しautoてmp::cpp_int、突然、セグメンテーション違反はありません。

于 2016-08-09T04:51:37.477 に答える