Вложенный цикл с зависимым счетчиком отключений границ - PullRequest
Новая
       25

Вложенный цикл с зависимым счетчиком отключений границ

3 голосов
/ 14 мая 2010

просто из любопытства я попытался сделать следующее, что оказалось не столь очевидным для меня; Предположим, у меня есть вложенные циклы с границами времени выполнения, например: 

 t = 0 //  trip count
 for l in 0:N
   for k in 0:N
     for j in max(l,k):N
        for i in k:j+1
           t += 1

 t is loop trip count

существует ли общий алгоритм / способ (очевидно, лучше, чем N ^ 4) для расчета счетчика циклов?

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

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

Ответы [ 3 ]

2 голосов
/ 14 мая 2010

Я верю, что внутренний цикл будет работать 

t = 1/8 * (N^4 + 6 * N^3 + 7 * N^2 + 2 * N)

раз.

Я не решал проблему напрямую, я подгонял полиномиальное выражение 4-го порядка к точно рассчитанному t для N от 1 до 50, надеясь, что получу точное соответствие.

Для точного расчета t я использовал 

sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),N),k,1,N),l,1,N)

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

подбор данных, логарифмическая шкала http://img714.imageshack.us/img714/2313/plot3.png

Подгонка для N от 1 до 50 точно соответствует, и вычисление ее для N = 100 дает 13258775 с использованием обоих методов.

EDIT: Упражнение было выполнено с использованием системы алгебры с открытым исходным кодом максимумы , вот фактический источник (вывод отброшен): 

nr(n):=sum(sum(sum(sum(1,i,k,j+1),j,max(l,k),n),k,1,n),l,1,n);
M : genmatrix( lambda([i,j],if j=1 then i else nr(i)), 50, 2 );
coefs : lsquares_estimates(M, [x,y], y = A*x^4+B*x^3+C*x^2+D*x+E, [A,B,C,D,E]);
sol(x):=ev(A*x^4+B*x^3+C*x^2+D*x+E, coefs);
sol(N);
S : genmatrix( lambda([i,j], if j=1 then i else sol(i)), 50, 2);
M-S;
plot2d([[discrete,makelist([M[N][1],M[N][2]],N,1,50)], sol(N)], [N, 1, 60], [style, points, lines], [color, red, blue], [legend, "simulation", sol(N)], [logy]);
compare(nr(100),sol(100));
0 голосов
/ 15 мая 2010

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

Чтобы увидеть это, рассмотрим следующее: 

for x in 0:N
  for y in 0:f(x)
    t += 1

Счетчик поездок t (N) равен сумме t (N) = f (0) + f (1) + f (2) + f (3) + ... + f (N-1).

Таким образом, если вы можете получить формулировку замкнутой формы для t (N) независимо от f (), вы нашли очень общий метод получения замкнутых форм, слишком общий, я бы сказал, потому что то, что вы здесь, соответствует интегралу и известно, что не все интегралы допускают формулировки замкнутых форм .

0 голосов
/ 14 мая 2010

Если вы хотите узнать, сколько раз внутренний цикл: 

for j in max(l,k):N

Будет выполнено, просто вычислить: N - max(l, k) в предположении открытого диапазона, N + 1 - max(l, k) в предположении закрытого диапазона.

Например, если: 

l = 2
k = 7
N = 10

тогда он будет работать 7, 8, 9, 10 (закрытый диапазон), так что действительно 10 + 1 - 7 = 4 раз.

...