Как оптимизировать алгоритм?
1. убрать рекурсию
2. убрать выделение памяти внутри счетного куска
3. раскрутить циклы
4. использовать команды SIMD-расширения - аля SSE X.X
затем смотреть дизассм
убрать рекурсиюрекурсия - суть алгоритма, если только я для каждого t не буду отдельные функции писать.
епт. замени циклами, массивами
это я к тому, что при вызове ф-ции надо параметры в стэк паковать и т.п.
да, ещё в нам в школе били по рукам когда множественное ветвление в цикле писали в критичных ко времени исполнения кусках кода.
P.S. В данный алгоритм не вникал, и не знаю насколько существенна в нём рекурсия.
Шпала, напиши свой алгоритм на псевдокоде. ибо код вряд-ли кто будет читать
это конечный автомат же, где извращения?
рекурсия - суть алгоритмапод убрать рекурсию, понимается следующее (как первый этап): рекурсию через системный стек заменить на рекурсию через массив.
а что такое 999999999999999999?
sumf1_5 = sumf1_5 + (f1_5 - F(countersum1_5/(double)N*(f1_5 - F(countersum1_5/(double)N;
у меня начал глаз дергацо. зачем 2 раза функцию звать, которая считает одно и тоже значение?
может дело все-таки не в рекурсии, а в том, что просто память не освобождается?
СЗМ
суммирование здесь на потоки разбей
4-8-16 потоков попробуй. (4-8-16 аккумуляторов, их после цикла суммируешь и получаешь расчитываемую сумму )
соотв. шаг в цикле(инкремент) 4-8-16.
было:
double S, val;
S = 0;
for(int i=0; i<N;i++)
{
val = F(x[i])
S += val*val
}
стало:
double S,S1,S2,S3,S4, val1,val2,val3,val4;
S1 = S2 = S3 = S4 = 0;
for(int i=0; i<N;i+=4)
{
val1 = F(x[i ]);
val2 = F(x[i+1]);
val3 = F(x[i+2]);
val4 = F(x[i+3]);
S1 += val1*val1;
S2 += val2*val2;
S3 += val3*val3;
S4 += val4*val4;
}
S = S1 + S2 + S3 + S4;
Да, и проверку внутри цикла здесь
for( countersumm1 = OtN ;countersumm1<=counter;countersumm1++ )
{
if (N!=0) summf1 = summf1 + (f1 - F(countersumm1/(double)N*(f1 - F(countersumm1/(double)N;
}
вынеси за тело цикла, т.к. N - глобальная переменная и внутри цикла не переопределяется.
ЗЫ ты физик? ничо личного, просто проверить гипотезу.
например, ArrayMin2
в массив загоняются значения, потом делается проход по массиву и ищется минимум
больше массив ни за чем не используется
не проще сразу минимум считать?
т.е. вместо массива ввести переменную и присваивать ее токо на минимальные значения
скорость и память тут пипец как соптимизяться
У тебя исходная задача-то какая? Приблизить отрезками с концами в узлах сетки с наименьшим среднеквадратическим отклонением? Так для этого динамику применять надо (f[a][b] - наименьшее квадратическое отклонение при использовании b отрезков для приближения функции от 0 до a. Затем составляем формулу рассчета f[a][b] используя значения с меньшими индексами.)
ггг. Вообще, приведённый код напомнил мне код написанный какими-то C#-программистами, которые (видимо) на сях (кроме до-диеза) до этого не писали ничего. Правда, удалять память они удосужились таки.
Высвобождай память, избавься от лишних массивов. Да и мелкие косяки в коде присутствуют.
Советы преждевременные, о них стоит говорить тогда, когда программа будет написана более понятно и аккуратно.
с++ не знаю, последний раз писал на нем на 3-м курсе, исправлял ужие проги под свои
я сначала написал эту прогу на 1с, но она раз в 100 медленнее ситает, т.к. не предназначена для этого ( , вот псевдокод на 1с
Функция Ф(арг) Экспорт
//е = 2.71828;
//здесь функция х^2, а в с++ е^3, в 1с нет е
Возврат арг * арг;
КонецФункции
Функция НайтиИскКонФ(КолвоОтр,ОтН,ПоН) Экспорт
Если КолвоОтр = 1 Тогда
сум = 0;
Для сч = ОтН по ПоН Цикл
Если Не N = 0 Тогда
Сум = Сум + ф(сч/N);
Иначе
Сум = Сум;
КонецЕсли;
КонецЦикла;
Если НЕ(ПоН - ОтН) = 0 Тогда
ИскФ1 = Сум/(ПоН - ОтН);
Иначе
ИскФ1 = 0;
КонецЕсли;
МассивИКФИЗ1 = Новый Массив(1);
МассивИКФИЗ1[0] = ИскФ1;
Возврат МассивИКФИЗ1;
///////////////////////////////////////////ф2
ИначеЕсли КолвоОтр = 2 Тогда
МассивМин2 = Новый Массив(ПоН - ОтН + 1);
Для Каждого ЭМ Из МассивМин2 Цикл
ЭМ = 9999999999999999999999999999999999999999;
КонецЦикла;
МассивСоот1 = Новый Массив(ПоН - ОтН + 1);
МассивСоот2 = Новый Массив(ПоН - ОтН + 1);
МассивСоот3 = Новый Массив(ПоН - ОтН + 1);
Для сч = ОтН по ПоН Цикл
МассиВНЗФ1 = НайтиИскКонФ(1,ОтН,сч);
МассиВНЗФ2 = НайтиИскКонФ(1,сч,ПоН);
ф1 = МассиВНЗФ1[0];
ф2 = МассиВНЗФ2[0];
//Суммирование ф1
Сумф1 = 0;
Для счСум1 = ОтН по сч Цикл
Если Не N=0 Тогда
Сумф1 = Сумф1 + (ф1 - ф(счСум1/N*(ф1 - ф(счСум1/N;
Иначе
Сумф1 =Сумф1;
КонецЕсли;
КонецЦикла;
//Сум ф2
Сумф2 = 0;
Для счСум2 = сч По ПоН Цикл
Сумф2 = ?(N<>0,Сумф2 + (ф2 - ф(счСум2/N*(ф2 - ф(счСум2/NСумф2);
КонецЦикла;
МассивМин2[сч - ОтН] = СумФ1 + Сумф2;
МассивСоот1[сч - ОтН] = ф1;
МассивСоот2[сч - ОтН] = ф2;
МассивСоот3[сч - ОтН] = Сч;
КонецЦикла;
МинЭл_2 = ПоискМинЭМ(МассивМин2);
ПорядковыйСчетчик = МассивМин2.Найти(МинЭл_2);
МассивИКФИЗ2 = Новый Массив(3);
МассивИКФИЗ2[0] =МассивСоот1[ПорядковыйСчетчик];
МассивИКФИЗ2[1] = МассивСоот2[ПорядковыйСчетчик];;
МассивИКФИЗ2[2] = МассивСоот3[ПорядковыйСчетчик];
Возврат МассивИКФИЗ2;
///////////////////////////////////ф3
ИначеЕсли КолвоОтр = 3 Тогда
МассивМин3 = Новый Массив(ПоН - ОтН + 1);
Для Каждого ЭМ Из МассивМин3 Цикл
ЭМ = 9999999999999999999999999999999999999999;
КонецЦикла;
МассивСоот1 = Новый Массив(ПоН - ОтН + 1);
МассивСоот2 = Новый Массив(ПоН - ОтН + 1);
МассивСоот3 = Новый Массив(ПоН - ОтН + 1);
МассивСоот4 = Новый Массив(ПоН - ОтН + 1);
МассивСоот5 = Новый Массив(ПоН - ОтН + 1);
Для Сч_3 = ОтН По ПоН Цикл
МассиВНЗФ1 = НайтиИскКонФ(2,ОтН,сч_3);
МассиВНЗФ2 = НайтиИскКонФ(1,сч_3,ПоН);
ф1_3 = МассиВНЗФ1[0];
ф2_3 = МассиВНЗФ1[1];
ИСч_3 =МассиВНЗФ1[2];
ф3_3 = МассиВНЗФ2[0];
//Суммирование ф1_3
Сумф1_3 = 0;
Для счСум1_3 = ОтН по Исч_3 Цикл
Сумф1_3 = ?(N<>0,Сумф1_3 + (ф1_3 - ф(счСум1_3/N*(ф1_3 - ф(счСум1_3/NСумф1_3);
КонецЦикла;
//Суммирование ф2_3
Сумф2_3 = 0;
Для счСум2_3 = Исч_3 по Сч_3 Цикл
Сумф2_3 = ?(N<>0,Сумф2_3 + (ф2_3 - ф(счСум2_3/N*(ф2_3 - ф(счСум2_3/NСумф2_3);
КонецЦикла;
//Суммирование ф3_3
Сумф3_3 = 0;
Для счСум3_3 = Сч_3 по ПоН Цикл
Сумф3_3 = ?(N<>0,Сумф3_3 + (ф3_3 - ф(счСум3_3/N*(ф3_3 - ф(счСум3_3/NСумф3_3);
КонецЦикла;
МассивМин3[сч_3 - ОтН] = СумФ1_3 + Сумф2_3 + Сумф3_3;
МассивСоот1[сч_3 - ОтН] = ф1_3;
МассивСоот2[сч_3 - ОтН] = ф2_3;
МассивСоот3[сч_3 - ОтН] = ф3_3;
МассивСоот4[сч_3 - ОтН] = ИСч_3;
МассивСоот5[сч_3 - ОтН] = Сч_3;
КонецЦикла;
МинЭл3 = ПоискМинЭМ(МассивМин3);
ПорИнд = МассивМин3.Найти(МинЭл3);
МассивИКФИЗ3 = Новый Массив(5);
МассивИКФИЗ3[0] = МассивСоот1[ПорИнд];
МассивИКФИЗ3[1] = МассивСоот2[ПорИнд];
МассивИКФИЗ3[2] = МассивСоот3[ПорИнд];
МассивИКФИЗ3[3] = МассивСоот4[ПорИнд];
МассивИКФИЗ3[4] = МассивСоот5[ПорИнд];
Возврат МассивИКФИЗ3;
////////////////////////////ф4
ИначеЕсли КолвоОтр = 4 Тогда
МассивМин4 = Новый Массив(ПоН - ОтН + 1);
Для Каждого ЭМ Из МассивМин4 Цикл
ЭМ = 9999999999999999999999999999999999999999;
КонецЦикла;
МассивСоот1 = Новый Массив(ПоН - ОтН + 1);
МассивСоот2 = Новый Массив(ПоН - ОтН + 1);
МассивСоот3 = Новый Массив(ПоН - ОтН + 1);
МассивСоот4 = Новый Массив(ПоН - ОтН + 1);
МассивСоот5 = Новый Массив(ПоН - ОтН + 1);
МассивСоот6 = Новый Массив(ПоН - ОтН + 1);
МассивСоот7 = Новый Массив(ПоН - ОтН + 1);
Для Сч_4 = ОтН По ПоН Цикл
МассиВНЗФ1 = НайтиИскКонФ(3,ОтН,сч_4);
МассиВНЗФ2 = НайтиИскКонФ(1,сч_4,ПоН);
ф1_4 = МассиВНЗФ1[0];
ф2_4 = МассиВНЗФ1[1];
ф3_4 = МассиВНЗФ1[2];
ИСч1_4 =МассиВНЗФ1[3];
ИСч2_4 =МассиВНЗФ1[4];
ф4_4 = МассиВНЗФ2[0];
//Суммирование ф1_4
Сумф1_4 = 0;
Для счСум1_4 = ОтН по Исч1_4 Цикл
Сумф1_4 = ?(N<>0,Сумф1_4 + (ф1_4 - ф(счСум1_4/N*(ф1_4 - ф(счСум1_4/NСумф1_4);
КонецЦикла;
//Суммирование ф2_4
Сумф2_4 = 0;
Для счСум2_4 = Исч1_4 по ИСч2_4 Цикл
Сумф2_4 = ?(N<>0,Сумф2_4 + (ф2_4 - ф(счСум2_4/N*(ф2_4 - ф(счСум2_4/NСумф2_4);
КонецЦикла;
//Суммирование ф3_4
Сумф3_4 = 0;
Для счСум3_4 = Исч2_4 по Сч_4 Цикл
Сумф3_4 = ?(N<>0,Сумф3_4 + (ф3_4 - ф(счСум3_4/N*(ф3_4 - ф(счСум3_4/NСумф3_4);
КонецЦикла;
//Суммирование ф4_4
Сумф4_4 = 0;
Для счСум4_4 = Сч_4 по ПоН Цикл
Сумф4_4 = ?(N<>0,Сумф4_4 + (ф4_4 - ф(счСум4_4/N*(ф4_4 - ф(счСум4_4/NСумф4_4);
КонецЦикла;
МассивМин4[сч_4 - ОтН] = СумФ1_4 + Сумф2_4 + Сумф3_4+ Сумф4_4;
МассивСоот1[сч_4 - ОтН] = ф1_4;
МассивСоот2[сч_4 - ОтН] = ф2_4;
МассивСоот3[сч_4 - ОтН] = ф3_4;
МассивСоот4[сч_4 - ОтН] = ф4_4;
МассивСоот5[сч_4 - ОтН] = Исч1_4;
МассивСоот6[сч_4 - ОтН] = Исч2_4;
МассивСоот7[сч_4 - ОтН] = Сч_4;
КонецЦикла;
МинЭл4 = ПоискМинЭМ(МассивМин4);
ПорИнд = МассивМин4.Найти(МинЭл4);
МассивИКФИЗ4 = Новый Массив(7);
МассивИКФИЗ4[0] = МассивСоот1[ПорИнд];
МассивИКФИЗ4[1] = МассивСоот2[ПорИнд];
МассивИКФИЗ4[2] = МассивСоот3[ПорИнд];
МассивИКФИЗ4[3] = МассивСоот4[ПорИнд];
МассивИКФИЗ4[4] = МассивСоот5[ПорИнд];
МассивИКФИЗ4[5] = МассивСоот6[ПорИнд];
МассивИКФИЗ4[6] = МассивСоот7[ПорИнд];
Возврат МассивИКФИЗ4;
////////////////ф5
ИначеЕсли КолвоОтр = 5 Тогда
МассивМин5 = Новый Массив(ПоН - ОтН + 1);
Для Каждого ЭМ Из МассивМин5 Цикл
ЭМ = 999999999999999999999999999999999999999999999999999999999999999999999;
КонецЦикла;
МассивСоот1 = Новый Массив(ПоН - ОтН + 1);
МассивСоот2 = Новый Массив(ПоН - ОтН + 1);
МассивСоот3 = Новый Массив(ПоН - ОтН + 1);
МассивСоот4 = Новый Массив(ПоН - ОтН + 1);
МассивСоот5 = Новый Массив(ПоН - ОтН + 1);
МассивСоот6 = Новый Массив(ПоН - ОтН + 1);
МассивСоот7 = Новый Массив(ПоН - ОтН + 1);
МассивСоот8 = Новый Массив(ПоН - ОтН + 1);
МассивСоот9 = Новый Массив(ПоН - ОтН + 1);
Для Сч_5 = ОтН По ПоН Цикл
МассиВНЗФ1 = Н
когда ты удалишь МассивМин2?
да, че-то лохонулся. спасибо, в 1с можно подчищать массивы.
подчищатьне в этом дело
удали это ВООБЩЕ
это
массивМин2[сч - ОтН] = СумФ1 + Сумф2;
замени на
ЕСЛИ (СумФ1 + Сумф2) > МинЭл_2
ТО
МинЭл_2 = СумФ1 + Сумф2;
МинПорядковыйСчетчик = сч - ОтН;
КОНЕЦ ЕСЛИ
функцию нахорждения минимума тоже удали нах
а также все твои кучи девяток, тем более что вместо этого нада юзать MAX_INT
у тебя минимум уже считается
бля, ужоснах
Оставить комментарий
UAV27
Алгоритм по приближению функции е^3х на участке от 0 до 1, с заданным шагом N и с заданным t количеством участков постоянства. посчитал для N = 100 и t = 5 (пока только для пяти написал, но для большего там по аналогии). для N = 1000 и t = 5 прога сжырает 3 гига памяти и вылетает.а мне надо посчитать для N = 1000 и t = 10
Суть алгоритма - рекурсивная функция, вызвающаяя себя много-много раз, т.е. что б посчитать для t = 5, мы вызавем ее 100 раз для t = 4, которая в свою очередь вызовет себя меньше 100 раз(скока неизвестно) для t = 3, и т.д. до t = 1. прога ищет искомые константные функции и точки разделения. (т.е. от 0 до 55 такая функция, от 55 до 98 такая-то функция и т.д.)
вот код: