2

Given a 10GB file full of names, the task is to a sort process on the file, and the system has only 2GB of RAM. How will you do it ?

Is it possible to load or process the 10GB file with 2GB RAM?

Jongware
  • 22,200
  • 8
  • 54
  • 100
Manzoor
  • 85
  • 1
  • 3
  • 10
  • Could you tell us the file's structure? As far as I understood, you want to sort it. Depending on the file type, that can be easil done using tools present on almost all modern Linux systems. Please edit your question accordingly. – Markus W Mahlberg Mar 31 '15 at 16:33
  • Its just a plain text file with names. One name per line. – Manzoor Apr 01 '15 at 17:03
  • I edited out the Linux from the text and tags, as they seem not to be relevant to the question -- I think this is (or should be) about the used *algorithm*, not a particular OS. – Jongware Apr 07 '15 at 19:54
  • On a 64-bit system, you might even be able to load it... (using tons of swap space) (Memory mapping the file is probably a better idea (with the right options the OS will only load parts into memory as needed)... (`mmap` is the way to do it on most Unix-like systems)). On 32-bit systems, you probably have to operate on the relevant parts of the file directly without attempting to have everything accessible as a variable at once... (read, seek, write, repeat - simpler approaches is likely slower though) – Gert van den Berg Mar 24 '16 at 06:41

3 Answers3

8

The solution is to divide the file into parts that will fit into memory, sort the parts individually and write them to temporary files, then merge the temporary files.

For a more detailed description, see the Wikipedia article on Merge Sort.

For the record, the solution of using virtual memory will not scale. Unless you design your sort algorithm really carefully you will push the system into catastrophic virtual memory thrashing.

Sorting a compressed file won't work either.

Is it possible to load a 10GB file with 2GB RAM ?

Interpreting that as a general question, the answer is No. If you have a problem that requires (significantly) more RAM than you have, then you need to employ an algorithm that divides the problem into smaller ones. If you can't find an algorithm that works that way, you are in for a hard time.

Is it possible to process a 10GB file with 2GB RAM ?

Yes ... provided that your processing doesn't require you hold the entire 10GB file in memory at the same time.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
2

As per comments to the original question, it is a 10GB file of single lines containing names. This is easily achieved by using coreutils' sort, which should be present on virtually every Linux system:

sort yourFile

Now, given the file contains the names in the form FirstName LastName, this would sort the file by first names first, which is propably not what you want. In this case, you have to tell sort that you want to sort by the second (and subsequent fields in special cases):

sort -k 2 yourFile

Next, you want to make sure that the case is ignored (in case of typos or special surnames) and that we have a sort order equalling the ones used in dictionaries. The former is achieved using the -f flag, the latter with the -d flag:

sort -k 2 -f -d yourFile

Last but not least, you might want to write the result to a file, which can be done using the -o flag (For the curious: I found this to be faster than output redirection with >):

sort -k 2 -o sortedFile -f -d yourFile

As for RAM usage: I haven't tested it, but as far as I can see it should not be much more than 1Mb. However, it may take quite a while to get results.

Markus W Mahlberg
  • 19,711
  • 6
  • 65
  • 89
  • hmm... I thought this would still load the whole file into memory, but turns out you're right: `sort` uses an [External R-Way merge sorting algorithm](http://vkundeti.blogspot.ca/2008/03/tech-algorithmic-details-of-unix-sort.html) and [does not](http://stackoverflow.com/a/930051/2063031) load the whole file. – ostrokach Jan 26 '16 at 21:48
  • 1
    @ostrokach I have sorted files far exceeding the memory limits of the respective machine. Sometimes empirical experience is all you need ;) – Markus W Mahlberg Jan 26 '16 at 23:48
0

I don't know if it will help, but with the Haskell language you can handle files much bigger than your system's RAM using lazy evaluation, meaning that

Data is only read from the Handle as the elements (characters) of the list are processed. As elements of the String are no longer used, Haskell's garbage collector automatically frees that memory.

Bryan O'Sullivan, Don Stewart and John Goerzen explain how it is done in their book Real World Haskell.

Marcus Vinícius Monteiro
  • 7,669
  • 5
  • 30
  • 39