Efficiently inserting an element into an array
18 views (last 30 days)
Lorcan O'Connor on 17 Aug 2021
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?
Walter Roberson on 17 Aug 2021
Edited: Walter Roberson on 17 Aug 2021
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.