Структура данных для хранения коэффициентов многомерного полинома?

Ты хочешь имея на входе Д координат получить число которое по этим координатам лежит.

Да

И таких структур тебе нужно много?

Мне нужно много экземпляров такой структуры. D известно в компайл-тайм, N в известно в рантайм. У разных экземпляров могут быть разные N и D

Как ты получил 66 для двумерного массива при N=10? 66 было бы при N=11.

степень k может быть нулевой в т.ч., т.е. 0<=k<=N

Ок. В голове крутится идея с последовательным отсечением слоев чтобы получать многомерные треугольники уменьшающейся размерности пока не получатся двумерные. Т.к. количество точек внутри каждого треугольника фиксировано и зависит от размерности то их можно будет преобразовать в линейный массив.

К сожалению в уме я это осилить не могу, т.к. умею представлять только 3хмерные объекты. Для куба (Д=3) и Н=4 например будут срезы по 15, 10, 6, 3, 1 точек. Но для больших размерностей придется хранить каждый слой последовательно, т.е. для Д=4 будет 4 группы по 35 чисел (если я ничего не напутал). Для случаев большей большей размерности мне нужно бумажка.

Да, я сейчас так же пытаюсь сделать. Только пока не работает.

ЗЫ точнее там можно отсекать пирамиду, треугольник и тд - понижать размерность оставшегося среза. Ну и все в одном векторе в итоге

В общем я сделал (bugfixer):

	inline uint64_t binomial_coeff(int n, int k){ // n>=k
		int a = k>n-k? k: n-k; uint64_t res = 1; 
		for(int i=a+1; i<=n; i++) res *= i; // n!/a!
		for(int i=2; i<=n-a; i++) res /= i; //  /(n-a)!
		return res;
	}
	template <int D, typename T=double> struct PolPowCoef {
		std::vector<T> coeffs;  // общее число коэффициентов binomial_coeff(max_pow+D-1, D)
		std::vector<int> vols;  // объемы пирамид, длина (D-1)*(max_pow+1), если степень равна нулю то и объем равен нулю
		int max_pow = -1, max_pow1 = 0;
	public:
		int get_max_pow() const { return max_pow; }
		size_t size() const { size_t sz = 0; for(auto x: coeffs){ sz += !is_caspol_zero(x); } return sz; }
		void init(int max_pow_){
			max_pow = max_pow_; max_pow1 = max_pow+1;
			vols.resize(max_pow1*(D-1), 0); coeffs.resize(binomial_coeff(max_pow+D-1, D), T(0));
			for(int d=D; d>1; d--){ // цикл по размерностям
				vols[(D-d)*max_pow1] = 0;
				for(int k=1; k<=max_pow; k++) // цикл по степеням
					vols[(D-d)*max_pow1+k] = binomial_coeff(k+d-1, d);
			}
		}
		template<typename K> T& operator[](K pows){
			size_t off = 0; uint32_t mp_k_sum = max_pow;
			for(int d=D-1; d>0; d--){
				uint32_t k = (pows>>(d*8))&0xFF;
				if(k){ off += vols[(D-1-d)*max_pow1 + mp_k_sum] - vols[(D-1-d)*max_pow1 + mp_k_sum-k];  mp_k_sum -= k; }
			}
			return coeffs[off+(pows&0xFF)];
		}
	};

На ноутбуке это дает небольшой прирост производительности по сравнению с хэш-таблицей, на кластере все вообще печально (slovazap)

map:           2.50155 minutes
unordered_map: 2.64558 minutes
PolPowCoef:    2.39972 minutes

Хотя многое зависит от постановки, на каких по то посановках хэш давал на кластере прирост, но небольшой.

Надо дальше думать над алгоритмом и играться с кодом. Всем спасибо за помощь!

Зачем же Вы индексы (vols) в одном месте с коэффициентами (coeffs) держите? Они должны считаться только один раз для данных D и N. Я бы сказал это ошибка дизайна.

Они считаются при инициализации структуры, это происходит куда реже чем доступ к структуре. Вводить какое то глобальное хранилище для индексов на ровном месте это вот как раз и будет ошибкой дизайна - такая оптимизация в данном случае вообще ничего не даст.

Вводить какое то глобальное хранилище для индексов на ровном месте

Никто не говорил про глобальное хранилище, создавать индекс можно где угодно, хоть на стеке. Главное отдельно от самих коэффициентов. Как минимум Вы просто перерасходуете память. Плюс такая табличка что - максимум десятки килобайт при Ваших параметрах, так? Ну и зачем её постоянно из кеша процессора вытряхивать и замещать копией? Дальше - если Вы всё правильно сделали то индекс будет вообще один для данного D (+ max(N) который используется), а сами данные могут быть любой длинны. Копирование данных стало дороже. Итд, итп. Дело Ваше конечно, но я бы на code review такое бы зарезал однозначно.

Я не программист, я вот этого всего что Вы написали не понимаю;-( Я знаю что размеры таблички много меньше размера вектора коэффициентов.

Куда бы Вы табличку положили?

Куда бы Вы табличку положили?

Если бы я это писал это был бы отдельный классик (PolPowCoefIndex или PolPowCoefVols, например) который бы передавался в конструктор PolPowCoef by const-ref (и хранился бы так же). Давайте так - пришлите мне как нибудь (выложите куда нибудь) self-contained sources, которые компиляются и работают на «дохлых» машинках - я Вам хотя бы дизайн и public interfaces поправлю (математику трогать не буду - и не просите), в пятницу (если авралов по работе не будет) думаю полчасика - часик смогу выкроить.

P.S. Да, и скажите в пределах какого плюсового стандарта нужно оставаться.

Я понял. Спасибо, это я могу сделать самостоятельно, я еще подумаю:-)

Я понял. Спасибо, это я могу сделать самостоятельно, я еще подумаю:-)

:) а зря ;) на самом деле ещё куча идей есть, но на код «нужно посмотреть»…

Верю! Если Вы хотите приобщиться к прекрасному миру академического кода (с т.з. программиста он ужасен до невозможности) то у нас его много. Хотите его поревьювить джаст-фор-фан?:-)

Верю! Если Вы хотите приобщиться к прекрасному миру академического кода

Я не знаю, (ну или у нас скорее всего разные понятия об) что такое «академический код»

Как выпускник «физкультурного техникума» я помочь пытался…

(с т.з. программиста он ужасен до невозможности) то у нас его много. Хотите его поревьювить джаст-фор-фан?:-)

Почему нет?

Я не знаю, (ну или у нас скорее всего разные понятия об) что такое «академический код»

Это код который пишется учОными не умеющими программировать для своих высоконаучных задач.

Почему нет?

t34119@yandex.ru

Но денег нет! Во всяком случае пока;-)

Но денег нет! Во всяком случае пока;-)

Не в них счастье, поверьте. Завтра отпишусь.

Как только Вы выведете формулу для числа точек на срезе N-мерного куба равноудаленных от его нулевой вершины (таких что sum(x{i}) = M) Вы получите отображение координат которые Вас интересуют на множество натуральных чисел, причём для данного max(M) такое отображение будет (запамятовал правильный термин) максимально компактно(?) / плотно(?). Мне представляется цена этого отображения будет O(D) и при это оно будет абсолютно нечувствительно к M.

―Ты бoярыню сoблазнил?
―Я. Аз есмь. Житие мoе.
―Какoе житие твoе, пес смердящий! Ты пoсмoтри на себя! Житие!
―Зинаида! Подскажи мне что-нибудь по-славянски! Паки! Паки, паки… Иже херувимы!