Speeding up dynamic programming code

2 vues (au cours des 30 derniers jours)
Paolo Binetti
Paolo Binetti le 13 Juin 2017
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)

Réponses (0)

Catégories

En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by