Recursion in proc fcmp

Reply
New Contributor
Posts: 3

Recursion in proc fcmp

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;

      end;

      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;

      end;

      end;

      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;

      end;

      end;

      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.

    SAS Employee
    Posts: 340

    Re: Recursion in proc fcmp

    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).

    New Contributor
    Posts: 3

    Re: Recursion in proc fcmp

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

    SAS Employee
    Posts: 340

    Re: Recursion in proc fcmp

    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).

    Super User
    Super User
    Posts: 7,720

    Re: Recursion in proc fcmp

    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.

    New Contributor
    Posts: 3

    Re: Recursion in proc fcmp

    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.

    Super User
    Super User
    Posts: 7,720

    Re: Recursion in proc fcmp

    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.

    Ask a Question
    Discussion stats
    • 6 replies
    • 403 views
    • 3 likes
    • 3 in conversation