Using the output of one run of a function as the input of another iteration of that function

Hi so I've a problem where I have made a function that adds neighbouring elements and reduces its size (i.e. 50 elements reduces to 25 after one run of the function). What I want to do is repeat the function until the size of the matrix is 1 so that I can output the final addition. I cannot wrap my head around the loops to use since I want the loop to use the output of the previous iteration as the input for the next iteration i.e. the next run of the same function. For example 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1 elements

I was thinking something like this but it just repeats the first step (50 -> 25 -> 13) a load of times

Thank you for your help

for i = 1:Counter
    outputv = ReduceArray(List)
    inputv = ReduceArray(outputv);
end

Answer 1

[Matt J]

for i = 1:Counter
    List = ReduceArray(List);
end

[Jose Carrasco]

Hi @Matt J, would it be possible to make such a function run faster by, for instance, not overwriting "List" on each iteration? I am trying to speed up an identical loop where I run @Jan's Shuffle.c function to column-wise shuffle 450 independent 4100*2 arrays and it takes about 14.5 seconds per array (roughly 1h 48' total runtime). So far, preallocating either a x200001 cell array (first cell contains the original array, and then I use indexing to save each iteration's output and use it as the next iteration's input) or a 4100*200002 NaN matrix (two first columns contain the original 4100*2 array) and using it to save the output of each iteration almost doubled runtime (totalling ~21 to ~24 seconds). I would be really glad to know whether there is a way this procedure could run even faster, because I need to go through this whole for loop often.

Thank you all very much in advance for your advice.

[Torsten]

Which of the 450 x 4100*2 x 200001 produced data do you need in the end (i.e. after the loop) ?

[Jose Carrasco]

Hi Torsten, thanks for replying so fast. I only need the last cell (the cell containing the 4100*2 array that underwent 200000 shuffles).

[Torsten]

The first thing I would do is to work with numerical arrays, not with cell arrays. And what difference do you expect if you shuffle your array 200000 times in contrast to only one time ? From the random point of view, there won't be any.

[Jose Carrasco]

Yes, as I wrote, I already tried preallocating and then filling a 4100*200002 NaN numerical array, with little difference in time from the cell array solution. The original 4100*2 data arrays are all numerical as well ('double'). I know there is no need to shuffle the data that many times, but there is a reason I cannot bypass why I need to do it that way (that is why I really want to speed up the process).

Answer 2

[Walter Roberson]

would it be possible to make such a function run faster by, for instance, not overwriting "List" on each iteration?

No.

When you pre-allocate memory for output, and assign into it, something along the lines of

Array(:,Indices) = SomeFunction(Array, otherInputs)

then the way MATLAB operates is that it fully calculates SomeFunction(Array, otherInputs) into a temporary array, and then it copies the values out of the temporary array into the destination on the indexed left side.

MATLAB does not have any mechanism to determine the addresses of the locations that are being written into, and pass along those locations into SomeFunction for SomeFunction to somehow write directly into.

In C or C++, the calling routine can pass in a vector of pointers to rows, and that vector of pointers could be out of order relative to the destination matrix, so in C or C++ you can effectively code the equivalent of (say) Array(:, [3 8 1]) = FunctionCall(...) by passing a vector with the address of row 3, then the address of row 8, then the address of row 1, and the function would just use regular C or C++ multidimensional array indexing and think it was writing to consecutive rows. In C or C++ if you are scrambling the order of entries along a fortunate dimension, you do not need to copy the data at all, just scramble the list of pointers to components.

MATLAB does not operate the same way. MATLAB numeric arrays are always chunks of consecutive memory, and the only way to scramble the contents is to copy the data into a new array. (Now, if you just happen to be using a cell array, then the "contents" to be copied are pointers to the actual memory, and in at least some cases it could be pretty efficient.)

Because of this behaviour, pre-allocation of the output array requires copying the numeric data out of temporary memory into the destination. But this process is still faster than the alternative of growing an array "in place". When you grow an array in place, all of the current data has to be copied into a new location and then the new data added. Then the next iteration when you grow the array again, everything already in the array has to be copied to a new location, including everything that was copied last time. You end up copying 1 column, then 2 columns, then 3 columns.... N'th step you have copied N*(N-1)/2 columns so far. That adds up a lot. Whereas with the pre-allocation version, the first time you copy 1 column, the second time you copy 1 column, the third time you copy 1 column... at the end you have copied N columns instead of about N^2/2 columns.

It the case where you repeatedly do

for i = 1:Counter
    List = ReduceArray(List);
end

then the temporary array produced by ReduceArray becomes the new output List, with no copying needed. So overwriting all of the left side is faster, in the case where you do not need to keep a record of what was produced.

[Jose Carrasco]

Hello @Walter Roberson. Then can it be definitely concluded that overwriting all the left side in each iteration as in the example:

for i = 1:Counter

List = ReduceArray(List);

end

is indeed the ultimately fastest way to repeatedly use a function's output as its following iteration's input in MATLAB in the case where it is not needed to keep a record of what was produced in each iteration? Can I consider this issue closed?