Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Visual C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.09.2012, 17:32   #1
BleStaR
Форумчанин
 
Регистрация: 25.09.2009
Сообщений: 234
Восклицание Оптимизация кода (ускорение вычисления)

Доброе время суток! Вот такая проблемка возникла: слишком долго работает (было еще дольше, раз в 5 дольше чем сейчас - оптимизировал как смог... но все равно надо быстрее). Среда VS2010. Основная проблема естественно в циклах, все что не в них особой роли не сыграет. Вот блок программы:
Код:
// ============== обработка матрицы ===================================
	double **Ir = new double*[M];
	for(int l = 0; l < M; l++)
		Ir[l] = new double[N];

	for(int l = 0; l < M; l++)
		for(int j = 0; j < N; j++)
			Ir[l][j] = 0.0;


	double x, y, z, xy2, xyz2, dz = d/5000, kv = sqrt(v/2), delgam = 2, Rad, S = 0.0, S1, B1, B2;

	double mConst = - ( 2 * w * delgam / (4 * M_PI * k) );
	double mConstZnak;
	double n;
	
	for (int l = 0; l < M; l++){
		for(int j = 0; j < N; j++){
			for(int p = 0; p < M; p++){
				for(int q = 0; q < N; q++){
					if (q< (N-1) && I[p][q]!= I[p][q+1]){
						x = q - j + 0.5;
						y = p - l;

						xy2 = x*x + y*y;
						mConstZnak = -I[p][q] * mConst;
					
						S1 = 0.0;
					
						for(int t = 1; t <= 5000; t++){
							z = d * (t-1)/5000;

							xyz2 = xy2 + z*z;

							B2 = 2 * pow(xyz2, 1.5);
							Rad = sqrt(xyz2);

							if ( u == 1 ){
								B1 = - exp( -v * (x + Rad) / 2 );
								S1 += dz * mConstZnak * B1 * ( 2 * x + v * (xyz2 + x * Rad) )/B2;
							}
							
							if ( u == 0 ){
								n = -Rad * kv;
								S1 += ( dz * mConstZnak * x * Rad * exp(n) * ( (1 + kv)*cos(n) - kv*sin(n)))/B2;
							}
						}
						S += S1;
					}
					if (p < (M-1) && I[p][q] != I[p+1][q]){
						x = q - j;
						y = p - l + 1/2;
						
						xy2 = x*x + y*y;

						mConstZnak = -I[p][q] * mConst;

						S1 = 0.0;
					
						for( int t = 1; t <= 5000; t++){
							z = d * (t-1)/5000;

							xyz2 = xy2 + z*z;

							B2 = 2 * pow(xyz2, 1.5);
							Rad = sqrt(xyz2);

							if (u==1) {
								B1 = - exp( -v * (x + Rad) / 2 );
								S1 += dz * mConstZnak * B1 * y * (2 + v * Rad) /B2;
							}
							if (u==0) {
								n = -Rad * kv;
								S1 += ( dz * mConstZnak * y * Rad * exp(n) * ( (1 + kv)*cos(n) - kv*sin(n)))/B2;
							}
						}
						S += S1;
					}
				}
			}
			Ir[l][j] = S + (I[l][j] == 0 ? 0 : I[l][j] < 0 ? -1 : 1);
			S = 0.0;
		}
		printf("1");
	}


	double **It = new double*[M];
	for(int l = 0; l < M; l++)
		It[l] = new double[N];

	for(int l = 0; l < M; l++)
		for(int j = 0; j < N; j++)
			It[l][j] = 0.0;


	for(int l = 0; l < M; l++){
		for(int j = 0; j < N; j++){
			if (Ir[l][j] <= -1) {
				It[l][j] = 0;
				continue;
			}
			if (Ir[l][j] >= 1){
				It[l][j] = 255;
				continue;
			}
			It[l][j] = (Ir[l][j]*127.5 + 127.5);
		}
	}
P.S.: Жду даже малейших улучшений скорости. Так сказать с мира по нитке)))
BleStaR вне форума Ответить с цитированием
Старый 05.09.2012, 18:14   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Круто...
А задача какая?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 05.09.2012, 18:50   #3
BleStaR
Форумчанин
 
Регистрация: 25.09.2009
Сообщений: 234
По умолчанию

В кратце суть самой проги: в результате исследования получился некий снимок (для программы это файл-изображения в черно-белом формате: в среднем 100Х100... но чем больше прога вывезет тем лучше для исследования). Сама прога определяет уровень влияния (для упрощения) "каждого пикселя на каждый" (за исключением некоторых случаев. На выходе даем обработанное изображение (файл с цветами белый, черный, градации серого - т.е. крайний левый столбец RGB политры). Собственно как то так.

естественно что внутри циклов, при 100х100, операции повторяются 500 млдр раз!!! А ведь там куча умножений, встерчаются вычесления корней, cos, sin, exp ... короче много тяжеловесных радостей.

я уже сократил вызовы корней и умножений (посредством ввода доп переменных), раскрыл пару exp вручную, убрал работу с комплексными числами (математика рулит - за комп посчитал и дал ему готовую формулу)... Сейчас занимаюсь распаралельванием (подключаю MPI)... Но все равно бы еще какие уловки по сокращению количества операций внутри циклов или их ускорению... или же ускорить проверки (if-ы... я как то косо поглядываю на вот эти строки:
Код:
...
if (q< (N-1) && I[p][q]!= I[p][q+1]){
...
if (p < (M-1) && I[p][q] != I[p+1][q]){
...
по первому условию они подходят для всех соответствующих значений кроме одного... но как правильно (что бы не повлиять на результат, ибо результат тут есть все - любой ценной так сказать) их урезать я не нашел)

может кто увидит какие нибудь способы ускорения (например, за счет приведения к битовым операциям), или может по логике (где нить я пропустил) вообще что нить сократить и убрать пару операций умножения и т.п.

P.S. убрать хотя бы одну операцию умножения это уже убрать 500 млрд умножений!!!)))

При удаче с распаралельванием прога будет отрабатывать на кластере)))

Забыл добавить... MPI я только читать начал, не говоря уже о практическом применении... поэтому если кто уже практиковал такое, от советов и предложений точно не откажусь)))

Последний раз редактировалось Stilet; 05.09.2012 в 21:01.
BleStaR вне форума Ответить с цитированием
Старый 05.09.2012, 20:28   #4
Vago
Форумчанин
 
Регистрация: 15.01.2010
Сообщений: 948
По умолчанию

Для начала на само описание агоритма (на формулы) хорошо бы посмотреть. Вряд-ли без них кто-то здесь позволит себе роскошь в этот, без единого комментария, код закопаться. Места, в которые буквально вслепую ткнул пальцем:

1. Что такое w , k и d ? d - точно число с плавающей? Что это за волшебная константа 5000 ?

2.
Код:
	
        ...
        if (q< (N-1) && I[p][q]!= I[p][q+1]){
		x = q - j + 0.5;
		y = p - l;
        ...
2.1. Вместо первой проверки не проще ли верхнюю границу цикла на единичку уменьшить?
2.2. Зачем эта коррекция расстояния между столбцами, и почему таковой нет между строками?

3.
Код:
        ...
	if (p < (M-1) && I[p][q] != I[p+1][q]){
		x = q - j;
		y = p - l + 1/2;
        ...
Вопрос, аналогичный предыдущему. К тому же, 1/2 - это не 0.5 !

Что до оптимизации, то, для начала, в реальных "молотильных" программах с матрицами никто никогда этим Сишным двуступенчатым выделением памяти не пользуется. Выделяют одномерный массив и работают с приведенным индексами.
Vago вне форума Ответить с цитированием
Старый 05.09.2012, 21:07   #5
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

Цитата:
Сама прога определяет уровень влияния (для упрощения) "каждого пикселя на каждый"
Та-а-ак... Погоди.
Я правильно понимаю - допустим в координате 0,0 есть серый пиксель скажем процентов 20% в темную сторону.
Соответственно есть некий коэффициент-критерий, который говорит о том куда темнота этого пикселя дотягивается, фактически просчитывается "тень" пикселя.
Так?
Тогда ты заранее знаешь что в координате скажем 10,10 затухание будет по некоторому закону, скажем по логарифму равно нулю - т.е. тень пикселя эту координату уже не может накрывать. Соответственно тебе относительно этого пикселя нужно просчитывать не всю матрицу а только ту, на которую падает тень.

Я правильно понял задачу?
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 05.09.2012, 21:43   #6
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

Цитата:
я как то косо поглядываю на вот эти строки:
Код:

...
if (q< (N-1) && I[p][q]!= I[p][q+1]){
...
if (p < (M-1) && I[p][q] != I[p+1][q]){
...

по первому условию они подходят для всех соответствующих значений кроме одного... но как правильно (что бы не повлиять на результат, ибо результат тут есть все - любой ценной так сказать) их урезать я не нашел)
Код:
for ( int p=0; p<M-1; p++){
	for (int q=0; q<N-1; q++){
		if I[p][q]!=I[p][q+1]{.....}
		if I[p][q]!=I[p+1][q]{ ....}
	}
	{ int q=N-1;
	   /// теперь можно ///  if I[p][q]!=I[p][q+1]{.....}
	  if I[p][q]!=I[p+1][q]{ ....}
	}
}
{ int p=M-1;
   for (int q=0; q<N-1; q++){
   	if I[p][q]!=I[p][q+1]{.....}
	// и здесь if I[p][q]!=I[p+1][q]{ ....}
  }
  { int q=N-1;
     //  и так if I[p][q]!=I[p][q+1]{.....}
     // и так  if I[p][q]!=I[p+1][q]{ ....}
   }
}
программа — запись алгоритма на языке понятном транслятору
evg_m на форуме Ответить с цитированием
Старый 05.09.2012, 22:05   #7
Vago
Форумчанин
 
Регистрация: 15.01.2010
Сообщений: 948
По умолчанию

Кстати, в самом внутреннем цикле (по t) я могу вынести за цикл домножение на mConstZnak (ну, теперь с к-том 5000, конечно) или мне только так кажется?

ADDED 20:23 CET:
И к dz цикл по t, по-моему, тоже инвариантен?..

Последний раз редактировалось Stilet; 05.09.2012 в 23:01.
Vago вне форума Ответить с цитированием
Старый 05.09.2012, 22:48   #8
gsl180
Пользователь
 
Регистрация: 24.06.2012
Сообщений: 36
По умолчанию

Я конечно новичок, но что если в более загруженных цыклах for применить модификатор register int.
gsl180 вне форума Ответить с цитированием
Старый 06.09.2012, 09:02   #9
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

еще вариант потребует дополнительной памяти
предварительно рассчитать результаты сравнений

Цитата:
Код:
if (p < (M-1) && I[p][q] != I[p+1][q]){
if (q< (N-1) && I[p][q]!= I[p][q+1]){
Код:
for (p =....){
for (q =....){
R[p][q] = (p < (M-1) && I[p][q] != I[p+1][q])
L[p][q] =(q< (N-1) && I[p][q]!= I[p][q+1])
}}

	for (int l = 0; l < M; l++){
		for(int j = 0; j < N; j++){
			for(int p = 0; p < M; p++){
				for(int q = 0; q < N; q++){
					if L[p][q]{
нигде не заметил вычисления (определения) u для вот для этого
Цитата:
Код:
	if (u==1) {
еще кандидат на вынесение проверки из все циклов.
Код:
if (u=1) { 	for (int l = 0; l < M; l++){
		for(int j = 0; j < N; j++){
			for(int p = 0; p < M; p++){
				for(int q = 0; q < N; q++){
....}

if (u=0) { 	for (int l = 0; l < M; l++){
		for(int j = 0; j < N; j++){
			for(int p = 0; p < M; p++){
				for(int q = 0; q < N; q++){
.... }
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 06.09.2012 в 09:13.
evg_m на форуме Ответить с цитированием
Старый 06.09.2012, 15:52   #10
BleStaR
Форумчанин
 
Регистрация: 25.09.2009
Сообщений: 234
По умолчанию

Vago:
Цитата:
1. Что такое w , k и d ? d - точно число с плавающей? Что это за волшебная константа 5000 ?
Код:
	double d = 1.0; //толщина кристалла (пусть=1)
	double w = 1.0; //мощность источника тепла (пусть=1)
	double k = 1.0; //коэффициент теплопроводности (пусть=1)
	
	/*	
	*	скорость сканирования зондом поверхности
	*	(величина варьируемая в зависимости от величины изображения и др. параметров
	*	надо погонять при <1 и >1. Например, v=0.2, v=0.5,v=1, v=10).
	*/
	double v = 0.5;

	/*
	*	метка (если u=1 - проводится расчет для зонда постоянной интенсивности по одним формулам, 
	*	если u=0 - для пульсирующего зонда, соответственно, по другим формулам).
	*/
	int u = 1;
Что за "волшебная константа" я точно не знаю, как и не знаю почему именно 5000... так было (с тем исключением что был первоначально это был массив от 5000 элементов - убрал за не надобностью)

Цитата:
2.1. Вместо первой проверки не проще ли верхнюю границу цикла на единичку уменьшить?
Нельзя, т.к. потеряем несколько значений: при
Код:
q = N - 1
второе условие с
Код:
p < (M-1)
может быть истинно.
Цитата:
2.2. Зачем эта коррекция расстояния между столбцами, и почему таковой нет между строками?
ХЗ... так было в первоначальном (очень долго работающим) варианте программы, составленным самим исследователем.
Цитата:
К тому же, 1/2 - это не 0.5 !
одно и тоже ... пропустил однако))).
Цитата:
Что до оптимизации, то, для начала, в реальных "молотильных" программах с матрицами никто никогда этим Сишным двуступенчатым выделением памяти не пользуется. Выделяют одномерный массив и работают с приведенным индексами.
Меня смущает тот факт что добавятся операции по приведению индексов. Но сделаю... в предпоследнюю очередь (сначала получим упрощение остальных моментов)... а там сделаю два варианта, и гляну что удачнее работает.
BleStaR вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация кода LatuSerge Общие вопросы Delphi 10 27.12.2011 01:51
Оптимизация кода в си dampirik Помощь студентам 4 07.07.2009 11:30
Оптимизация кода nusik Общие вопросы Delphi 2 21.05.2009 17:55
Оптимизация кода Terran Общие вопросы Delphi 6 01.11.2008 16:57
Оптимизация кода [Smarik] Gamedev - cоздание игр: Unity, OpenGL, DirectX 9 20.08.2008 15:00