28

I have a text file with a word in each line, the size of the file is 800GB. I need to sort the words alphabetically.

I have tried using the Windows sort program using:

sort.exe input.txt /o output.txt

which gives the error: Not enough main memory to complete the sort.

I have 32GB of RAM so when I try specifying 10GB of memory for the sort using:

sort.exe input.txt /o output.txt /M 10000000

I get:

Warning: the specifed memory size is being reduced to the available paging memory.

Input record exceeds maximum length. Specify larger maximum.

What are my options?

18
  • 2
  • 11
    This is not a cross-post, I am not a machine so posting this and deleting the other takes a few minutes!
    – MaYaN
    Mar 4, 2018 at 17:15
  • 3
    In the future allow the community to migrate your question
    – Ramhound
    Mar 4, 2018 at 18:57
  • 4
    With Linux, you could apply this method. With files of 100Mb, it shouldn't be a big problem. Mar 4, 2018 at 21:06
  • 3
    What version of Windows are you using? The sort.exe with the rather old Windows Server 2012 R2 claims to be able to do external merge sorting with the use of a temporary file on disk (without documenting a size limit). Try using /T to specify a disk with 800Gb free for the temporary file. And the message about "input record exceeds maximum length" seems unrelated to space - look at the /REC option and consider what your line terminator is.
    – davidbak
    Mar 4, 2018 at 22:54

5 Answers 5

18

What are my options?

Try Freeware Command Line Sort Utility CMSort.

It uses multiple temporary files and then merges them at the end.

CMsort is reading records of an input file until the adjusted memory is reached. Then the records are sorted and written to a temporary file. This will be repeated until all records are processed. Finally, all temporary files are merged into the output file. If the available memory is sufficient, no temporary files are written and no merging is needed.

One user reports it sorted a file of 130,000,000 bytes.

If you want to tweak some code yourself, there is also Sorting Huge Text Files - CodeProject - "Algorithm of sorting lines in text files size of which exceeds available memory"

2
  • 31
    Wow, 130 megabytes!!! +1 Mar 4, 2018 at 21:01
  • 3
    @DavidPostill Are you sure that sort from coreutils for windows is not more efficient (--parallel option if you have more than one core...)?
    – Hastur
    Mar 5, 2018 at 7:16
23

One other option is to load the file into a Database. E.g. MySQL and MySQL Workbench.
Databases are perfect candidates for working with large files.

If your input file contains just words separated by a new line this shouldn't be too hard.

After you've installed the database and MySQL Workbench this is what you'd need to do.

First, create the schema (this assumes words won't be longer that 255 characters although you could alter this by increasing the argument value).

The first column "idwords" is a primary key.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Secondly, import the data.
E.g. this will import all the words into the table; this step may take a while to complete. My advise would be to run a test with a smaller file first and once you are sure the format is the same as the larger one (truncate the table... i.e. clear it out and load the full data set).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);

This link may help with getting the format right for the load. https://dev.mysql.com/doc/refman/5.7/en/load-data.html

E.g. if you needed to skip the first line you'd do the following.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Finally, save the sorted file. This may take a while also depending on your PC.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

You can also search the data at will as you like.
E.g. this will give you the first 50 words in ascending order (starting from the zero position or first word).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;
4
  • 2
    This IS the correct answer by a considerable margin.
    – MonkeyZeus
    Mar 5, 2018 at 13:11
  • 1
    This approach will definitely be more flexible, especially if you discover you need to re-run the sort with a different order, for example.
    – barbecue
    Mar 5, 2018 at 14:48
  • I don't care how fast your instance of MySQL, MariaDB or any other DBMS is, it is not going to come anywhere close to the the insert performance of SQLite running on the same machine. Even with something as fast as SQLite this amount of data is too much (and slow) to process (trust me I tried that first!) so the best solution is to sort and remove the duplicates first then insert to a DB such as SQLite. So while this solution may be valid for some cases it certainly is not for what I am trying to do. Thank you for taking the time to post this anyway.
    – MaYaN
    Mar 5, 2018 at 19:50
  • Ordering by mywords will take forever. Even with the LIMIT, it will take just as long as the whole thing because MySQL will have to go through every single value of mywords and order them. To fix this, you have to do the following after you've done LOAD DATA. Add an index to mywords. Now you can order by that column and not have it take a millennium. And it is better to add the index after loading the data rather than at the time you created the table (much faster data load). Mar 5, 2018 at 23:30
7

sort

There are many algorithms used to sort ordered and not ordered files [1].
Since all those algorithms are already implemented, pick a program already tested.

In coreutils (from Linux but available for windows too [2]), it exists the sort command capable to run in parallel under multi-core processors: usually it is enough.

If your file is so huge you can help the processing splitting (split -l), the file in some chunks, possibly using the parallel option (--parallel), and sorting the resulted ordered-chunks with the -m option (merge sort).
One of the many ways to do it is explained here (split file, order single chunks, merge ordered chunks, delete temp files).

Notes:

  • In windows 10 there exist the so called Windows Subsystem for Linux in which all the Linux example will seem more natural.
  • Sorting with different algorithms has different execution times that scale as function of the number of data entries to be sorted (O(nm), O(nlogn)...).
  • The efficiency of the algorithm depends on the order that is already present in the original file.
    (For example a bubble sort is the most fast algorithm for an already ordered file -- exactly N --, but it is not efficient in other cases).
2

To offer an alternative solution to Peter H, there is a program q which allows SQL style commands against text files. The command below would do the same (run from command prompt in same directory as file), without needing to install SQL Workbench or creating tables.

q "select * from words.txt order by c1"

c1 is shorthand for column 1.

You can exclude duplicate words with

q "select distinct c1 from words.txt order by c1"

and send the output to another file

q "select distinct c1 from words.txt order by c1" > sorted.txt
3
  • Any idea whether this will cope with an 800 gig file?
    – Rawling
    Mar 5, 2018 at 15:39
  • 1
    I'm not 100% sure - I tested the above with a 1200 line file (9KB). The developers page has a "limitations" page that doesn't mention anything about a maximum file size. A large file may still come up against a memory problem.
    – Brian
    Mar 5, 2018 at 16:21
  • 3
    q cannot process this amount of data remember that q uses SQLite behind the scene if I could not load the data direct to SQLite what makes you think q can?
    – MaYaN
    Mar 5, 2018 at 19:58
2

If the words on each line are from a limited vocabulary (like English) then you can sort the list in O(n + m log m) time using a TreeMap and recording counts (where m is the number of unique values).

Otherwise you can use the java library big-sorter. It splits the input to sorted intermediate files and merges them efficiently (overall O(nlogn)). To sort your file looks like this:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

I created a 1.7GB file (100m lines) with randomly generated 16 character words and sorted it as above in 142s and based on the O(n log n) computational complexity of the method I am using I estimate that 800GB of 16 character words would take about 24 hours to sort single-threaded on my i5 2.3GHz laptop with SSD.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .