3 ms·
Hmm, interesting. The classic dynamic programming edit distance algorithm uses linear space (with a far better constant factor than this algorithm) and quadrat
by amluto 10y ago
Hmm, interesting. The classic dynamic programming edit distance algorithm uses linear space (with a far better constant factor than this algorithm) and quadratic time. You build a table c where c[i][j] is the edit distance from the first I characters of file 1 to the first j characters of file 2. (You don't need to store the whole table.) There's a cute trick to get the actual diff out without using more space (by rerunning the algorithm a few times on portions of the input). To get below quadratic time on sensible input, IIRC, the standard approach is to think of the problem a bit like Dijkstra's algorithm and fill in the table in order by value, smallest edits first.
I imagine you get to linear time without much loss by heuristically throwing out chunks of the table where i is far from j.
The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file?
- DannyBee 10y ago"The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file? " No. Well, in theoretical time bound, no. In practice, also no :) On hackernews, maybe! You can't just throw out unique lines, they may be in the middle of a replacement. IE a e c a d c Note: edit distance is zero until unique line occurs :( But what if you just start at the unique lines and edit distance from there, somehow ignoring the equal lines? This is basically just transforming it into another problem with the same time bound, where that problem is "where is the next/previous point in the file where the streams misalign, if i assume it was aligned before point x". Sadly, this problem is not any faster to solve. For simple proof, think of it this way: The unique line info just tells you, for sure, that the next alignment point is at least N characters away, where N is the line length, when you are staring at a given character. This is, at best, a constant factor faster, where the constant factor is the average line length * number of unique lines or something like that. It's actually just an application of the boyer-moore trick. But it's still not theoretically faster, because edit distance is really just a stream alignment algorithm where, instead of stopping, you just keep counting how misaligned they are. IE edit distance is already a measure of stream alignment, and it's already a very fast one. Now, you could make a diff algorithm out of the above if you wanted. Find unique lines, or also lines with count mismatches between a and b (since they are at least adds or deletes). Starting from there, segment file into pieces by stream misalignment points. This is equivalent to splitting the file into segments, where each segment has the same edit distance. While computing, hash each aligned segment to map to where it appears on each side (we need to know where it moved to, and this is a single O(N) pass anyway). Now you know, for everything that moved, where it moved to, for everything that's the same, where they start and end being the same, etc. From that you can output add, remove, changed as you will. If this sounds familiar, it's because it's what the algorithms do already for the most part, you are just starting the diff in a different place. Edit distance can already be done in O(s * min(m,n )) time, where s is the maximum edit distance (which is still O(mn) if the file has completely changed). That's going to be hard to beat. Truthfully, the real good stream alignment algorithms you would want to look at here at the various algorithms used to do gene sequence alignment :) But it's not going to be faster unless you are diffing gigabytes of text. Only better in the sense that they use heuristics to do better than edit distance when there are multiple possible points of alignment for a given piece of text. (IE diff falls down, among other places, where a piece of code could validly have been said to be duplicated to two places. Usually it will notice one of them, and consider the other a replacement or an add of brand new text. Using those algorithms, or the above would let you augment this by saying "it's not an add of really new text, I duplicated thing X to two new places")
- hairtuq 10y agoYes, you can. There's an algorithm running in O((r+l) log l) time, where l is the number of lines and r is the total number of ordered pairs of line numbers at which the two files match [1]. So if all lines are unique, this runs in O(l log l). [1] J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5):350–353, 1977.
- DannyBee 10y agoAs the paper itself says, this is still N^2 log N worst case :) Note that these are all variants of general algorithm I posted, and more generally, variants of tricks used in boyer-moore (though hunt's work predates boyer-moore, that's the easiest way to describe it), which means they try to skip parts of the text they can prove can't match. Because they can't always do so, they don't change the worst case time bound, only various other time bounds.
- austincheney 10y ago> I imagine you get to linear time without much loss by heuristically throwing out chunks of the table where i is far from j. I originally tried a delete as you go approach to the hash map where you remove entries that were no longer needed, such as when both values (counts) for a given key reached 0. My thinking was that this would improve execution speed over the space of a very large table by gradually reducing the key space and thus reducing look up times. This thinking proved false against two 1.7mb code samples. Removing this set of instructions reduced execution time from an average of 0.95 seconds to an average of 0.71 seconds (on my machine and browser). It is simply more efficient to read from a large hash map than it is modify that hash map to improve reading efficiency. A better approach, which I have not tried, would be to reduce writes to the hash map at the time of running through the second code sample, because you have already gone through the first code sample and not yet performed your formal analysis. To be efficient enough for a valid performance improvement though the analysis at this point would have to be tiny and yet somehow benefit for the formal analysis coming in the next step. The underlying assumption is that having a smaller hash map means fewer writes to memory. To be helpful to the next step of formal analysis the loop would have to achieve fewer iterations. > The article raises an interesting question: can you improve this by using advantage of the fact that lines of code have a decent chance of being unique or nearly unique within a file? As a code author I cannot predict user behavior and do not try. Instead I make assumptions upon that behavior and execute to these assumptions, whether or not they are valid. My assumption is that if a user wishes to compare unrelated things the number of differences sky-rockets, which means a bit more computation and temporary data. I suspect that if a user does this it is probably for some exploratory reason and thus are better prepare for the trivial increase in processing.