2

This answer states

I don't think you (or I) can do dynamic data structures 'in' MATLAB. We have to use MATLAB OO features and MATLAB classes. Since I think that these facilities are really a MATLAB wrapper around Java I make the bold claim that those facilities are outside MATLAB. A matter of semantics, I concede. If you want to do dynamic data structures with MATLAB, you have to use OO and classes, you can't do it with what I think of as the core language, which lacks pointers at the user level.

Now suppose a bag. New numbers are added to the bag in random order and still the numbers should be ordered. The amount of numbers is unknown. Hence I need a dynamic data-structure: the size of the structure must be able to get changed. Also the structure must be able to get balanced i.e. I need to get it ordered.

Which data structure should I use for the dynamic balanced data-structure requirement in Matlab?

Community
  • 1
  • 1
hhh
  • 50,788
  • 62
  • 179
  • 282
  • 2
    That answer is completely out of date, Matlab's intrinsic OO facilities have advanced tremendously in the 4 years since I wrote it. Which suggests, to me, that you haven't done your research properly, haven't looked at the extensive documentation of Matlab's current OO and other data-structuring features. – High Performance Mark Aug 28 '13 at 16:31
  • @HighPerformanceMark Matlab works best with matrices, I cannot understand your talk about OO. Suppose a need for a dynamic matrix, is there anything like that? Or matrix where column-size needs to be updated every-now-and-then? – hhh Aug 28 '13 at 16:45
  • 1
    You can also use [Java data structures](http://undocumentedmatlab.com/blog/using-java-collections-in-matlab/) such as collections and maps. – Eitan T Aug 28 '13 at 16:55
  • @EitanT yes but does it make sense to use [Java data structures](http://undocumentedmatlab.com/blog/using-java-collections-in-matlab/) here? Matlab's matrices are inherently dynamic according to Luis. – hhh Aug 28 '13 at 18:25
  • 1
    @hhh MATLAB reallocates memory when changing size of arrays, which makes it very inefficient. – Eitan T Aug 29 '13 at 07:54
  • @EitanT where did you find the information about the reallocation of memory and inefficiency? If you are sure about Java's collections and maps, why are you not answering? It would make it easier for people to downvote/upvote different ideas. – hhh Aug 31 '13 at 21:16
  • @HighPerformanceMark If you are so sure about the `"extensive documentation"`, why are you not answering or correcting your old answer? – hhh Aug 31 '13 at 21:19
  • @hhh MATLAB's arrays are stored in contiguous in memory (_e.g_, see [here](http://www.mathworks.com/help/matlab/matlab_prog/strategies-for-efficient-use-of-memory.html)), so changing their size would require (re)allocation of a larger contiguous memory chunk. As to Java structures, I don't have MATLAB at hand to test my solution so I'm refraining from answering. – Eitan T Sep 01 '13 at 08:05

1 Answers1

2

Matlab's matrices are inherently dynamic. If you have a vector of ordered numbers and want to insert a new number in its proper place (maintaining the vector ordered), you can simply do

[~, ind] = find(number<=vector,1,'first'); % determine where to insert
if isempty(ind), ind = numel(vector)+1; end % in this case, insert at the end
vector = [vector(1:ind-1) number vector(ind:end)]; % do the insert, extending the vector

Of course this is not very fast because of the need for memory reallocation.

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • How does this method compare with other methods? I am confused by HPM's OO and why you call this `"Of course -- not very fast"`. Could it be faster to implement this with some novel linked-list implementation? Does Matlab implicitly implement the balancing? – hhh Aug 28 '13 at 18:44
  • Matlab does not allow you to directly control memory allocation (no malloc, pointers, etc). When you redefine the vector to be larger than it was, Matlab does the memory reallocation. Depending on how Matlab does it, it may be slow. – Luis Mendo Aug 28 '13 at 18:56
  • 1
    Nice. That `ind:xxx` is allowed when ind is empty is one of the wonders of matlab. – Buck Thorn Aug 29 '13 at 11:33
  • 1
    @TryHard Wow, I didn't know that! In any case, that doesn't allow me to remove line 2, because then `1:ind-1` would also be empty. – Luis Mendo Aug 29 '13 at 12:10
  • @LuisMendo could you update your answer, I did not follow the point -- taking me some time... +1 for comments. – hhh Aug 29 '13 at 16:50
  • @LuisMendo `"That ind:xxx is allowed when ind is empty is one of the wonders of matlab"` -- it like []:7 returns empty matrix. Is there a point when the code fails? If `ind` is empty, then vector becomes the number surrounded by empty sets. – hhh Aug 30 '13 at 21:51
  • @hhh No, the code does not fail, to my knowledge. The special cases that give rise to empty sets (the new element is to be inserted before the currect first or after the current last) are handled correctly as it stands. – Luis Mendo Aug 31 '13 at 13:05