# Sorting a large file

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!

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

-
I think that Mathematica is not the most convenient tool for this task. I'd try to use the unix command line tools for sorting: linux.com/learn/tutorials/296684-learning-gnu-text-utilities- Mathematica excels when you can read the full data into memory. – Szabolcs Mar 11 '14 at 14:56
First of all, welcome to mma.se! Secondly, splitting up data, sorting the parts and then combining them again isn't all that bad, this is what mergesort does. You can try using a combination of OpenRead and ReadList with 3 arguments. – Jacob Akkerboom Mar 11 '14 at 15:30
I'm very grateful for your kind answers ! I'm setting up some code and I would be pleased to share it and its benchmark here, if someone is interested. By the way, my S.O. is windows, therefore, as far as I know, the only sorting utility available is the dos command Find. See you soon ! – mitochondrial Mar 12 '14 at 13:22
user12659, I like your enthusiasm, I am getting enthusiastic as well :). Would you please consider setting a username? The fact that you are on Windows is a good pretext for me to write an answer implementing the things I mentioned. Also: the structure of the log files may be important. I am hoping your entries are structured like "date: 11/12/2013, entry: lots of text". In this case we can disregard a lot of the data while sorting (by date), and later retrieve the information. Is the data in @rhermans answer close? – Jacob Akkerboom Mar 13 '14 at 15:17
@user12659 Did you end up solving the problem suing Mathematica? – rhermans Mar 19 '14 at 11:50

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"]

Do[
SetStreamPosition[strR, nList[[l, 1]]];
, {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.

-
With open streams, you have to be careful about long running executions being aborted and leaving the streams open. Here's some methods for dealing with that. – rcollyer Sep 22 '14 at 12:43

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.

-