Efficiently inserting an element into an array

2021 8 17
1 个回答
回答已采纳
更新时间：2021 8 17
16 次查看（30 天）

0 个投票

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?

13 个评论
显示 11更早的评论 隐藏 11更早的评论

Matt J
Matt J 2021-8-17
No, there isn't. If you elaborate on what the code is doing, it might be possible to recommend alternative formulations.
Yazan
Yazan 2021-8-17
I think the complexity is O(n) indeed.
Lorcan O'Connor
Lorcan O'Connor 2021-8-17
@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
Matt J 2021-8-17
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
the cyclist 2021-8-17
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
Dave B 2021-8-17
Ran in:
Ran in:
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
Lorcan O'Connor 2021-8-17
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
Lorcan O'Connor 2021-8-17
@the cyclist unfortunately in this case I think any pre-allocation solution would use O(n^2) memory
Lorcan O'Connor
Lorcan O'Connor 2021-8-17
@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
dpb 2021-8-17
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
Lorcan O'Connor 2021-8-17
Are there other data structures, in MATLAB or not, that can insert in sublinear time?
Dave B
Dave B 2021-8-17
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
Dave B 2021-8-17
"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.

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

Walter Roberson
Walter Roberson 2021-8-17
编辑：Walter Roberson 2021-8-17

0 个投票

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.

更多回答（0 个）

类别

在 帮助中心 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

产品

版本

R2019b

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by