Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

I am looking for a fast filter that will take a text file on standard input, hash each line up to the first tab character, and put the line into a different file depending on the hash value (modulo some number of files). For example, something like:

$ cat > foo
a   1
b   2
c   3
d   4
^D
$ hashit -o bar -n2 < foo
$ cat bar.0
b   2
$ cat bar.1
a   1
c   3
d   4

The hash function must be consistent between invocations.

This is somewhat like the standard split utility, but I want to split on the hashed content of lines, not simply the number of lines per component.

share|improve this question

4 Answers 4

So you need speed. That kind of speed likely requires C (though Perl might be sufficiently optimized). Unfortunately, buffering is complex to do manually in C, and slow automatically in Perl/Python/Java.

So one possible path to a least-pain C solution, assuming you can run on a 64-bit system and you aren't processing more than a few bajillion TB of data:

  1. open the output files
  2. mmap the entire input file
  3. remember current position
  4. scan until a tab, summing the ASCII values modulo your file count (possibly subtracting 31 from each character first), to get the code
  5. scan until a newline or EOF
  6. the contents are mmap'd. this is an array. write from start position to the new line to an ouput file. Use write(2), not fputs or something like that, to keep the C library's buffering out of the way.
  7. return to 3 until file is finished

The friendly kernel will take care of paging things into memory as you reach the end, so you don't have to buffer yourself.

Note that memory-mapped IO is not necessarily faster than read/write calls for bulk I/O, which this effectively is, but it will make the code substantially simpler than trying to write buffering logic yourself. A Python solution based on this general design may be fast enough as well.

share|improve this answer
    
Interesting.... does mmap() work on standard input? –  Reid May 21 '13 at 2:58
    
@Reid No, it requires the underlying descriptor to be a real file. It operates on a file descriptor, so if stdin is a file, it will work, but won't work on e.g. a pipe. For a pipe you'll have to mess with buffering. –  Michael Ekstrand May 21 '13 at 3:42
    
Turns out that on Linux at least, the default buffering for getline() is plenty fast. –  Reid May 22 '13 at 19:11

You could write a python script to do this... since you said it needs to be fast, perhaps a CRC is a reasonable choice of hash function.

Try something like this:

import fileinput
import binascii

for line in fileinput.input():
    modulo = binascii.crc32(line.split()[0]) % splits

The variable splits should be set to the number of files into which you wish to split the input. You can use the variable modulo to construct the filename where each line should be placed.

share|improve this answer
    
I did try profiling a relatively naive Python script. The hashing is consuming a pretty small fraction of the time (~5%). It's ~25% io.write(), ~25% split(), and ~50% unknown (because it didn't show up in the profile). –  Reid May 21 '13 at 0:00
    
Cool, good analysis. Was the Python approach too slow for your problem set? –  Mox May 21 '13 at 0:08
    
Yes, it's about 20MB/s. My hope is for it to be fast enough that the disk is the bottleneck: 150-200MB/s. –  Reid May 21 '13 at 0:43

That (suspiciously like homework looking ;) problem sounds like a job for awk

awk '{ print > "FilePrefix."$1%YourModValueHere }'

eg

awk '{ print > "bar."$1%3 }'

Update to fix missunderstanding:

1) define outputfilePrefix and modoloValue
2) load inputfile linewise as positional parameters
3) iterate over all entries in the first column
   a) calculate CRC (cksum), and modolo CRC
   b) output first positional parameter ($1) to file (prefix.modoloOfCRC )
   c) shift positional parameters one to the left (discarding the current line in position 1)

code: just enter as single line in bash

preFix="bar"; modolo=3;IFS=$'\n';set $(cat foo); for i in $(cut -f1 foo);do target=$(( $(echo $i | cksum | cut -d ' ' -f1;) % $modolo ));echo $1 >> $preFix.$target; shift; echo $target; done

better readable for understanding

1) preFix="bar"; modolo=3;
2) IFS=$'\n';set $(cat foo); 
3) for i in $(cut -f1 foo);do 
       target=$(( $(echo $i | cksum | cut -d ' ' -f1;) % $modolo ));
       echo $1 >> $preFix.$target; shift; echo $target; 
   done

if you put it in a shellscript, you can even pipe in the file (with little modification..) via stdin

share|improve this answer
    
This solution seems to be missing the hashing step. In the awk arguments above, $1 is the (unhashed) text in each line up to the first tab. –  Mox May 20 '13 at 23:33
    
aah, i understood that OP means to use modolo as hash-function... –  Legionair May 20 '13 at 23:36
    
Not homework. The modulus operation simply reduces the number of hash values to match the number of output files. –  Reid May 20 '13 at 23:41
    
@Reid update now includes hashing, didn't do benchmarking, but should perform reasonably well.. –  Legionair May 21 '13 at 12:22
    
Thanks. Doesn't that execute a subshell for each line? Also I can only read the input stream once (remember, it's stdin). –  Reid May 21 '13 at 17:00
up vote 0 down vote accepted

As far as I can tell, there are no standard utilities to do this, and a naive implementation in Python is too slow.

So, I implemented it in C in the open source project where I needed it, QUAC. Hopefully this will be useful for others. (I haven't yet pushed, but that should happen within a few days.)

share|improve this answer

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.