2 ms·
You assumed the diff algorithm only compares each line against one other line. That's not true. You look at each line many times in these algorithms. Running t
by ajuc 6y ago
You assumed the diff algorithm only compares each line against one other line. That's not true.
You look at each line many times in these algorithms. Running time is O(n log n) or O(n^2) not O(n).
So you generate N hashes and compare each hash against log N or N other hashes.
So, for big enough data it should be faster.
- OskarS 6y agoNo, you misunderstand: he mentions a common optimization where before you run your diffing algorithm, you find the common line suffix/prefix for the file, and how that will improve performance (if you have a compact 5-line diff in a 10,000 line file, it's unnecessary to run the diffing algorithm over the whole thing). His point was that this suffix/prefix finding thing was surprisingly slow totally apart from the actual diffing. I was talking about that part, how hashing there is unnecessary. As I mentioned at the end of my comment, for the actual diffing algorithm, it's fine to hash away.