3 ms·
Unix sort already does a merge sort (search for it), which is your default solution if you just want to sort individual lines based on a field: http://vkundeti
by timr 16y ago
Unix sort already does a merge sort (search for it), which is your default solution if you just want to sort individual lines based on a field:
http://vkundeti.blogspot.com/2008/03/tech-algorithmic-details-of-unix-sort.html http://vkundeti.blogspot.com/2008/03/tech-algorithmic-detail...
Thus, sort -u <filename> is your go-to for simple jobs. (Note that you'll need to have enough extra disk space to hold all of the temporary files.)
If you need to do something more sophisticated (e.g. joining lines from a web server log into sessions, then sorting sessions), you can still use divide-and-conquer, but you have to be smarter. Divide the file into N parts based on some logic (i.e. divide into files based on session ID), then sort the lines in each individually, then merge the results back together.
This is what map/reduce frameworks are made to do, of course, but something like Hadoop may be overkill unless you plan to do this type of thing often.
- arnabdotorg 16y agoMerge sort works very well if you have multiple cores available. The general idea is to split the file, sort in parallel, and then merge. Here's a blog post I wrote about it: http://arnab.org/blog/quick-and-easy-multicore-sort http://arnab.org/blog/quick-and-easy-multicore-sort
- ralph 16y agoGNU sort has a --compress-program option that can help if you're really tight on scratch space, e.g. lzop(1). The -T option or TMPDIR environment variable lets you state a filesystem with more free space can be used instead.
- pjscott 16y agoThe -T option especially helps if you have more than one hard drive, and you're sorting a very large file where disk I/O is the bottleneck. You can use a second hard drive for the temporary files.
- jbl 16y agoThis is the approach that I use except that I generate a Makefile which has: - a target to split the input into chunks - targets to sort each of the split chunks - a target to merge the sorted chunks using "sort -m" Then, if you are using GNU make, it's just a matter of using the -j flag to control how many chunks are sorted in parallel.