Efficiently inserting an element into an array

41 次查看（过去 30 天）
Lorcan O'Connor
Lorcan O'Connor 2021-8-17
编辑： Walter Roberson 2021-8-17
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更早的评论
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
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 个）

类别

在 Help Center 和 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