On Wed, Jan 15, 2014 at 10:49 AM, Matthias BUSSONNIER < [email protected]> wrote:
> > > Le 14 janv. 2014 à 21:02, Shashwat Anand a écrit : > > > >> I just found that trying to consume the minimal memory (n+1) was > significantly > >> slower than using (2n) IIRC. > >> > > Just someone curious here. > > > > Assuming two strings of length M and N, we can do the naive edit > distance via dynamic programming, > > in O (MN) time and O (MN) space. > > > > However since only last row is used to determine the result, we can save > the space by using O (N) memory, > > which is basically 2*N memory. > > > > What I don't understand is, what is this minimal memory (n + 1) you just > mentioned ? > > > Assuming you have computed row P from 1 to Q (included) , you don't need > the values > of row P-1 from 1 to Q (excluded) anymore. So you can use a circular > buffer. > So you store Q+N-(Q-1) = N+1 values. > > Awesome ! I never thought, we can use circular buffer like this. Quite nifty an approach it is. Why is it slow then ? Is it due to % operator ? See https://en.wikipedia.org/wiki/Longest_common_subsequence_problem > Reduce the required space section (they don't explain why exactly but once > you > see the matrix you'll get it) > > This one is textbook, use 2 rows and keep on alternating between them. A lot of problems like Longest Common Subsequence, Shortest Common Supersequence etc are solved via this. Also this technique is fairly common in programming competitions. I also found that "Dynamic Programing" is an over-used term. > Why ? I have heard this at some other places too. Is this because it is a really broad category ? For example, a lot of graph theory falls under same area. On an unrelated note, I like writing a recursive code and then simple memoizing it. Seems to me the best way to convert a tree to directed acyclic graph. But cases like these are where we need table, where we need to save space. Or probably we can save space using recursion too, I am not aware of it though ? > -- > M > > > > > >
