7

I have a very large text file (around 20 GB and 300 million lines), which contains three columns separated by tabs:

word1 word2 word3
word1 word2 word3
word1 word2 word3
word1 word2 word3

word1, word2, and word3 are different in each line. word3 specifies the class of the line, and repeats often for different lines (having thousands of different values). The goal is to separate the file by the line class (word3). I.e. word1 and word2 should be stored in a file called word3, for all the lines. For example, for the line:

a b c

the string "a b" should be appended to the file called c.

Now I know how this can be done with a while loop, reading line by line of a file, and appending the proper file for each line:

while IFS='' read -r line || [[ -n "$line" ]]; do
    # Variables
    read -a line_array <<< ${line}
    word1=${line_array[0]}
    word2=${line_array[1]}
    word3=${line_array[2]}

    # Adding word1 and word2 to file word3
    echo "${word1} ${word2}" >> ${word3}  
done < "inputfile"

It works, but is very slow (even though I have a fast workstation with an SSD). How can this be speed up? I have already tried to carry out this procedure in /dev/shm, and splitted the file into 10 pieces and run the above script in parallel for each file. But it is still quite slow. Is there a way to further speed this up?

1
  • The builtin read command is quite inefficient and not a good choice for large files. Consider using awk instead. Oct 20, 2018 at 14:37

5 Answers 5

4

Let's generate an example file:

$ seq -f "%.0f" 3000000 | awk -F $'\t' '{print $1 FS "Col_B" FS int(2000*rand())}' >file

That generates a 3 million line file with 2,000 different values in column 3 similar to this:

$ head -n 3 file; echo "..."; tail -n 3 file
1   Col_B   1680
2   Col_B   788
3   Col_B   1566
...
2999998 Col_B   1562
2999999 Col_B   1803
3000000 Col_B   1252

With a simple awk you can generate the files you describe this way:

$ time awk -F $'\t' '{ print $1 " " $2 >> $3; close($3) }' file
real    3m31.011s
user    0m25.260s
sys     3m0.994s

So that awk will generate the 2,000 group files in about 3 minutes 31 seconds. Certainly faster than Bash, but this can be faster by presorting the file by the third column and writing each group file in one go.

You can use the Unix sort utility in a pipe and feed the output to a script that can separate the sorted groups to different files. Use the -s option with sort and the value of the third field will be the only fields that will change the order of the lines.

Since we can assume sort has partitioned the file into groups based on column 3 of the file, the script only needs to detect when that value changes:

$ time sort -s -k3 file | awk -F $'\t' 'fn != ($3 "") { close(fn); fn = $3 } { print $1 " " $2 > fn }'
real    0m4.727s
user    0m5.495s
sys     0m0.541s

Because of the efficiency gained by presorting, the same net process completes in 5 seconds.

If you are sure that the 'words' in column 3 are ascii only (ie, you do not need to deal with UTF-8), you can set LC_ALL=C for additional speed:

$ time LC_ALL=C sort -s -k3 file | awk -F $'\t' 'fn != ($3 "") { close(fn); fn = $3 } { print $1 " " $2 > fn }'
real    0m3.801s
user    0m3.796s
sys     0m0.479s

From comments:

1) Please add a line to explain why we need the bracketed expression in fn != ($3 ""):

The awk construct of fn != ($3 "") {action} is an effective shortcut for fn != $3 || fn=="" {action} use the one you consider most readable.

2) Not sure if this also works if the file is larger than the available memory, so this might be a limiting factor.:

I ran the first and the last awk with 300 million records and 20,000 output files. The last one with sort did the task in 12 minutes. The first took 10 hours...

It may be that the sort version actually scales better since opening appending and closing 20,000 files 300 million times takes a while. It is more efficient to gang up and stream similar data.

3) I was thinking about sort earlier but then felt it might not be the fastest because we have to read the whole file twice with this approach.:

This is the case for purely random data; if the actual data is somewhat ordered, there is a tradeoff with reading the file twice. The first awk would be significantly faster with less random data. But then it will also take time to determine if the file is sorted. If you know file is mostly sorted, use the first; if it is likely somewhat disordered, use the last.

7
  • 2
    Thank you for your nice solution. I have tested it with larger files as well, because I was worried that sorting does not scale linearly with the number of lines. But surprisingly, it seems that sort scales linearly with the file size, so your solution should work also for very large files. The largest file I tested was 6 GB. Not sure if this also works if the file is larger than the available memory, so this might be a limiting factor. Otherwise, this seems to be the most efficient solution so far.
    – Jadzia
    Oct 21, 2018 at 0:05
  • 2
    sort will sort files much larger than physical memory by breaking the input up into smaller temp files. It is a miracle of 1970's tech when both RAM and disk were dear.
    – dawg
    Oct 21, 2018 at 2:06
  • 2
    @Jadzia I think this should be the accepted answer, not mine. Oct 21, 2018 at 7:46
  • Also, I suggest changing the awk script at the end to (fn != ($3 "")) { close(fn); fn = $3 } { print $1 " " $2 > fn }. Oct 21, 2018 at 9:46
  • 3
    @dawg: Thank you for clarifying this. In this case, I agree with oguzismail that your solution should be the accepted answer. It is an remarkable additional speedup to the already remarkable speedup with awk alone.
    – Jadzia
    Oct 21, 2018 at 10:50
3

You can use awk:

awk -F $'\t' '{ print $1 " " $2 >> $3; close($3) }' file
2
  • 1
    Thank you very much for this great solution. I have tested it, it works at an amazing speed. Approximately 100 times faster than my purely Bash-based solution.
    – Jadzia
    Oct 20, 2018 at 14:38
  • 2
    Should be awk -F $'\t' '{ print $1 FS $2 >> $3; close($3) }' file since the file is tab separated... And perhaps awk -F $'\t' '{ print $1 " " $2 >> $3; close($3) }' file to replicate what the original Bash program is doing since the tabs are being converted to spaces by that.
    – dawg
    Oct 20, 2018 at 14:44
2

This solution uses GNU parallel, but may be tuned with the other awk solutions. Also it has a nice progress bar:

parallel -a data_file --bar 'read -a arr <<< {}; echo "${arr[0]} ${arr[1]}" >> ${arr[2]}'
2

Use awk for example:

awk -F '{ print $1 FS $2 > $3 }' FILES

Or this Perl script (written by me) - I won't repost it here, as it is a bit longer. awk should be somewhat slower as it (re)opens the files for every line. This is better than the Perl script whenever you have more than 250 different values/output files (or whatever your OS has as limit for the number of simultaneously open filehandles). The Perl script tries to hold all input data in memory, which is much faster but can be problematic for large inputs.

The solution for a large count of output files was posted by user oguzismail :

awk '{ print $1 FS $2 >> $3; close($3) }' file

This (re)opens the output file for every line and it won't run into the issue of having too many open output filehandles open at the same time. (Re)opening the file might be slower, but reportedly isn't.

Edit: Fixed awk invocation - it printed the whole line to the output, instead of the first two columns.
4
  • What if column three contains hundreds of different filenames? Oct 20, 2018 at 14:24
  • 1
    Yeah - then awk will have the same problem as the perl script, opening too many filehandles. Your approach with append+close is better then, but slower otherwise.
    – Corion
    Oct 20, 2018 at 14:26
  • Thank you very much for your answer. Both are great solutions when there are not so many files as you point out. Currently, I have thousands of different files (values of column3), but I might have files with fewer values in the future, therefore I am glad you posted your suggestion.
    – Jadzia
    Oct 20, 2018 at 14:33
  • 1
    Don't know about other versions but in gawk mine is faster than yours. Oct 20, 2018 at 14:53
1

You question is very much similar in nature to Is it possible to parallelize awk writing to multiple files through GNU parallel?

If your disk can handle it:

splitter() {
  mkdir -p $1
  cd $1
  awk -F $'\t' '{ print $1 " " $2 >> $3; close($3) }'
}
export -f splitter
# Do the splitting in each dir 
parallel --pipepart -a myfile --block -1 splitter {%}
# Merge the results
parallel 'cd {}; ls' ::: dir-* | sort -u | parallel 'cat */{} > {}'
# Cleanup dirs
rm -r */

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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