Sorting a large file

Question

I have some huge logs, which are text files, containing up to a million rows each, and I need them sorted.

Because trying to import one obviously makes Mathematica run out of memory, we must rule out approaches like this

data=Sort/@Import[fileIn,"Lines"];
Export[fileOut,data,"Lines"];

At the present moment I use a childish method, splitting the file to be ordered in ten files 0.txt ... 9.txt, where k.txt contains only lines starting with the figure k; ordering each (as above) and, finally, gathering them.

It works fine in some respects but it's deadly slow, even on a solid state hard disk.

Does Mathematica ( 8.0 or 9.0 ) provide any built-in support or package for sorting files?

Any suggestion is highly welcome!

ADDENDUM : 2014 03 21

Firstly I apologize for my poor English and I thank for you adjusting: I will attend english.stackexchange.com, promise. I'm good enough in "from English to Italian" but I still walk backward on a finely greased, splippery, floor.

I have put a piece of my code here: https://www.dropbox.com/s/i9l4atcfwhcmg5q/fileSorter%20ver.%204.2%20unformatted.%20.zip

It operates splitting a file over and over again, up to pieces loadable in RAM, sorting them and sticking all togheter.

It works as intended but deadly slowly: sorting a file containing 10^7 records, a string of length 10^3 each, takes around two hours on my pc (P4 1,8 GHz, 2 Gb RAM, SSD) because of a wasteful cutting method.

At present moment I'm improving it to a single pass knife.

I'm thoroughly studying the Stream[] based hint you provided, also

The dabaase to be sorted is precisely structured; it' a tab delimited list of files, located on external hard disks :

file size, unit serial number, unit label, file date, file hash (crc32), file hash (crcmd5), filedate, folder, file base name, file extension

Answer 1

I think that it can be done, without loading all the data into memory. The main idea would be to load only the data necessary to do the sorting and then take advantage of Stream

Let's first create a a fake log file with random data:

strW = OpenWrite["UnSorted.txt"]

Do[
 WriteString[strW,
  FromCharacterCode[RandomInteger[{65, 90}, 10]], "\t"
  , RandomInteger[10^7], "\t"
  , FromCharacterCode[RandomInteger[{65, 90}, 10]]
  , "\n"
  ], {10^6}]

Close[strW]

Now we can store in a table only the data necessary for the sorting and the stream position.

strR = OpenRead["UnSorted.txt"]

nList = Table[
   With[{sp = StreamPosition[strR], 
     line = Read[strR, {"Word", "Number", "String"}]}, {sp, line[[2]]}]
   , {i, 10^6}
   ];

Close[strR]

Now we create an ordering list, with the positions of the lines of the sorted list.

oList = Ordering[nList[[All, 2]]];

And now we write line by line in the correct order.

strW2 = OpenWrite["Sorted.txt"]
strR = OpenRead["UnSorted.txt"]

Do[
 SetStreamPosition[strR, nList[[l, 1]]];
 WriteString[strW2, Read[strR, "String"], "\n"];
 , {l, oList[[;10^3]]}]

Close[strR]; Close[strW2]

This is memory efficient and the sorting takes only a second, the delay is mainly from the slow read/write on disk operations.

EDIT: I changed the code to write only the first thousand sorted elements, as this process is too long to wait just for the sake of an example.

Answer 2

Mathematica 9 has no Sort implementation geared for out-of-core (~ does not fit in RAM) data. As Szabolcs suggested, you can use GNU sort command (possibly directly from Mma), unless you want to specifically implement some external sorting algorithm with Mathematica.

For further information on external sorting with GNU sort, see this stackoverflow thread.

Of course, if your order function is more complicated than sort can handle, it doesn't work that well. Method you described not really much worse algorithmically if all split files fit in memory for sorting - but it may be unaware of optimal memory use and manner of read/write operations from temporary files, which may lead to virtual memory trashing or excessive hard disk seeking.