Improving For loops, Needs speed optimization
3 views (last 30 days)
Show older comments
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)
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?
% 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
4 Comments
Matt Kindig
on 8 Oct 2012
Edited: Matt Kindig
on 8 Oct 2012
To read the file into a matrix (assuming no header lines):
Data = dlmread( '/path/to/your/file.txt', 'Delimiter', ' ');
For the second part, I'm not as clear as to your objective. What are you trying to do exactly? I can see that you "loop through each key and then each of the edges", but the purpose is less clear to me.
Answers (2)
Sean de Wolski
on 8 Oct 2012
File reads take awhile. Read the whole thing in using dlmread and reshape/transpose as necessary. A for-loop over an existing matrix to determine distances etc. (or just a simple max()) will be much faster.
Also, if you can give us a small example, say the first 60 lines of your file, and what you expect as a result, we might be able to help you with something tricky to bypass the loops.
Greg
on 8 Oct 2012
2 Comments
Matt Kindig
on 9 Oct 2012
Hmmm, I'm still not really sure what your code is supposed to be doing. Like, for example, I'm not sure where max_edge_in_prim is set. Can you explain to us verbally what your algorithm is supposed to be doing? We might be able to offer an alternative approach that takes better advantage of Matlab's capabilities.
By the way, to extract all of the information from the file that you specified, you can do something like this:
fid = fopen('/path/to/your/file.txt', 'rt');
if fid < 3,
error('Unable to open file');
end
frewind(fid);
Cost = str2double(fgetl(fid)); %cost of cable
fgetl(fid); %skip next line
NPoints = str2double( fgetl(fid)); %number of points
NEdges = str2double( fgetl(fid)); %number of edges
Data = textscan(fid, '%d %d %d', 'CollectOutput', true);
Data = Data{1}; %this is your actual data, as one matrix
fclose(fid);
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!