Filter a large file quickly The challenge is to filter a large file quickly.  


Input: Each line has three space separated positive integers. 
Output: All input lines A B, Tthat satisfy either of the following criterion.


There exists another input line C, D, U where D = A and 0 &lt;= T - U &lt; 100.
There exists another input line C, D, U where B = C and 0 &lt;= U - T &lt; 100.



To make a test file use the following python script which will also be used for testing. It will make a 1.3G file. You can of course reduce nolines for testing.

import random    
nolines = 50000000 # 50 million
for i in xrange(nolines):
    print random.randint(0,nolines-1), random.randint(0,nolines-1), random.randint(0,nolines-1)


Rules. The fastest code when tested on an input file I make using the above script on my computer wins.  The deadline is one week from the time of the first correct entry.

My Machine The timings will be run on my machine. This is a standard 8GB RAM ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Some relevant timing information  

Timings updated to run the following before each test.

sync &amp;&amp; sudo bash -c 'echo  3 &gt; /proc/sys/vm/drop_caches'

time wc test.file

real    0m26.835s
user    0m18.363s
sys     0m0.495s

time sort -n largefile.file  &gt; /dev/null

real    1m32.344s
user    2m9.530s
sys     0m6.543s


Status of entries

I run the following line before each test.

sync &amp;&amp; sudo bash -c 'echo  3 &gt; /proc/sys/vm/drop_caches'



Perl (Waiting for bug fix.)
Scala 1 minutes 37 seconds by @James_pic. (Using scala -J-Xmx6g Filterer largefile.file output.txt)
Java. 1 minute 23 seconds by @Geobits. (Using java -Xmx6g Filter_26643)
C. 2 minutes 21 seconds by @ScottLeadley.
C. 28 seconds by @James_pic.
Python+pandas. Maybe there is a simple "groupby" solution?
C. 28 seconds by @KeithRandall.


The winners are Keith Randall and James_pic.

I couldn't tell their running times apart and both are almost as fast as wc!
C, ~ 7 4.1 seconds

Radix sort on T, then walk through the array looking for matches.

It is fast because it is cache friendly.  The radix sort reasonably so, and the final walk very.  I have to check each row against about 100 others, but they are all adjacent in the cache.

Added: I no longer have to check each row against a scan of 100 other rows.  A small table of counts of low order bits of b's in the window suffices to eliminate most instances of this scan.

Now about 1/2 time parsing, 1/3 time sorting, 1/6 time doing the actual matching.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;sys/mman.h&gt;
#include &lt;fcntl.h&gt;

// B = # of bits per radix pass
// R = # of radix passes
#define B 9
#define R 3
#define M ((1&lt;&lt;B)-1)
#define MAXN 50000000

int count[R][1&lt;&lt;B];

typedef struct {
  int a,b,t,print;
} entry;

entry A[MAXN];
entry C[MAXN];

// Sized to fit well in L1 cache
unsigned char bcount[16384];

int main(int argc, char *argv[]) {
  FILE *f = fopen(argv[1], "r");
  fseek(f, 0, SEEK_END);
  int size = ftell(f);
  fclose(f);

  int fd = open(argv[1], O_RDONLY);
  const char *p = (const char*)mmap(0, size, PROT_READ, MAP_SHARED, fd, 0);
  const char *endp = p + size;

  // parse, insert into array
  int n = 0;
  while(p &lt; endp) {

    // parse line
    int a = 0;
    while(*p != ' ') {
      a *= 10;
      a += *p - '0';
      p++;
    }
    p++;
    int b = 0;
    while(*p != ' ') {
      b *= 10;
      b += *p - '0';
      p++;
    }
    p++;
    int t = 0;
    while(*p != '\n') {
      t *= 10;
      t += *p - '0';
      p++;
    }
    p++;

    // insert it
    if(n == MAXN) {
      printf("too many elements\n");
      exit(1);
    }
    A[n].a = a;
    A[n].b = b;
    A[n].t = t;
    n++;

    // compute counts for radix sort
    count[0][t&amp;M]++;
    count[1][(t&gt;&gt;B)&amp;M]++;
    count[2][t&gt;&gt;2*B]++;
  }

  // accumulate count entries
  for(int r = 0; r &lt; R; r++) {
    for(int i = 0; i &lt; M; i++) {
      count[r][i+1]+=count[r][i];
    }
  }

  // radix sort, 3 rounds
  for(int i = n-1; i &gt;= 0; i--) {
    C[--count[0][A[i].t&amp;M]] = A[i];
  }
  for(int i = n-1; i &gt;= 0; i--) {
    A[--count[1][(C[i].t&gt;&gt;B)&amp;M]] = C[i];
  }
  for(int i = n-1; i &gt;= 0; i--) {
    C[--count[2][A[i].t&gt;&gt;2*B]] = A[i];
  }

  // Walk through array (now sorted by T) and find matches.
  // We maintain a window of T values that might match.
  // To facilitate finding matches within that window, bcount
  // keeps track of a count of how many b's in that window
  // have the given low 14 bits.
  int j = 0;
  for(int i = 0; i &lt; n; i++) {
    int a = C[i].a;
    int t = C[i].t;
    while(C[j].t &lt;= t - 100) {
      int x = C[j].b &amp; 16383;
      if(bcount[x] != 255) bcount[x]--;
      j++;
    }
    if(bcount[a &amp; 16383] &gt; 0) {
      // somewhere in the window is a b that matches the
      // low 14 bits of a.  Find out if there is a full match.
      for(int k = j; k &lt; i; k++) {
        if(a == C[k].b)
          C[k].print = C[i].print = 1;
      }
    }
    int x = C[i].b &amp; 16383;
    if(bcount[x] != 255) bcount[x]++;
  }
  for(int i = 0; i &lt; n; i++) {
    if(C[i].print)
      printf("%d %d %d\n", C[i].a, C[i].b, C[i].t);
  }
}