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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 07.09.2012, 15:09   #21
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

В развитие
Цитата:
Начинку циклов по t можно без труда сделать инвариантной относительно значений I[][]. Тогда она выносится в начало и, в результате её выполнения MxN (кажется) раз
Вместо двух предложенных раннее массивов, можно
Если элементом массива сделать запись, то кроме значений проверок туда можно добавить и другие величины зависящие только от p и q,
в т.ч. сами значения p и q.
Код:
mas[p][q].L = первая проверка
mas[p][q].R = другая проверка
mas[p][q].x = q - j + 0.5;
mas[p][q].y = p - l;
mas[p][q].xy2 = x*x + y*y;
mas[p][q].mConstZnak = -I[p][q] * mConst; 
в т.ч. сами значения p и q. 
mas[p][q].p =p;
mas[p][q].q =q;
Зачем р и q?
А теперь мы можем безболезненно превратить массив в одномерный
Цитата:
Меня смущает тот факт что добавятся операции по приведению индексов
было
Код:
for (p=0; p<M; p++)
for (q=0; q<N; q++)
станет
Код:
for (pq=0; pq<M*N; pq++)
или вообще отказаться от использования индексов а пользоваться "бегущим" указателем. нечто вроде любимой конструкции C
Код:
for (stat =*mas[0][0];указатель на первый
      stat<*mas[M][N];указатель на последний
      stat++ движение указателя )
программа — запись алгоритма на языке понятном транслятору

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

evg_m
x и y нельзя добавлять как поле, так как: при картинке 100х100 mas будет иметь 100^2 элементов, а значений x и y должно быть 100^4.

Последний раз редактировалось BleStaR; 07.09.2012 в 15:58.
BleStaR вне форума Ответить с цитированием
Старый 07.09.2012, 18:49   #23
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,515
По умолчанию

Цитата:
Код:
for(int t = 1; t <= 5000; t++){
	z = d * (t-1)/5000;
Код:
for ( int t=1; t<5000; t++) (z[t]:=d*(t-1)/5000;
Еще один вынесенный расчет. (N*N*M*M) раз

Внутри остается
Код:
for (int t=1; t<5000; t++){
  xyz2 = xy2 + z[t]*z[t];
А может и так получится
Код:
z[t] =( d*(t-1)/5000 ) * ( d*(t-1)/5000 );
Цитата:
x и y нельзя добавлять как поле, так как: при картинке 100х100 mas будет иметь 100^2 элементов, а значений x и y должно быть 100^4.
x = q - j + 0.5;
q =0..N j=0..N => x = -N (0-N) .. N(N-0) итого (2N+1) значениий
учитваая разные добавки (+0.5 +0) получаем 4N+2 вариантов

осталость придумать как это вынести за скобки (из цикла)

y = p - l;
аналогично y = -M M 4M+2 вариантов
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 07.09.2012 в 19:17.
evg_m вне форума Ответить с цитированием
Старый 07.09.2012, 20:27   #24
Ivan_Susanin
Пользователь
 
Регистрация: 15.04.2007
Сообщений: 20
По умолчанию

обсуждая данную задачу с Evg_m

Цитата:
Сообщение от evg_m Посмотреть сообщение

x = q - j + 0.5;
q =0..N j=0..N => x = -N (0-N) .. N(N-0) итого (2N+1) значениий
учитваая разные добавки (+0.5 +0) получаем 4N+2 вариантов

осталость придумать как это вынести за скобки (из цикла)
рассмотрели такой вариант сокращения сложности с N^2*M^2*Z(=5000) до N*M*Z + N^2*M^2


вводится дополнитеьный массив XY, и аналогичный ему xy2, для второй ветки ифа

Код:
for (i=-N;i<n;i++) {
 for(j=0;j<m;j++){
    S1 = 0.0;
    x = i + 0.5;
    y = j;
    xy2=x*x+y*y
     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);
           B1 = - exp( -v * (x + Rad) / 2 );
           S1 += B1 * ( 2 * x + v * (xyz2 + x * Rad) )/B2;
           }
     XY[i,j]=s1;
}}
а основной код заменяется на


Код:
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]){
						mConstZnak = -I[p][q] * mConst;
					        
						S += XY[q - j,p-i] *mConstZnak;}
                                          if (p < (M-1) && I[p][q] != I[p+1][q]){

						mConstZnak = -I[p][q] * mConst;
					        
						S += XY2[q - j,p-i] *mConstZnak;}
					}

Последний раз редактировалось Ivan_Susanin; 07.09.2012 в 20:52.
Ivan_Susanin вне форума Ответить с цитированием
Старый 11.09.2012, 11:07   #25
Kukurudza
Форумчанин
 
Регистрация: 02.06.2011
Сообщений: 282
По умолчанию

я в программе не разбирался ибо не знаю алгоритма, но правильно заметили ранее, приведите алгоритм? что вообще делаете? может вы и правда, как было замечено, 99% времени тратите впустую на влияние нуля на далеко лежащие клетки?
а вообще, если ваш алгоритм имеет сложность, скажем N^5 хоть наизнанку вывернитесь, он так же будет занимать N^5, может подобрать другой алгоритм?
и хотелось бы всетаки узнать, на сколько программа ускорилась от начального момента до последней редакции?
я не зря написал N^5, так как у вас 5 вложенных друг в друга циклов.

Последний раз редактировалось Kukurudza; 11.09.2012 в 11:10.
Kukurudza вне форума Ответить с цитированием
Старый 06.10.2015, 20:09   #26
photon82
Новичок
Джуниор
 
Регистрация: 06.10.2015
Сообщений: 2
По умолчанию

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

В приведенном коде есть new и нет delete - у вас так будет утечка памяти. Лучше пользоваться уже изобретенными велосипедами типа std::vector и забыть о проблеме с утечкой памяти.

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

Объявите переменные, по которым бегают циклы, над ними, а не в циклах - вы избежите многократного выделения памяти и удаления этих переменных по каждому проходу внешних циклов

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

Цитата:
Сообщение от BleStaR Посмотреть сообщение

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;
вычисление y тут можно поднять на уровень выше.

++i в циклах предпочтительнее, чем i++


Ну и наконец, основное ускорение вы получите, если не будете решать задачу в лоб, а проанализируете, расстояние, на котором какое-то влияние еще есть.
С ростом Rad у вас очень быстро стремится к 0 B1 и S1. Для изображения, которое строится с точностью 8 бит добавки даже в 5-ом знаке после запятой ни на что не повлияют, а это значит, что вместо пробегания по 5000х5000 точек вам, возможно,
хватит какой-нибудь окрестности типа 11х11 (зависит от значения v) - то есть сразу ускоритесь примерно в 200000 раз. Даже если окрестность будет 101х101 все равно выиграете больше чем в 2000 раз, но я сильно сомневаюсь, что при экспоненциальном убывании влияния понадобится рассматривать расстояния больше чем на 10-20 точек.

Последний раз редактировалось photon82; 06.10.2015 в 20:17.
photon82 вне форума Ответить с цитированием
Старый 06.10.2015, 20:17   #27
photon82
Новичок
Джуниор
 
Регистрация: 06.10.2015
Сообщений: 2
По умолчанию

Цитата:
Сообщение от Kukurudza Посмотреть сообщение
а вообще, если ваш алгоритм имеет сложность, скажем N^5 хоть наизнанку вывернитесь, он так же будет занимать N^5, может подобрать другой алгоритм?
Это не так. Если сейчас он рассматривает все далекие точки, а на самом деле надо рассматривать только фиксированное количество соседей, то вместо сложности О(N^5) получит O(N^3*R^2), где R - радиус, на котором надо смотреть влияющих соседей.

При N > R, как в нашем случае, влияние R станет константным и сложность алгоритма станет O(N^3) - это совсем не то, что O(N^5)
photon82 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 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