![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
One of the DP problems I alluded to in my last post is minimum edit distance: how many one-letter changes does it take to turn text string A into string B? Skiena gives a simple recursive solution, which is described incorrectly in the text but correctly as code. I'd coded my own version in C, and it worked, slowly. Then I memoized it by hand and it worked, much faster. Then more recently, as I practice Python by translating my C and Perl programs into it, I did a Python naive code, which worked, slowly. Then I memoized it with the lru_cache decorator, and it worked much faster. All is well.
But often you'd want to know an actual path of edits to make, not just how long the distance is. Skiena gives a full DP solution, filling one table of 'cached' lengths and another one of 'last moves', which you can then use to reconstruct the path. Skiena himself says it can be a bit tricky to get the boundaries and such right. I decided to try to get paths myself, but with the recursive version.
At first I was thinking in terms of last-move tables too, and worrying that I might need the memoization table hidden by the lru_cache. But then I thought, "no, this is all wrong, I should be thinking about a pure recursive solution first." And in a flash it came to me: the best path is the previous best path, plus whatever the current move is. Plus a base case, of course. That's it! Like all good recursive solutions it feels magical or cheating, like you're punting the work somewhere else indefinitely, but it does work, with pretty transparent code. Yay! Magic!
But magic has its price. I tried timing the code as inputs scaled, especially making two strings of length N and doubling N. "Oh no, it's exponential! Nx2, time x8! No wait, that's cubic, whew." But the algorithm is supposed to be quadratic, O(N^2) not O(N^3).
Well, I can guess why. Recursive programming makes clear and correct code easy, at the cost of often slinging copies of lists or strings around. If there are N^2 steps but each one is taking N steps of its own to copy or hash a string, that's cubic. And it looked like my code was copying path strings a lot; also, memoization works by hashing arguments, I think.
So when I was lying awake in bed thinking on the problem, I imagined this post was going to be a happy story of how I made a couple of tweaks and got my running time down. Sadly, that has not been the case. The string arguments never change, so I lifted them out of the function that gets memoized, but that didn't make much difference. Maybe it was already looking at their addresses and not their contents? I also tried building my paths up in lists rather than strings, but so far that's not correct. I suspect some sort of reference collision but haven't solved it yet, even by returning whole-list slices. And as a side project, I tried making a more concise version of the string-path code, but it took twice as long. I've clawed some of that back but it still takes 30-40% more time than the original.
I was surprised to find that avoiding using the min() function, even on an array of 3 items, in lieu of chained if..then, made a big difference. I'm guessing any function call is expensive.
I'm having bad flashbacks to my one 'big' Haskell class project (in an algorithms class, even), which was clearly non-optimal but also really hard to improve from its original form.
Well, today's frustration about code optimization aside, I can still be happy that the recursive path-finding magic works. The next related project is whether I can find similarly simple solutions to the related problems Skiena adapted his DP solution to solve, like approximate substring matching.
Also good to know: for deep recursion, you can and in fact have to modify Python's stack and recursionlimit in your code, no apparent need to mess with ulimit from the shell. Right now I'm setting the recursionlimit as a function of N...
But often you'd want to know an actual path of edits to make, not just how long the distance is. Skiena gives a full DP solution, filling one table of 'cached' lengths and another one of 'last moves', which you can then use to reconstruct the path. Skiena himself says it can be a bit tricky to get the boundaries and such right. I decided to try to get paths myself, but with the recursive version.
At first I was thinking in terms of last-move tables too, and worrying that I might need the memoization table hidden by the lru_cache. But then I thought, "no, this is all wrong, I should be thinking about a pure recursive solution first." And in a flash it came to me: the best path is the previous best path, plus whatever the current move is. Plus a base case, of course. That's it! Like all good recursive solutions it feels magical or cheating, like you're punting the work somewhere else indefinitely, but it does work, with pretty transparent code. Yay! Magic!
But magic has its price. I tried timing the code as inputs scaled, especially making two strings of length N and doubling N. "Oh no, it's exponential! Nx2, time x8! No wait, that's cubic, whew." But the algorithm is supposed to be quadratic, O(N^2) not O(N^3).
Well, I can guess why. Recursive programming makes clear and correct code easy, at the cost of often slinging copies of lists or strings around. If there are N^2 steps but each one is taking N steps of its own to copy or hash a string, that's cubic. And it looked like my code was copying path strings a lot; also, memoization works by hashing arguments, I think.
So when I was lying awake in bed thinking on the problem, I imagined this post was going to be a happy story of how I made a couple of tweaks and got my running time down. Sadly, that has not been the case. The string arguments never change, so I lifted them out of the function that gets memoized, but that didn't make much difference. Maybe it was already looking at their addresses and not their contents? I also tried building my paths up in lists rather than strings, but so far that's not correct. I suspect some sort of reference collision but haven't solved it yet, even by returning whole-list slices. And as a side project, I tried making a more concise version of the string-path code, but it took twice as long. I've clawed some of that back but it still takes 30-40% more time than the original.
I was surprised to find that avoiding using the min() function, even on an array of 3 items, in lieu of chained if..then, made a big difference. I'm guessing any function call is expensive.
I'm having bad flashbacks to my one 'big' Haskell class project (in an algorithms class, even), which was clearly non-optimal but also really hard to improve from its original form.
Well, today's frustration about code optimization aside, I can still be happy that the recursive path-finding magic works. The next related project is whether I can find similarly simple solutions to the related problems Skiena adapted his DP solution to solve, like approximate substring matching.
Also good to know: for deep recursion, you can and in fact have to modify Python's stack and recursionlimit in your code, no apparent need to mess with ulimit from the shell. Right now I'm setting the recursionlimit as a function of N...