MATLAB: Selecting submatrix takes long

indexingmatrixspeed

I am working on a TSP tour construction algorithm, where distances are saved in a distance matrix D, and the tour is represented as a permutation of the n cities.
It starts with a partial tour of two nodes, and from then on it keeps adding an unvisited city until the partial tour contains all cities.
To decide which city to add to the current partial tour, I need a submatrix from the D distance matrix. However, this operation, as it turns out, takes about 90% of full running time. Is there any way to speed this up?
Here is part of my code: (the line that takes most time is the one that defines 'searchArea'
    while numel(tour) < n-1
       searchArea = D(nodesLeft,tour); %submatrix that needs to be investigated
       
       addCity = findCity(searchArea); %find the city that should be added
       addCity = nodesLeft(addCity); %convert 'addCity' from an idx to city number
       tour = insertCity(D,tour,addCity); %insert city in partial tour appropriately
       nodesLeft = nodesLeft(nodesLeft~=addCity);% update which cities are left over
    end
EDIT:
nodesLeft is a shrinking vector containing all numbers not yet in tour.
similarly tour is a growing vector containing all numbers 1:n except for what is in nodesLeft

Best Answer

The growing and shrinking of array is expensive, because Matlab has to allocate new arrays each time and copy the old contents (except for the deleted element). Usually it is cheaper to use arrays with constant sizes and a logical vector, which contain a true for cities, which are selected.
This might forward the creation of submatrices to the subfunctions, such that it depends on the implementation of the not shown functions like findCity. Without seeing the full code, it is hard to guess, if the "90%" can be avoided or to suggest working code.
Related Question