У меня есть следующий код, который вычисляет число Стирлинга второго рода для заданных n и k,
#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
, но затем вылетает вскоре после этого. В частности, segfault происходит в 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.
Кто-нибудь знает, что здесь происходит?
Итак, после нескольких часов путаницы я сузил это до проблемы шаблонов выражений. Я не совсем понимаю, почему, но все это было связано с этим маленьким auto
в соответствии
auto val = k * stirlingS2(n - 1, k) + stirlingS2(n - 1, k - 1)
В основном, изменить это auto
в mp::cpp_int
и внезапно, никакого сегфоута.
Других решений пока нет …