matlab - What makes this code faster? -

this first question in stackoverflow, ask comprehension might wrong question. also, i'm not native english speaker, i'll try clear possible.

i implementing first fit (ff) heuristic 1-dimensional bin packing problem (bpp) in matlab. after first implementation of algorithm, tried improve code , ended second implementation thought better, since pretty more elegant in opinion. curiosity (let me i'm perfectionist) lead me run , compare both implementations. arrived same result (as should be), first implementation more 10 times faster!

my question is: can me find why that? part of second implementation slowing down code?

thank you.

1st implementation:

function packing = firstfit(items)  global n_items bin_size  item_assign = zeros(n_items,1); residual = bin_size*ones(n_items,1); tmp = residual;  % assign each item on list bin = 1:n_items     j = 1; % start trying first bin     % repeat until item assigned bin     while true         if items(i) > residual(j)             j = j+1; % try fit in next bin          else             residual(j) = residual(j)-items(i);             item_assign(i) = j;             break         end     end end  % check how many bins needed accommodate items n_bins = n_items - sum(residual == tmp);  packing = cell(n_bins,3); = 1:n_bins     packing{i,1} = item_assign == i;     packing{i,2} = items(packing{i,1});     packing{i,3} = residual(i); end  end 

2nd implementation:

function packing = firstfit2(items)  global n_items bin_size  % initialize 1st bin packing{1,1} = false(n_items,1); packing{1,3} = bin_size; n_bins = 1;  % assign each item on list bin = 1:n_items     % first bin able hold item     j = find(cell2mat(packing(:,3)) >= items(i),1);     if isempty(j)         % create new empty bin if necessary         j = n_bins + 1;         packing{j,1} = false(n_items,1);         packing{j,3} = bin_size;         n_bins = j;     end     % assign item bin     packing{j,1}(i) = true;     packing{j,2} = [packing{j,2};items(i)];     packing{j,3} = packing{j,3} - items(i); end  end 

results:

for given dataset, got runtime of 0.011 seconds first implementation while second 1 took around 0.13 seconds complete.

if want, can provide dataset, let me know.

a brief description of bpp:

there set of items having characteristic length each. these items should packed set of bins of fixed size. goal use few bins possible pack items.

a brief description of ff heuristic:

the idea behind first-fit (ff) heuristic simple:

1. items considered sequentially , each of them located first bin can accommodate it.
2. a bin initialized residual capacity r=c, , when item arranged it, residual capacity decreased size of item.
3. if none of open bins can accommodate item, new empty bin created.

your code more complicated needs be. it's not easy why 1 implementation faster other because matlab variety of optimizations behind scenes. loops, , changing size of vector inside loop (as in second code) slow.

the clean matlab way of doing looks like

%% actual work binsize = 20; itemmaxsize = 10; numitems = 10;  items = randi(itemmaxsize, numitems, 1);  r = binsize * ones(numitems, 1); % there can not more bins items assignment = zeros(numitems, 1);  = 1:numitems     assignment(i) = find( r >= items(i), 1, 'first');     r(assignment(i)) = r(assignment(i)) - items(i);  end  r = r( r < binsize );  %% make figure figure hold on = 1:length(r)     iteminds = find(assignment == i);     sizes = items(iteminds);      plot(i, cumsum(sizes), '*')     text(i * ones(size(sizes)) + .1, cumsum(sizes), num2str(iteminds)) end   ylim([0 round(binsize*1.1)]) plot([.5 length(r)+.5], [binsize binsize], '--') xlim([.5, length(r)+.5]); set(gca, 'xtick', 1:length(r)) xlabel('bin ind') ylabel('fill')