Сабж. Есть полином от D параметров x_1,…x_D суммарной степени N. Его можно рассматривать как сумму членов x_1^{k1} x_2^{k2} … x_D^{kD}, sum k_i<=N. При каждом таком члене есть коэффициент типа double, нужна структура данных которая обеспечит эффективный доступ к коэффициенту если известен набор степеней k.
Число D известно в компайл-тайм, как правило D=2..4 но может быть и больше (скажем до 8ми). N известно в рантайм, N<256.
Можно смотреть на это как на структуру данных, которая должна реализовать угол D-мерной кубической сетки отрезанный плоскостью проходящей через ближайшие к нижнему левому углы вершины. Или как на результат возведения в степень N суммы D переменных (только там не мультиномиальные коэффициенты, с ними еще всякие пертурбации происходят).
Cтепени k хранятся в беззнаковом целом (4 или 8 байт), по байту на степень.
Сейчас это реализовано тупо, как std::map<uint32_t, double>, есть ощущение что доступ к этой штуке сильно тормозит. Другой крайностью будет просто создать массив из N^D даблов, но это противоречит моему чуйтству прекрасного - уж больно здоровый оверхед по памяти.
Можно еще просто создать вектор из даблов, вектор из int-ов (или вектор из пар) и заниматься там поиском половинным делением - это будет всяко лучше мапа. Но есть спинномозговое ощущение, что можно придумать формулу индексации, позволяющую из набора степеней получать смещение в векторе. Вот если кто то такую формулу знает, или может подсказать как такой алгоритм построить…
ЗЫ если кто то хочет предложить хэш-таблицу, то нужно предложить сразу алгоритма вычисления хэша исключающий коллизии - это собственно и будет искомая формула;-)
