У меня есть несколько функций, которым даны некоторые переменные x, y, z и т. Д., И я оцениваю их соответствующие множители с некоторыми постоянными коэффициентами в этих точках, возвращая значения.Мои переменные затем устанавливаются равными этим значениям, и процесс повторяется.В псевдо-коде:
repeat N times:
x_new = f1(x, y, z)
y_new = f2(x, y, z)
z_new = f3(x, y, z)
x = x_new
y = y_new
z = z_new
и функции - это что-то вроде
f1(x, y, z)
return c0 + c1*x + c2*y + c3*z + c4*x*x + c5*x*y + c6*x*z ...
Каждый раз, когда я сохраняю промежуточные значения моих переменных, а затем графически отображаю результат.Чтобы иметь достаточно точек для построения графика достаточного качества, мне нужно около 10 миллионов точек данных.У меня есть код, который делает это довольно быстро для 3 переменных и многочленов степени 3, но я пытаюсь расширить его, чтобы поддерживать произвольное число переменных и многочленов любой степени.Здесь все идет медленно, и я думаю, что мне нужен другой подход.
Мой оригинальный (жестко запрограммированный) оценщик c выглядел так:
double evaluateStep(double x, double y, double z, double *coeffs) {
double sum;
sum = coeffs[0];
sum += coeffs[1] * x;
sum += coeffs[2] * y;
sum += coeffs[3] * z;
sum += coeffs[4] * x * y;
sum += coeffs[5] * x * z;
sum += coeffs[6] * y * z;
sum += coeffs[7] * x * x;
sum += coeffs[8] * y * y;
sum += coeffs[9] * z * z;
sum += coeffs[10] * x * y * z;
sum += coeffs[11] * x * x * y;
sum += coeffs[12] * x * x * z;
sum += coeffs[13] * y * y * x;
sum += coeffs[14] * y * y * z;
sum += coeffs[15] * z * z * x;
sum += coeffs[16] * z * z * y;
sum += coeffs[17] * x * x * x;
sum += coeffs[18] * y * y * y;
sum += coeffs[19] * z * z * z;
return sum;
}
Обобщенный код:
double recursiveEval(double factor, double *position, int ndim, double **coeffs, int order) {
if (!order)
return factor * *((*coeffs)++);
double sum = 0;
for (int i = 0; i < ndim; i++)
sum += recursiveEval(factor * position[i], position + i, ndim - i, coeffs, order - 1);
return sum;
}
double evaluateNDStep(double *position, double *coeffs) {
double *coefficients = coeffs;
return recursiveEval(1, position, NUM_DIMENSIONS + 1, &coefficients, ORDER);
}
Конечно, я уверен, что это только что разрушило способность моего компилятора (gcc) выполнять общее удаление подвыражений и другие подобные оптимизации.Мне интересно, есть ли лучший подход, который я мог бы выбрать.Есть одна информация, которой я пока не смог воспользоваться - все коэффициенты взяты в начале программы из пула из 25 (с повторениями).Они охватывают [-1.2, 1.2] включительно, если это имеет какое-либо значение.
Я рассмотрел вычисление одного члена многочлена, а затем преобразовал его в каждое из других выражений путем простого умножения variableA/variableB, но суммаошибки, которая вводит, может быть слишком много.Я также рассмотрел вычисление всех терминов до степени n и их использование для построения терминов от n+1 до 2n.Еще один вариант, который я не уверен в том, как его реализовать, состоит в том, чтобы учитывать эти термины, используя тот факт, что многие термины будут иметь один и тот же коэффициент (принцип пиджинхола), так что может быть возможно снизить его до необходимого умножения.& дополнений, чем есть термины в расширенном выражении.Я не имею ни малейшего понятия, как это сделать, так как это должно было произойти во время выполнения, и это перешло бы в область JIT-компиляции выражения или чего-то подобного.
Как есть, 3Переменные степени 3 (всего 20 терминов) занимают почти 6 секунд, а 4 переменные степени 3 (всего 35 терминов) занимают чуть более 13 секунд.Они не будут хорошо масштабироваться до больших степеней или более переменных (формула для числа различных членов равна nck(degree + variables, degree), где nck - это «n выбирают k»).Я ищу способ улучшить производительность обобщенного кода, в идеале асимптотически (я подозреваю, с помощью частичной факторизации).Мне действительно безразличен язык;Я пишу этот код на C, но если вы предпочитаете представлять алгоритм на каком-то другом языке, это не будет проблемой для меня.