Improving For loops, Needs speed optimization

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

[Sean de Wolski]

What does the strructure of the text file look like?

[Greg]

The text file is set up in the following format (each point on a seperate line):

Point[SPACE]Point_it_connects_to[SPACE]distance_to_that_point

[Matt Kindig]

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.

[Greg]

That one line will read the entire textfile into a matrix? Since each point is separated on a line, how would that work? Also, I'm not sure how much that would help, because each data point is added to a vector in the map as you can see. So having all points grouped together in a structure wouldn't be much of a help. It needs to loop through each point (check its distance to see if it is the new max) and assign it into the map at the correct location. It must also determine the path back to it, and assign the inverse in the map.

As far as the second part, it loops through each of the keys in wsp (in the same format as master_graph in the previous code) and looks that key up in graph. It then loops through each point in the vector located at that key. It determines if that point is worth adding to the best path. I just was curious if there was a more effective way of implementing this for loop, possibly with vectorization.

Answer 1

[Sean de Wolski]

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]

I will definitely try to implement the new way of doing reads. That, however is not the worse part of the slowdown. The actual finding of the best path is the most important part. I will post an excerpt from the input file, and the correct execution of the for loop on a small example.

[Greg]

Posted

Answer 2

[Greg]

Input file The first line is the cost of putting a cable(this is a cable-trench problem). The second line is ignored. The third line is the number of points, and the fourth line is the number of edges.

1
1
501
24675
1 40 766916
1 43 261202
1 44 467756
1 45 1.53843e+006
1 86 752985
1 89 216916
1 90 1.57769e+006
1 125 860861
1 126 820277
1 128 780598
1 129 741969
1 132 153383
1 133 1.58661e+006
1 166 895684
1 169 696163
1 172 108458
1 173 1.62904e+006
1 199 1.85967e+006
1 200 2.06413e+006
1 203 977329
1 204 957877
1 205 691076
1 208 48504
1 209 1.68791e+006
1 242 1.81096e+006
1 243 1.99752e+006
1 245 1.08458e+006
1 246 1.04143e+006
1 247 689371
1 249 1.89414e+006
1 251 1.45835e+006
1 252 1.7333e+006
1 277 1.23757e+006
1 278 1.19403e+006
1 279 1.15088e+006
1 282 691076
1 283 1.89476e+006
1 285 1.81874e+006
1 286 1.84634e+006
1 287 84011.4
1 288 1.74951e+006
1 316 1.39233e+006
1 317 1.37018e+006
1 318 1.30511e+006
1 321 696163
1 324 1.81356e+006
1 325 1.80771e+006
1 326 1.85143e+006
1 327 108458
1 328 1.79727e+006
1 364 1.46077e+006
1 365 2.13252e+006
1 366 735600
1 370 160870
1 371 1.8622e+006
1 402 716153
1 405 222273
1 406 1.91207e+006
1 441 730786
1 443 1.40996e+006
1 445 286954
1 446 1.97918e+006
1 447 2.04121e+006
1 448 2.05899e+006
1 449 2.12202e+006
1 450 2.14133e+006
1 490 748283
1 492 353114
1 493 2.03081e+006
2 3 108458
2 4 733999
2 5 1.90158e+006
2 6 1.95526e+006
2 7 894369
2 8 999935
2 9 1.26947e+006
2 46 2.06413e+006
2 47 1.37276e+006
2 48 1.84124e+006
2 49 1.82648e+006
2 50 68595
2 51 687663
2 52 1.85397e+006
2 53 963997
2 55 1.33892e+006
2 91 2.06584e+006
2 92 1.43066e+006
2 93 137190
2 94 174884
2 95 692776
2 96 1.03349e+006
2 97 1.80315e+006
2 99 1.37704e+006
2 134 2.06868e+006
2 135 1.48235e+006
2 136 242520
2 137 696163
2 138 1.03916e+006

[Greg]

Round 1 : 

   (1, 172) C=119304 B=0  T= 119304

   (1, 208) C=53354.4 B=0  T= 53354.4

   (1, 287) C=92412.5 B=0  T= 92412.5

   (1, 327) C=119304 B=0  T= 119304

  Select S (1, 208) = 53354.4

Round 2 : 

   (1, 172) C=119304 B=0  T= 119304

   (1, 287) C=92412.5 B=0  T= 92412.5

   (1, 327) C=119304 B=0  T= 119304

   (208, 132) C=167808 B=0  T= 167808

   (208, 172) C=123959 B=0  T= 123959

   (208, 287) C=179195 B=0  T= 179195

  Select S (1, 287) = 92412.5

Round 3 : 

   (1, 172) C=119304 B=0  T= 119304

   (1, 327) C=119304 B=0  T= 119304

   (208, 132) C=167808 B=0  T= 167808

   (208, 172) C=123959 B=0  T= 123959

   (287, 327) C=159466 B=0  T= 159466

   (287, 370) C=234920 B=0  T= 234920

  Select S (1, 172) = 119304

Round 4 : 

   (1, 327) C=119304 B=0  T= 119304

   (208, 132) C=167808 B=0  T= 167808

   (287, 327) C=159466 B=0  T= 159466

   (287, 370) C=234920 B=0  T= 234920

   (172, 89) C=268521 B=0  T= 268521

   (172, 132) C=200871 B=0  T= 200871

  Select S (1, 327) = 119304

Round 5 : 

   (208, 132) C=167808 B=0  T= 167808

   (327, 370) C=183913 B=0  T= 183913

   (327, 405) C=259367 B=0  T= 259367

   (287, 370) C=234920 B=0  T= 234920

   (172, 89) C=268521 B=0  T= 268521

   (172, 132) C=200871 B=0  T= 200871

  Select S (208, 132) = 167808

Round 6 : 

   (327, 370) C=183913 B=0  T= 183913

   (327, 405) C=259367 B=0  T= 259367

   (287, 370) C=234920 B=0  T= 234920

   (132, 43) C=276266 B=0  T= 276266

   (132, 89) C=232417 B=0  T= 232417

   (172, 89) C=268521 B=0  T= 268521

  Select S (327, 370) = 183913

Round 7 : 

   (327, 405) C=259367 B=0  T= 259367

   (132, 43) C=276266 B=0  T= 276266

   (132, 89) C=232417 B=0  T= 232417

   (172, 89) C=268521 B=0  T= 268521

   (370, 405) C=252508 B=0  T= 252508

   (370, 445) C=327962 B=0  T= 327962

  Select S (132, 89) = 232417

Round 8 : 

   (89, 43) C=278911 B=0  T= 278911

   (327, 405) C=259367 B=0  T= 259367

   (132, 43) C=276266 B=0  T= 276266

   (370, 405) C=252508 B=0  T= 252508

   (370, 445) C=327962 B=0  T= 327962

  Select S (370, 405) = 252508

Round 9 : 

   (89, 43) C=278911 B=0  T= 278911

   (132, 43) C=276266 B=0  T= 276266

   (370, 445) C=327962 B=0  T= 327962

   (405, 445) C=321103 B=0  T= 321103

   (405, 492) C=396557 B=0  T= 396557

  Select S (132, 43) = 276266

Round 10 : 

   (370, 445) C=327962 B=0  T= 327962

   (405, 445) C=321103 B=0  T= 321103

   (405, 492) C=396557 B=0  T= 396557

  Select S (405, 445) = 321103

Round 11 : 

   (405, 492) C=396557 B=0  T= 396557

   (445, 492) C=389698 B=0  T= 389698

  Select S (445, 492) = 389698

Round 12 : 

The graph is not connected!

[Matt Kindig]

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);