Most efficient way to store dictionaries in Matlab

0
votes

I have a set of IDs associated with costs which is just a double value. IDs are integers and unique. Two IDs may have same costs. I stored them as:-

a=containers.Map('KeyType','uint32','ValueType','double');
a(1)=7.3
a(2)=8.4
a(3)=7.3

Now i want to find the minimum cost.

b=[];
c=values(a);
b=[b,c{:}];
cost_min=min(b);

Now i want to find all IDs associated i.e. 1 and 3 with the minimum cost i.e. 7.3. I can collect all the keys into an array and then do a for loop over this array. Is there a better way to do this entire thing in Matlab so that for loops are not required?

2
matlabhashmap
so basically keys AND values are numbers? could it hurt to change the data type of the keys to double as well? I don't think so, then you could put everything in a normal array. - Robert Seifert
@thewaywewalk I read elsewhere that map containers in matlab do O(1) search unlike traversal over arrays. My main concern is speed. If you could suggest a fast way to do this on a normal array, that's enough for me. - user_1_1_1
@user_1_1_1 I think you misunderstand the concept of maps. Maps are effeicient if you have a key associated with a value and want to get the value of a specific key. This search can be fast because the keys are stored internally (eg. sorted or mapped with some hash or so) in an efficient way. However the problem you have is reversed. You want to find the smallest value. Unlike the IDs these are not sorted. This means that to find the smallest value you still have O(n/2) on average, except the element access will be slower. So use map if you need many key lookups else 2 array might do better. - patrik

2 Answers

2
votes

sparse matrix can work as a hashmap, just do this:

a= sparse(1:3,1,[7.3 8.4 7.3])
find(a == min(nonzeros(a))
0
votes

There are methods which can be used on maps for this kind of operations

http://se.mathworks.com/help/matlab/ref/containers.map-class.html

The approach finding minimum values and minimum keys can be done something like this,

a=containers.Map('KeyType','uint32','ValueType','double');
a(1)=7.3;
a(3)=8.4;
a(4)=7.3;

minval = inf;
minkeys = -1;
for k = keys(a)
    val = a.values(k);
    val = val{1};
    if (val < minval(1))
        minkeys = k;
        minval = val;
    elseif (val == minval(1))
        minkeys = [minkeys,k];
    end
end

disp(minval);
disp(minkeys);

This is not efficient though and value search is clumsy for maps. This is not what they are intended for. Maps is supposed to do efficient key lookup. In case you are going to do a lot of lookups and this is what takes time, then use a map. If you need to do a lot of value searches, I would recommend that you use a matrix (or two arrays) for this instead.

idx = [1;3;4];
val = [7.3,8.3,7.3];
minval = min(val);
minidx = idx(val==minval);
disp(minval);
disp(minidx);

There is also another post with an example where it is shown how a sparse matrix can be used as a hashmap. Let the index become the key. This will take about 3 times the memory as all non-zero elements an ordinary array, but a map uses more memory than an array as well.