MATLAB: Is it possible to vectorize this

MATLABvectorization

A = [starts ends];
b = zeros(size(A,1),1);
c = zeros(size(A,1),1);
for i = 1:1:size(A,1)
    b(i) = max(x(A(i,1):A(i,2)));
    c(i) = min(x(A(i,1):A(i,2)));
end

starts, ends and x are column vectors. The intervals does not overlap.

Best Answer

There is no general way to vectorize this. If the starts and ends vector define intervals that are not overlapping, and that cover every index in x, you can do the following:

ind = zeros(length(x), 1);
for i=1:size(A, 1)
    ind(starts(i):ends(i)) = i;
end
% ind(j) gives the number of the interval that j (and x(j)) are in.
b = accumarray(ind, x(:), [], @max);
c = accumarray(ind, x(:), [], @min);

Depending on where starts and ends are coming from, maybe you can construct ind in a vectorized format from there?

Related Solutions

MATLAB: Numerical packing

Thank you Sean, Elige, for your responses, and thanks Walter for naming the problem I'd posed. Even after seeing it as a "knapsack" problem, I had difficulty adopting one of the FEX knapsack solutions to this particular problem out of the box, so I also made a solution of my own (below).

Here are some codes, times, and comments:

My solution: (sorry about the line wrapping... I use a wider MATLAB page size than this website)

function grps = orderedMinOfMaxKnapsackSums(A, lim)
% Discover how many knapsacks (or groups) to use
grps = zeros(size(A));
while any(grps==0)
    openIdxs = find(grps==0);
    mask = cumsum(A(openIdxs))<lim;
    grps(openIdxs(mask)) = max(grps)+1;
end
numGrps = max(grps);
% Build all possible indice pairs for each group
maxInds = arrayfun(@(i)find(grps==i,1,'last'),1:numGrps);
grpIndPairs = arrayfun(@(mn,mx)[mn mn; nchoosek(mn:mx,2); mx mx], 1:numGrps, maxInds, 'Un',0);
% Ensure that the first group "starts" at 1, and the last group "ends" at the length of A
grpIndPairs{1}(grpIndPairs{1}(:,1)>1,:) = [];
grpIndPairs{end}(grpIndPairs{end}(:,2)<length(A),:) = [];
% Remove the "possible" indice pairs that over-fill that knapsack
grpIndPairs = cellfun(@(pair)pair(arrayfun(@(fr,to)sum(A(fr:to)), pair(:,1),pair(:,2))<lim, :), grpIndPairs, 'Un',0);
% Reduce the "possible" indice pairs to those with valid adjacent knapsack possibilities. For
% example, if knapsack 1 only holds indices 1:2 or 1:3, knapsack 2 must start at element 3 or 4.
while 1
    oldNumels = cellfun(@numel, grpIndPairs);
    grpIndPairs(1:end-1) = cellfun(@(this,next)this(ismember(this(:,2), next(:,1)-1),:),...
        grpIndPairs(1:end-1), grpIndPairs(2:end), 'Un',0);
    grpIndPairs(2:end) = cellfun(@(this,last)this(ismember(this(:,1), last(:,2)+1),:)  ,...
        grpIndPairs(2:end), grpIndPairs(1:end-1), 'Un',0);
    if isequal(oldNumels, cellfun(@numel, grpIndPairs)), break;  end
end
% Build the set of all possible combinations from each of the groups
elNumsCell = cellfun(@(x)1:size(x,1), grpIndPairs, 'UniformOutput', false);
grpIndsCell = cell(size(elNumsCell));
[grpIndsCell{:}] = ndgrid(elNumsCell{:});
allCombs = cell2mat(arrayfun(@(i)grpIndPairs{i}(grpIndsCell{i}(:),:),1:numGrps,'Un',0));
% Remove combinations where knapsack elements don't immediately follow the previous knapsack
combsDiff = diff(allCombs,[],2);
allCombs = allCombs(all(combsDiff(:,2:2:end)==1, 2), :);
% Calculate the size of each knapsack for all the combinations that remain
combSums = zeros(size(allCombs,1),numGrps);
for i = 1:numGrps
    combSums(:,i) = arrayfun(@(fr,to)sum(A(fr:to)), allCombs(:,2*(i-1)+1), allCombs(:,2*(i-1)+2));
end
% Choose the best combination
[~, bestCombIdx] = min(max(combSums,[],2));
grps = cell2mat(arrayfun(@(i)i*ones(1,1+diff(allCombs(bestCombIdx,2*(i-1)+(1:2)))), 1:numGrps,'Un',0));
end

And here's Elige's solution:

function best_combo = bruteForce(A, lim)
intmax = prod(A);
% WEIGHT 
%   >0.5 weight STD of sum more heavily 
%   <0.5 weight difference of lim and MEAN of sum more heavily 
weight = 0.5; 
best_combo = zeros(1,length(A));
best_fit = intmax;
for i = 1 : length(A)-1
  B = nchoosek(1:length(A)-1,i);
  for j = 1 : nchoosek(length(A)-1,i)
      C = (i+1)*ones(1,length(A));
      for k = sort(1 : i,'descend')
          C(1:length(A)<=B(j,k))=k;
      end
      fit = (std(arrayfun(@(k)sum(A(C==k)),1:i+1))*(weight))^2 + ...
            ((lim-mean(arrayfun(@(k)sum(A(C==k)),1:i+1)))*(1-weight))^2;
      if sum(arrayfun(@(k)sum(A(C==k)),1:i+1)>lim) == 0 && fit < best_fit
          best_fit = fit;
          best_combo = C;
      end
  end
end
end

Here are some timings:

A = [235 235 235 234 235 235 234 234 234 220 280 215 234]
lim = 1000
tic, for i = 1:10
orderedMinOfMaxKnapsackSums(A, lim);
     end, toc
tic, for i = 1:10
bruteForce(A, lim);
     end, toc

Elapsed time is 0.053719 seconds.

Elapsed time is 338.265262 seconds.

Elige, I know I stated that I was dealing with small data sets so efficiency wasn't an issue - but I think the brute force method here ran for a bit longer than I was anticipating.

Sean, I don't have the GO toolbox so I can't test out your solution. Can you post a little speed summary here for us?

Walter, I had a bit of trouble fitting my particular problem into one of the FEX knapsack entries. It seems that they had in-built criterion to optimise (whereas my criterion was to minimise the maximum knapsack size), so I went ahead making my own solution as an exercise. Did I miss something obvious that could have saved time?

So anyway Sean, you get the accepted answer... I'm tempted to accept my own but it doesn't meet my own criteria (of short and sweet) and want to at least give you guys the credit for tackling someone else's problem :)

MATLAB: Overlapping time-intervals

Hi Rostislav

It looks like you want the union of closed intervals. Here is some code that I think does the job. When the ends of intervals have the same value, it works because the sort function is stable and preserves ordering for ties.

% Nx2 matrix of endpoints x1, x2 of intervals
x = [8 10; 2 4; 4 5; 5 7; 9 11; 15 16; 14 17; 10 12]
% -----plot it first
nline  = repmat((1:size(x,1))',1,2);
plot(x',nline','o-')
ylim([-.5*nrow 1.5*nrow])
% ----- find union of intervals
x = sort(x,2);
nrow = size(x,1); 
[x ind] = sort(x(:));
n = [(1:nrow) (1:nrow)]';
n = n(ind);
c = [ones(1,nrow) -ones(1,nrow)]';
c = c(ind);
csc = cumsum(c);          % =0 at upper end of new interval(s)
irit = find(csc==0);
ilef = [1; irit+1];
ilef(end) = [];           % no new interval starting at the very end 
% y matrix is start and end points of the new intervals, y1,y2
%
% ny matrix is the corresponding indices of the start and end points
% in terms of what row of x they occurred in.
   y = [x(ilef) x(irit)]
  ny = [n(ilef) n(irit)]

Best Answer

Related Solutions

MATLAB: Numerical packing

MATLAB: Overlapping time-intervals

Related Question