topic Re: Recursion in proc fcmp in SAS Programming

Recursion in proc fcmp

RandomBet — Wed, 06 May 2015 03:14:46 GMT

Background: http://programmers.stackexchange.com/questions/281820/algorithms-for-allocating-n-balls-into-m-boxes

I'm trying a using recursion to update an array;

data Test;

N = 14;

M = 3;

array boxes[4] boxes1-boxes4 (4*.);

V = MyFun(N,M,boxes);

run;

proc fcmp outlib=Work.Functions.Test;

function MyFun(N,M,boxes

) varargs;

outargs boxes;

if M = 1 then do;

Total = 0;

do i = 0 to N;

if Func1(i) > Total then do;

Total = Func1(i);

boxes[1] = i;

end;

if M = 2 then do;

Total = 0;

do i = 0 to N;

do j = 0 to N-i;

if Func1(i) + Func2(j) > Total then do;

Total = Func1(i) + Func2(j);

boxes[1] = i;

boxes[2] = j;

end;

if M = 3 then do;

Total = 0;

D = dim(boxes);

array temp[1] / nosymbols;

call dynamic_array(temp,D);

do i = 0 to N;

do j = 0 to min(i,N-i);

Total_New = MyFun(i-j,M-1,temp) + Func3(j);

if Total_New > Total then do;

Total = Total_New;

boxes[1] = temp[1];

boxes[2] = temp[2];

boxes[3] = j;

end;

return(Total);

endsub;

run;

For M < 3, this works. But When M = 3, Total_New = MyFun(i-j,M-1,temp) + Func3(j); doesn't update the array temp.

For M > 3, how can I automatically adjust Func3 to MyFun_for_that_M ? In fact, functions don't have the same prefix.

Any hint is greatly appreciated.

Re: Recursion in proc fcmp

gergely_batho — Wed, 06 May 2015 12:54:00 GMT

Hi,

as a workaround you can use a static array.

D = dim(boxes);

array temp[1] / nosymbols;

call dynamic_array(temp,D);

array temp[999];

I found this sentence in the doc:

When an array is resized, the resized array is available only within the routine that resized it.

Base SAS(R) 9.3 Procedures Guide, Second Edition

Yes, you are calling the same routine, but still it is another "instance" of the MyFun function.

And because boxes is listed in the outargs statement, it is passed by reference, so the temp array basically becomes the boxes array (but not available, because it was resized).

Re: Recursion in proc fcmp

RW9 — Wed, 06 May 2015 13:08:04 GMT

Sorry, not entirely seeing the reason for creating a compiled function for this. Surely a simple set of loops in a datastep would be more efficient, as currently you hard code a loop value into the three blocks. I would consider looking at what you want to achieve, and simplifying, maybe create a small macro if really needed.

Re: Recursion in proc fcmp

RandomBet — Wed, 06 May 2015 15:39:49 GMT

Question edited. Please see the problem background.

Basically it's about the complexity. When N,M are large, brute force using loops will be very very slow. And it's not convenient to apply the function on different M's.

Re: Recursion in proc fcmp

RandomBet — Wed, 06 May 2015 15:42:21 GMT

Yes. It's passed by ref instead of by value. But the question is I do need outargs statements to update the boxes array.

Re: Recursion in proc fcmp

RW9 — Wed, 06 May 2015 17:10:02 GMT

Yes, you may want to add this to the Statistical procedures section, they may be able to give an actual procedure or simplified formula. From my side, I still can't see how the compiled function is going to be any quicker than standard code. In you example you have code blocks for if M=1, 2 or 3. But if M=100, you going to end up with (100 * 9) + 100 lines of code, so from a maintenance point of view that is a lot.

Perhaps some test data and required output would help, so I can fiddle around with it, example can the data be normalised, processed then transposed up again, does it need array processing. Maybe have conditional sub loops etc.

Re: Recursion in proc fcmp

gergely_batho — Thu, 07 May 2015 06:56:31 GMT

Yes, you need the outargs statement if you want to update the array and want to be the result "permanent" (accessible from the calling code).