Preallocating cells with unknown output size

I need to optimize my script. A thing I could do is preallocating, however the size of my output cell is unknown so my question is if it is worth it.

the output of the script is X, the size of X is not known.

Now I have:

X={};
*my script
X=nxn cell

If the output cell has the size 2x2 for example, can I do something like this:

not sure if it will increase the speed of my script

X=cell(999);
*my script
X=999x999 cell

*somehow reduce the size of X

X=2x2 cell

[Stephen23]

@Joel Schelander: what size (or range of sizes) do you expect the final output to be?

https://www.mathworks.com/matlabcentral/answers/394671-no-performance-improvement-with-preallocating-for-object-arrays

https://blogs.mathworks.com/steve/2011/05/16/automatic-array-growth-gets-a-lot-faster-in-r2011a/?s_tid=srchtitle

[Joel Schelander]

the size is not known. Since X is an output of several set of input it is impossible for me to preallocate an exact size

[Stephen23]

@Joel Schelander: I am not expecting an exact size (otherwise the point of your question is moot). Most likely you can estimate the order of magnitude of how many cells you might expect (e.g. if you are processing image data, then the number of pixels places an upper limit on how many distinct objects can be represented in that image.

If we have an idea of the order of magnitude, then we can tailor our answers to help you better.

It makes a difference if your cell array is of the order one hundred cells vs one hundred million cells.

[Joel Schelander]

The size of X will increase to the magnitude 100 million I think. Right now Im just working with a very small sample to optimize the script.

[Bruno Luong]

10 millions by 10 million cell?

I don't believe any existing HW can support that at the moment.

Answer 1

[Bruno Luong]

If the size is not known, a good way is the to grow the preallocation array exponentially.

Rather than the assigment

X{i,j} = value;

Call

X = gassign(X,i,j,value);

where gassign implemented as follow

function X = gassign(X, i, j, val)
[m,n] = size(X);
if (i > m) || (j > n)
    gidx = @(s,k) max(max(2*s,s+1),k);
    X(gidx(m,i),gidx(n,j)) = {[]};
end
X{i,j} = val;
end

Then when finish truncate X to remove not filled cells.

You can start the script with X initialized as

X = {};

Answer 2

[KSSV]

You can try to initilize them as

X = cell([],[]) ;

You can check the timing using tic , toc.