I am very, very new to Matlab. I migrated c++ code to Matlab, because I knew vectors were involved in the problem, and thought I could get a performance boost using the language. I pretty much just translated the code line-by-line. My inexperience was obvious, since the code runs slower than it did in c++....
Obviously, I'm not taking full advantage of the language's features... or maybe the problem just isn't suited for it.
Below are the two code segments (both loops) that have become a huge bottle neck. It is a graph problem, with this iteration having 501 points (24675 edges). The program also used for much bigger test sets, up to 20,000 points, so speed is a necessity.
The first code segment takes about a minute. It reads in all the point values in a text file. master_graph is a map (int keys) of vectors (edges)
Code:
for i=1:(numEdges)
%? change types to save space?
line = fgets(fid);
%# read line by line
A = sscanf(line,'%i %i %i');
num1 = A(1);
num2 = A(2);
num3 = A(3);
temp_node = num1;
temp_edge.endpoint=num2;
temp_edge.distance=num3;
if (temp_edge.distance > max_distance_for_wb)
max_distance_for_wb = temp_edge.distance;
end
if(isKey(master_graph,temp_node))
master_graph(temp_node) = [master_graph(temp_node) temp_edge];
else
master_graph(temp_node) = temp_edge;
end
swap = temp_node;
temp_node = temp_edge.endpoint;
temp_edge.endpoint = swap;
if(isKey(master_graph,temp_node))
master_graph(temp_node) = [master_graph(temp_node) temp_edge];
else
master_graph(temp_node) = temp_edge;
end
end
The fact that reading from a file is involved, it will obviously be slower, but is there a better way of doing this?
The second code segment involves two nested for-loops. wsp and graph are in the same format as master_graph. It loops through each key and then each of the edges (stored in a vector mapped with that key). I know loops can be optimized with 'vectorization', but I'm kinda clueless. Any suggestions?
Code:
% for each node in wsp
%############################################
for it = 1:wsp.Count()
%? for each edge in the graph
key = thekeys{it};
for i = 1:length(graph(key))
thisEdge = graph(key);
thisPoint = thisEdge(i);
if (thisPoint.distance > max_edge_in_prim)
continue;
end
if(terminal(thisPoint.endpoint))
str = sprintf('\tT');
fprintf(str);
cost_of_addition = costFunc(thisPoint.distance, path_length(key));
else
%disp('Not Terminal!');
str = sprintf('\t ');
fprintf(str);
cost_of_addition = (TRENCH_COST * thisPoint.distance);
end
% BENEFIT
% calculate cost one time...
curr_cost = costFunc(thisPoint.distance, path_length(key));
% added (TRENCH_COST *) below
curr_cost = (WC * curr_cost) - (WB * benefit(thisPoint.endpoint));
str = sprintf('( %d , %d) C=%d B=%d T=%d',key,thisPoint.endpoint,costFunc(thisPoint.distance,path_length(key)), benefit(thisPoint.endpoint),curr_cost); fprintf(str);
disp(' ');
% curr_cost holds the overall value of which the min should
% be tracked
if (first || curr_cost < min)
first = 0;
min = curr_cost;
select = thisPoint.endpoint;
node = key;
distance = thisPoint.distance;
node_added = 1;
cost_of_min = cost_of_addition;
end
end
end
Any suggestions would be HUGELY appreciated. I need to speed this thing up anyway possible. The code runs in C++ in under a second. This code takes MINUTES. Hopefully I can avoid embarrassment in my suggestion of translating to matlab. Also, I only have access to R2010b.
Thanks Greg