Complexity comparison: remove a key-value pair from a containers.map vs removing an item from an array.

Hi there,

I have an array (dataArr) of integers and I want to remove a specific integer (a) from it. A simple way to achieve this is by setting dataArr(dataArr == a) = []. Since the logical indexing here costs O(n) to compute, I think this way of removing a takes O(n) runtime.

A second possible approach is to store integers as the values of a containers.map and then use the "remove" function to remove a. I'm wondering if this approach will be more efficient? What will the complexity of this approach be?

I'll be grateful for any suggestions :)

Thanks,

Shirley

Answer 1

[Jan]

You can run a short test:

function [] = MapTest

figure;

len  = 1e3:5e4:1e6;
tMap = zeros(1, numel(len));
for idx = 1:numel(len)
   n = len(idx);
   M = containers.Map(1:n, 1:n);
   r = randperm(n, 1e3);

   tic
   for k = 1:1e3
      remove(M, r(k));
   end
   tMap(idx) = toc;
end
yyaxis left
H(1) = plot(len, tMap);

tInd = zeros(1, numel(len));
for idx = 1:numel(len)
   n = len(idx);
   M = 1:n;
   r = randperm(n, 1e3);
   
   tic
   for k = 1:1e3
      M(M == r(k)) = [];
   end
   tInd(idx) = toc;
end
yyaxis right
H(2) = plot(len, tInd);

legend(H, {'Map', 'Array'});

tMap(end)
tInd(end)
end

Result (R2018b, Win10):

The relations between the runtime and the data size look equivalent and like O(n), but the absolute run-time for arrays is much higher than for the map. I assume the arrays need much more time, because deleting one element let Matlab create a new array and copy the other elements. For Maps it seems, like the elements are stored independently, such that removing one element does not need to touch the rest, or the inplace-processing helps to save time. I do not know, how the container.Map is implemented internally.

[Xiaoqi Liu]

Thanks so much Jan for suggesting this experiement! :) Also, I discovered that a contain map seems to be a Java-based, unordered, construct, that uses hash-tables for indexing. See muncherelli's answer here: https://coderedirect.com/questions/201921/the-difference-between-a-container-map-and-a-struct-in-matlab . This means that the "remove" function supposedly takes O(1) runtime to complete.

[Bruno Luong]

The link doesn't work. But your question is valid. My guess is that the hash is used to transform a key to hash, however MATLAB stil store the array of all hash code as contiguous array behond the scene, therefor remove is not time constant?

[Jan]

Finding the matching key needs more time for larger maps. The timings look like an O(n) realtion also.