Faster alternative to containers.Map

51 views (last 30 days)
Paolo Binetti
Paolo Binetti on 31 Aug 2017
Commented: Paolo Binetti on 1 Sep 2017
Profiling a script (attached, along with a sample input data file), I have found that looking up a Map generated with containers.Map is the bottleneck. Namely the table is:
s = containers.Map(nodes, num2cell([1:numel(nodes)]'));
and the script looks it up within a while-loop a few thousands times:
idx = s(temp1); % same as above if s is a Map object
I have tried replacing the Map object with a data structure, but it did not seem to work, due to field name limitations. Are there other faster methods?
  2 Comments
Paolo Binetti
Paolo Binetti on 1 Sep 2017
Thank you. I have just tried it. Referring to my original code (attached to the question), you can create the hash table like this:
t = java.util.Hashtable;
for k = 1:numel(nodes)
t.put(nodes{k}, k);
end
This takes much longer than creating a Map object, but maybe it can be sped up by vectorizing, if possible.
Then you can simply look the table up as follows:
idx = t.get(temp1);
Unfortunately this takes much longer than looking up the equivalent Matlab object.
Perhaps it would be faster using Python dictionaries in Matlab, but still have not figured out how.

Sign in to comment.

Answers (1)

Walter Roberson
Walter Roberson on 1 Sep 2017
fid = fopen('dataset_203_2.txt', 'rt');
approx_num_nodes = 3000;
used_nodes = 0;
known_nodes = nan(1, approx_num_nodes);
node_connections = cell(1, approx_num_nodes);
while true
thisline = fgetl(fid);
if ~ischar(thisline); break; end %end of file
toks = regexp(thisline, '^(?<src>\d+)\s*->\s*(?<dst>(\d+,\s*)*\d+)', 'names');
src = str2double(toks.src);
dst = str2double( regexp(toks.dst, ',\s*', 'split') );
mentioned = [src, dst];
[known, idx] = ismember(mentioned, known_nodes);
unknown = ~known;
num_new_nodes = nnz(unknown);
newnodes = used_nodes+(1:num_new_nodes);
known_nodes(newnodes) = mentioned(unknown);
used_nodes = used_nodes + num_new_nodes;
idx(unknown) = newnodes;
node_connections{idx(1)} = idx(2:end);
end
fclose(fid);
known_nodes = known_nodes(1:used_nodes);
At the end of this code, known_nodes will be a numeric list of node numbers from the file, in the order encountered, and node_connections will be a cell array of numeric vectors listing all of the connections. The connections listed will be in terms of the indices into the known_nodes list, not in terms of the original node numbers.
Another way of phrasing this is that the known_nodes is something would something you would use for the node labels, but the information in the node_connections list uses internal node numbers. It would be each to reconfigure this for text labels instead of numeric labels.
  3 Comments
Paolo Binetti
Paolo Binetti on 1 Sep 2017
Thank you. I also had tried a method based on repeated calls of ismember, but it was very slow. I was wondering if it could be improved by using undocumented ismembc2, but I am not sure it's a good approach.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!