Efficiently inserting an element into an array

I have a 1xn array A and need to insert a number x between the mth and (m+1)th element.

I know this can be done by

A = [A(1:m),x,A(m+1:end)]

but I am not sure how MATLAB processes this - it could possibly involve re-assigning the entire latter section of the array, taking O(n) time. I suspect this is the case as a program that applies this many times is running quite slowly.

Is there a more efficient way to do this?

[Matt J]

No, there isn't. If you elaborate on what the code is doing, it might be possible to recommend alternative formulations.

[Yazan]

I think the complexity is O(n) indeed.

[Lorcan O'Connor]

@Matt J The program requires A to remain sorted at each iteration, and to insert a new element x at the correct spot each time. I find the insertion position by binary search, so theoretically the complexity should be log(n) - however updating A is a weak link at O(n)

[Matt J]

The elaboration that I think we need is on what is being done with A and why it needs to remain sorted. You will not be able to do so with o(N) effort.

[the cyclist]

I think it may be possible for the memory usage to be more efficient, if you are steadily growing A, element-by-element, to a large size. The reason is that MATLAB may need to repeatedly reallocate the memory for A.

If you know how large A will ultimately get, you can preallocate A to be that size (filling in with NaNs or zeros). You may need to do a bit more indexing to manipulate only the section of A that contains meaningful values, for your search/insertion. The devil is in the details.

[Dave B]

Just to expand on @the cyclist's preallocation approach, here's a version of that which avoids the reallocation. Here I used find to keep that bit concise...which I'm guessing would be O(n)...but you'd replace this with the log(n) bit that depends on A being sorted.

A = nan(1,100);
for i = 1:100
    b=rand;
    m=find(A<b,1,'last');
    if isempty(m)
        A(1:i)=[b A(1:i-1)];
    else
        A(1:i)=[A(1:m) b A(m+1:i-1)];
    end
end
isequal(A,sort(A))

ans = logical
   1

[Lorcan O'Connor]

This is a piece of coursework so I can't give full details. But I am dealing with a random 'invasion process' on the infinite square lattice, where we start at the origin and move 'outward' from the cluster of visited vertices at each step. I am constrained to use only O(n) memory for the first n steps, so to keep track of the visited vertices I can't just use a huge O(n^2) matrix of zeros and ones. Instead I store the coordinates in A, ordered first by the first coordinate and subordinately by the second coordinate. Given a random vertex from A, I need to check which neighbours are in A. Due to the ordering, I can do this in O(logn) time. When I then generate a new vertex, I can find where to slot it into A in O(logn) time too. The problem is actually slotting it into A efficiently.

I need to work on the order of n = 10^6, so this is basically impossible if the algorithm takes O(n^2) time but should be fast if I can get it to O(nlogn)

[Lorcan O'Connor]

@the cyclist unfortunately in this case I think any pre-allocation solution would use O(n^2) memory

[Lorcan O'Connor]

@Dave B Thanks but I don't really understand this - even though the size of A is preallocated, doesn't the A(1:i) =[b A(1:i-1)] line still take O(i) time since we're changing the value of all i entries? I'm not too familiar with the details of how matlab manages arrays, so perhaps I'm wrong here

[dpb]

All @Dave B claimed is to save any memory reallocation, not the complexity of the MATLAB-generated code.

TMW never divulges details of the code optimizations, but it is possible the reassignment boils down to a call to the compiler RTL memcopy() routine which is about as fast as you're going to get if you use an algorithm that must actually do the insertion each iteration.

Alternatively, keep only the insertion points and only build the list at the end although then the complexity of the indexing may turn out to be the killer...

[Lorcan O'Connor]

Are there other data structures, in MATLAB or not, that can insert in sublinear time?

[Dave B]

I probably was overly simplistic above, as I'm (probably) making a temporary array for the right hand side. The problem with appending to an array is that you reallocate it every time: insertion is inherently expensive.

Maybe you could do a little experiment to approximate O?

[Dave B]

"Are there other data structures, in MATLAB or not, that can insert in sublinear time?"

I'd think the standard datatype for fast insertion is a linked list, there isn't a built-in linked list in MATLAB (to my knowledge), but you can implement your own. https://www.mathworks.com/help/matlab/matlab_oop/example-implementing-linked-lists.html The example is for doubly linked and you could probably simplify by making a singly linked.

Answer 1

[Walter Roberson]

Create a binary tree from cell arrays. Nodes are cell if they are branches, non-cell if they are terminal.

It is common to use an implementation where each node has a slot for a value plus a left and right slot (possibly empty); this avoids reallocation of nodes, and can avoid having to chase down to the leaves every time.

... Would it be acceptable to use Containers.map ? https://www.mathworks.com/help/matlab/map-containers.html Those are, if I recall correctly, implemented as hash tables.