случ. блуждания, периодические граничные условия

darin06

Вопрос алгоритмический. Задача о случайных блужданиях по двумерной решетке. Сейчас это выглядит приблизительно так:

  

// begin of loop over realizations;

i = rndi(N-1);//function returns random integer number (0,..., N - 1)

j = rndi(N-1);

[url=\\take]\\take[/url] into account periodically boundary conditions:

if(i == (N - 1 DeltaF = dh*(4*h[0][j] + 4*h[i][j + 1] + 2*h[i - 1][j] - h[0][j] - h[i][j + 1];

else DeltaF = dh*(4*h[i + 1][j] + 4*h[i][j + 1] + 2*h[i - 1][j] - h[i + 1][j] - h[i][j + 1]);

/*and so on, direct checking of indeces to select elements at the edge*/

//end of loop over realizations;

Смысл в том, что выбрав случайный элемент на решетке, с помощью if проверяется находится ли он на границе, и если i,j = 0 (нижняя и левая граница области то делаем замену i-1,j-1 => (N - 1 что бы замкнуть граничные условия (для правой и верхней границ соответственно i, j = (N - 1) => i+1, j+1 = 0).
Мне такой код не нравится.
1. Насколько сильно снижает производительность использование if (4 раза) в данном случае? (число шагов порядка 10^6)?
2. Как можно реорганизовать данный код, написав универсальную формулу для DeltaF, с автоматическим вычислением "правильных" индексов?
На второй вопрос у меня в голове мысли по решению, основанные на использовании операции остаток от деления нацело, но пока не реализовалось ни во что работающее )

evgen5555

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

Типа такого, что ли?
j - 1 => (j + N - 1) % N
j + 1 => (j + 1) % N

darin06

j - 1 => (j + N - 1) % N
j + 1 => (j + 1) % N

О, да, это оно.
А использование if в цикле насколько плохо само по себе?

evgen5555

А использование if в цикле насколько плохо само по себе?

Да не так уж это и плохо по идее, в код всего-то три инструкции добавляется:
subtract, compare to zero, jump if false
при порядке 10^6 это даже и не заметно
Другой вопрос - нужно ли ветвление после вышеозначенной замены?

elenangel

как бы деление будет выполняться всегда, а переход только в N из N^2 случаев, что по идее должен учесть предсказатель переходов

darin06

Да, с заменой мне гораздо больше нравится. Просто у меня давно засела фраза, не помню уже от кого услышанная, что мол "if в цикле это не круто", а чем это плохо я не знаю.

erotic

"if в цикле это не круто"

У меня на эту тему такая каша в голове:
Типа конвеер может заполнить наперед одни инструкции, а ветвление пойдет не туда, и ему придется занова думать. Правда, что-то мне такое говорили, что он в обе ветки просчитывает, но когда у тебя цикл с коротким телом и кучей if'ов, там уже получается много веток, может быть от этого тормоза. Мб щас все по-другому или это все неправильно я себе представляю.

Papazyan

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