Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm trying to compare two text files. I want to compute how many lines were added and removed. Basically what git diff --stat is doing. Bonus points for not having to store the entire file contents in memory.

The approach I'm currently having in mind is:

  1. read each line of the old file
  2. compute a hash (probably MD5 or SHA-1) for each line
  3. store the hashes in a set
  4. do the same for each line in the new file
  5. every hash from the old file set that's missing in the new file set was removed
  6. every hash from the new file set that's missing in the old file set was added

I'll probably want to exclude empty and all white space lines. There is a small issue with duplicated lines. This can either be solved by additionally storing how often a hash appears or comparing the number of lines in the old and new file and adjust either the added or removed lines so that the numbers add up.

Do you see room for improvements or a better approach?

Edit

I'm currently using Java and the SVNKit library.

share|improve this question
    
It seems you do not to not care for the order of lines - is that intentional? –  Doc Brown Oct 29 '12 at 14:17
    
Right, I don't care about the order. –  Philippe Marschall Oct 29 '12 at 16:24
    
Actually, if you don't care about the order, your algorithm outline seems to be the standard approach for solving this problem. Simple to implement, and as fast as it can be. Note that using hashes only, without comparing the original data, leaves you with a slight risk of hash collisions of non-identical lines. Of course, if you have really big files to process, you may reach memory limits. –  Doc Brown Oct 29 '12 at 16:36
add comment

2 Answers 2

Since this is something quite common among diff tools, why not use a tried-and-tested diff library to do the work efficiently instead of rolling out your own code?

Searching for "diff library" or "diff tools" with the name of the language would provide some easier ways.

share|improve this answer
1  
I'm currently parsing the output of svn diff. But I'm not happy with the performance, I'm doing it over the entire repository. Since I actually need less information than svn diff I figured there must be a quicker way to do it. –  Philippe Marschall Oct 29 '12 at 11:18
1  
@PhilippeMarschall The answer does not suggest using the diff in a separate process, but rather taking an existing diff library, and embedding it in your code. This will improve performance, because no new process would be created for each pair of files that you are diff-fing. –  dasblinkenlight Oct 29 '12 at 11:53
    
I'm already calling svn diff in-process. –  Philippe Marschall Oct 29 '12 at 11:55
2  
but you are creating an sub-process and let svn diff do unnecessary work. a library is something you use natively inside your program code. example is code.google.com/p/google-diff-match-patch –  Jan Prieser Oct 29 '12 at 13:01
1  
@JanPrieser I'm calling the diff code of a Subversion library in-process. I'm not forking a new process. –  Philippe Marschall Oct 29 '12 at 16:21
show 3 more comments
svn diff | diffstat

This gives you the same thing as git diff --stat does.

If this is not an option for you, then maybe a good alternative is to parse the output of svn diff: count the lines starting with + and -, keep in mind that for each affected files there will be lines starting with +++ and ---.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.