Comparing the contents of very large files efficiently
<p>I need to compare two files of differing formats quickly and I'm not sure how to do it. I would very much appreciate it if someone could point me in the right direction.</p>

<p>I am working on CentOS 6 and I am most comfortable with Python (both Python 2 and Python 3 are available).</p>

<hr>

<h2>The problem</h2>

<p>I am looking to compare the contents two large files (quickly). The files, unfortunately, differ in content; I will need to modify the contents of one before I can compare them. They are not particularly well-organized, so I can't move linearly down each and compare line-by-line.</p>

<p>Here's an example of the files:</p>

<pre>
<i>File 1                    File 2</i>
Job,Time                  Job,Start,End
0123,3-00:00:00           0123,2016-01-01T00:00:00,2016-01-04T00:00:00
1111,05:30:00             1111,2016-01-01T00:00:00,2016-01-01T05:30:00
0000,00:00:05             9090.abc,2016-01-01T12:00:00,2016-01-01T22:00:00
9090.abc,10:00:00         0000,2015-06-01T00:00:00,2015-06-01T00:00:05
...                       ...
</pre>

<p>I would like to compare the contents of lines with the same "Job" field, like so:</p>

<pre>
<i>Job        File 1 Content   File 2 Content</i>
0123       3-00:00:00       2016-01-01T00:00:00,2016-01-04T00:00:00
1111       05:30:00         2016-01-01T00:00:00,2016-01-01T05:30:00
0000       00:00:05         2015-06-01T00:00:00,2015-06-01T00:00:05
9090.abc   10:00:00         2016-01-01T12:00:00,2016-01-01T22:00:00
...        ...              ...
</pre>

<p>I will be performing calculations on the <i>File 1 Content</i> and <i>File 2 Content</i> and comparing the two (for each line).</p>

<p>What is the most efficient way of doing this (matching lines)?</p>

<hr>

<p>The system currently in place loops through one file in its entirety for each line in the other (until a match is found). This process may take hours to complete, and the files are always growing. I am looking to make the process of comparing them as efficient as possible, but even marginal improvements in performance can have a drastic effect.</p>

<p>I appreciate any and all help.</p>

<p>Thank you!</p>

<p>The most efficient way I can think of is to use some standard UNIX tools which every modern Linux system should have. I know that this is not a python solution, but you determination to use python seems to build mostly on what you already know about that language and not any external constraints. Given how simple this task is using UNIX tools I will outline that solution here.</p>

<p>What you're trying to do is a standard database-style join where you look up information in two tables which share a column. For this the files must be sorted, but UNIX <code>sort</code> uses an efficient algorithm for that and you will not get around sorting or copying your file into a data structure which implies some sort of sorting.</p>

<p>Long version for demonstration</p>

<pre><code>tail -n+2 file1.csv | LC_ALL=C sort -t , -k 1  &gt; file1.sorted.csv
tail -n+2 file2.csv | LC_ALL=C sort -t , -k 1  &gt; file2.sorted.csv
join -a 1 -a 2 -t , -1 1 -2 1 file1.sorted.csv file2.sorted.csv \
   &gt; joined.csv
</code></pre>

<p><code>tail -n+2</code> cuts off the first line of the file which contains the headers. <code>-t ,</code> parts are to set comma as columns separator, <code>-k 1</code> means sort on first column. <code>-1 1 -2 1</code> means "Use the first column of the first file and the first column of the second file as shared columns of the two files". <code>-a 1 -a 2</code> means "Also output lines from file 1 and file 2 for which no matching line can be found in the other file. This relates to a "full outer join" in database lingo. See <a href="http://unix.stackexchange.com/questions/120096/how-to-sort-big-files">this SO question</a> and others for <code>LC_ALL=C</code></p>

<p>If you want to avoid saving temporary files, you can sort on-the-fly using bash's "Process substitution" <code>&lt;( ... )</code></p>

<pre><code>join -a 1 -a 2 -t , -1 1 -2 1 \
    &lt;( tail -n+2 file1.csv | LC_ALL=C sort -t , -k 1 ) \
    &lt;( tail -n+2 file2.csv | LC_ALL=C sort -t , -k 1 ) \
    &gt; joined.csv
</code></pre>

<p>Note that <code>sort</code> supports multiple cores (see <code>--parallel</code> in <code>man sort</code>) If your files are so big that sorting the file on one machine takes longer than splitting it up, sending the chunks across the network, sorting them on multiple machines, sending them back and merging the sorted parts, refer to <a href="https://blog.mafr.de/2010/05/23/sorting-large-files/" rel="nofollow">this blog-post</a>.</p>

python performance file io