Speeding up dynamic programming code

Paolo Binetti

2017 6 13

0 个回答

2 次查看（30 天）

0 个投票

Is there a way to speed up this piece of code implementing a dynamic programming algorithm?

% sample input
v = repmat('CGACAGCTACTCACTCAGTAGCCGCAGCGAGTGTCTTGACAATTCGGAGGGG', 1, 20);
w = repmat('TATACACATTCATGAATGAAAATTGACCTCCTACAGTTGTAGTGGTAGT', 1, 20);
n = numel(v);
m = numel(w);
s = zeros(n+1, m+1);
back = zeros(n, m);
for i = 1:n
  temp = s(i, 1:end-1)+(v(i)==w);
  for j = 1:m
    [s(i+1, j+1), back(i, j)] = max([s(i, j+1) s(i+1, j) temp(j)]);
  end
end

(Memory is also an issue when scaling up, due to the size of arrays "s" and "back", but I have found a way to reduce "s" to just two lines, and "back" could be expressed as uint8)