Billion word sort

I like your merge sort approach but consider whether or not it is necessary to create a bunch of files preemptively. Is it really necessary? Why not just make files when needed? Also, is it necessary that you use files based on words starting with 'a' (or whatever the first letter is) - what happens if you have many files full of sorted sets of strings?

If you can use the Windows API (or any other OS's API, really), I'd strongly suggest using a single memory mapped file. If the file format is fixed (such as one 5-character word per line, with the line terminator being "\n"), you can easily figure out how many words you have, and from there you can easily do something like load in as many as you can fit into memory, sort them, then write those to your mapped file (storing the offset and size in an in-memory 'master index'), then repeat until the end. After that, a simple merge could combine the stacks from the first memory mapped file into a final destination file.

You could use block read/write (fread/fwrite or ifstream::read/ofstream::write)instead of memory mapping, but it's more complicated because it means manually 'paging' things into and out of memory as needed, and it could end up much slower if you do it wrong. The upside is that it would be standard C or standard C++ and thus would be platform independant.

I agree with Colin. what would happen if all the words start with "a"? you'd have a.dat being equal to the original file. you can't recurse using this same sort function and other standard sorting functions might not fit in memory.

also consider that the item size is fixed (5 chars) this means we could treat the file as an array (and use fseek to get the element)and use heapsort or other in-place algorithims to sort the whole file but at the cost of very slow operation since lots of disk access have to be made. This might not be feasible to actually implement on a billion size list.

personaly, I would:
1. get the max amount of memory possible
2. allocate a large percent (say 70-80%) in a buffer
3. read as much data as possible into the buffer
4. sort the buffer using standard sorting (quicksort,etc)
5. write the buffer into a temp file
6. clear the buffer and read the next batch of data, sort, write (steps 3-5)
7. you now have several sorted temp files
8. merge the sorted files (and in the process search for the 2 hidden strings)

notes:
*since the items are always 5 chars, you can use binary search and fseek to find
the hidden strings. As an added bonus, can a lot of words at the same time using fread to avoid reading line by line to maybe get a small speed boost.

In the best case, all data fits into the buffer so sorting is just all in memory. this can be modified to use no additional disk space by writing the sorted data back into the main file.

The strings are all 5 characters?

The characters are restricted to [a-u, A-U]?

So 42 different code points per character.

How many different 5 character strings are there?

42^5, or roughly 13 million, or roughly 2^27, strings.

If you only need to know existance, you can store this in 2^19 bytes of data, or 1/2 a meg. Get a string. Encode it as a number from 0 to 2^27. Set that bit in your 1/2 megabyte array. Repeat.

If you need to have a count of duplicates, things get harder. :)

Well, not much harder.

4 bytes per node, 2^27 nodes, is 2^31 bytes. Or about 2 gigabytes of data. Easy to fit in a hard drive.

Optimization I leave to you.

The algorithm I'm using is known as "bucket sort". It relies on the fact that you have more words than you have possibly different words in order to break the O(n lgn) theoretical restriction on the speed of sorting.

NotAYakk has the right idea (I didn't want to give it all away) but a couple of wrong numbers.

Quote:

Original post by NotAYakk 42^5, or roughly 130 million, or roughly 2^27, strings. If you only need to know existance, you can store this in 2^24 bytes of data, or 16 megs Get a string. Encode it as a number from 0 to 2^27. Set that bit in your 16 megabyte array. Repeat.

I'm pretty sure the most optimal solution would be to make a lexigraphic tree.

struct WordTree{  bool IsWord;  WordTree * letters[26];    //assuming all 26 letters};

If you have a word max length, it makes it even easier. Basically, the word is in the list if you can traverse its letters without hitting a NULL pointer and the (IsWord) var is set.

Oh yeah, the best part is searching AND inserting AND deleting are performed in constant time regardless of the # of words.

Hope that helps.

bucket sort is aka radix sort.

Create a function that takes the 5 character string and encodes it to a 30 bit string. Encode the 42 possibilities to a 6 bit string and or-shift the 5 of them together into 1 30 bit number.

Make a single 1GB file and zero it.
Read in the first string, encode it and add 1 to the byte position in the 1GB file.
Do this for all 1billion numbers. If the numbers are evenly distributed this will work without issue.

Sorting is now O(n) and searching is O(1). Take the string you are looking for, encode it, look in that spot in the file and if it's >0 it's there.

Now, your instructor might be hip to this killer optimization, and he might toss in something insane like 500,000,000 of the same value so we need a way for this to scale.

When you read in the byte value and add 1 to it, you need to ensure you're not over-flowing 255. If you read in 255, then you need to create a second 1GB file. At first you might think to just continue counting in the new file starting with 1 and leave the 255 in the first file. Don't do that - instead use the second file as the second byte of the number. 0xFF + 1 = 0x0100. So write a 00 into the first file and a 01 into the second file. Make this scale up to 4 1GB files and you'll handle up to 4billion of the same string repeating itself over & over.
(Just make sure your read routine takes into account the bonus files if they exist so you read back the correct count.)

If you code it efficently you can bust out the sort in about 30 seconds.

I would probably use an approach similar to bubble sort, only it's on blocks. Let N be the maximum number of words that you can safely fit in memory at any given moment without hitting the swap.

1. Open file "input"
2. Open file "output"
3. Create two buffers A and B of size N/2 each.
4. Read two buffers from "input".
5. Sort buffer A using any in-place method of your choice.
6. Begin Loop
7. Sort buffer B using any in-place method of your choice.
8. Merge A and B by outputting their first N/2 elements into "output".
9. Merge the rest of A and B, sorted, into A.
10. If (Read N/2 elements from "input" into B) then goto 6
11. Else Write A to "output".

The above performs a bubble sort iteration on the data. Once you do (2*Size/N) iterations, the file will be sorted. For greater speed, you can use your intended approach of writing elements to 52 different files based on their first letter, which will decrease the number of necessary iterations.

I strongly suspect that operating system specific APIs such as those required for memory mapping are not to be used. Furthurmore, this may be intended as an external sorting exercize, which would mean that they do not want you to try and sort the whole thing in memory. I would seek clarification on this issue.
I myself have in the past done such an assignment, and it had to be external sorting.

The approach suggested to us was merge to and from files. You simply build runs as long as possible by appending each item in the first file which has a previous item less than the new item. Or if no such file exists AND you already have a certain number of files, you append it to the one with the largest previous item (starting a new run in the same file). About 16 files max should be plenty. Then close those files and open them as input, and repeat. You continue until you complete one iteration without having to write a second file, at which point you can rename the one file to the final filename as it is fully sorted.

Shannon Barber is right on track, but I have a better solution for overflow.

Once you reach 255, isntead of creating another file, use a simple hash table for the count.

What's interesting here is that a file with that number of elements of that size can't be indexed using a 32 bit integer, the file size is greater than 2³². The bucket sort is my favourite solution, but I'd recursively divide the file until the file was small enough to sort using an in-memory algorithm like qsort, i.e. if the a.dat was too large, create aa.dat, ab.dat, ac.dat and so on. You might also want to name the intermediate files differently just in case the character set being used includes invalid filename characters ('\' for example).

NotAYakk / Shannon Barber's solution doesn't scale well with an increased character set or increased word lengths.

Skizz

Scaling isn't required. It may be shortsided but without more info it's hard to say. Thier solution is simple and very fast.

I actually did this sort of thing once for a course. The assignment was something along the lines of "Compute whether a given integer (in the range 2..max) is prime, the only criteria is speed". This set off alarm bells in my head so I asked specifically if it was really the case that only speed was important. Upon being assured that it was I implemented a huge lookup table with one byte per entry (a bit array would have required a few extra instructions) and beat the pants off everybody else.

I do believe that the next year the assignment was changed to "the most important criteria is speed" :).

Quote:

Original post by Zahlman NotAYakk has the right idea (I didn't want to give it all away) but a couple of wrong numbers. Quote: Original post by NotAYakk 42^5, or roughly 130 million, or roughly 2^27, strings. If you only need to know existance, you can store this in 2^24 bytes of data, or 16 megs Get a string. Encode it as a number from 0 to 2^27. Set that bit in your 16 megabyte array. Repeat.

:p~

Ya ya, I did 27-8 instead of 27-lg(8).

Damn numbers.

Quote:

NotAYakk / Shannon Barber's solution doesn't scale well with an increased character set or increased word lengths.

Yes. But the problem was sorting a 5 character word, not generic sorting.

Bucket sort is an end-run around the N lg N speed barrier for sorting. Sorting is "really" N lg C, where C is the number of distinct possible code points.

Shannon Barber, instead of that complex method, I'd just create 42 different files and use 32 bit counters -- or just create one large file with 32 bit counters (and don't use 32 bit ints for indexing).

Mike, I'd expect that going the bit array method would have been faster, simply because you wouldn't have had to access as much memory. Better chance of cache coherance!

It does remind me of an OS class we had. We where writing an "OS siulator" -- write a library that, in user mode, provides the services that an OS needs, and write programs in simulated user mode that use those services.

One of the large projects was to implement a memory manager. My friend wrote it in an hour using the STL.

Next term, STL usage was disallowed. :)

Thank you all for the replies. I had a few questions about the radix sort.

Quote:

Shannon Barber: Create a function that takes the 5 character string and encodes it to a 30 bit string. Encode the 42 possibilities to a 6 bit string and or-shift the 5 of them together into 1 30 bit number. Make a single 1GB file and zero it. Read in the first string, encode it and add 1 to the byte position in the 1GB file. Do this for all 1billion numbers. If the numbers are evenly distributed this will work without issue.

My understanding is that each 5 char string will end up representing a unique byte in the 1gb file. "AAAAA" -> byte 1, "abfgD" -> byte n. Then, when I come across that value in the original data file, and encode it, it basically increases the counter value being stored in the final file. Am I getting this right?

Also, doing it this way, in a search, how would I return the position of the value searched for? I'm not sure it's possible.

Quote:

My understanding is that each 5 char string will end up representing a unique byte in the 1gb file. "AAAAA" -> byte 1, "abfgD" -> byte n. Then, when I come across that value in the original data file, and encode it, it basically increases the counter value being stored in the final file. Am I getting this right?

yep thats the basic idea, there were also a few things mentioned incase there are more then 255 occurences of one string so it doesnt overflow.

Quote:

Also, doing it this way, in a search, how would I return the position of the value searched for? I'm not sure it's possible.

assuming you want its location in the sorted list, if your word is "abfgD" and it is at byte n you add all the bytes from byte 1 to byte n-1 and this will tell you how many strings there are before the first occurence and adding the nth byte will tell you were the last ocurrence is.

klay, spend some time thinking about your problems before asking them. If there is something you don't understand, sit back, and think. Maybe play with the problem on a really small scale (instead of 5 characters, 1 character. Instead of 42 code points per character, 4 code points per character. Now you can do radix sort manually on a piece of paper).

Sure, many other people here could do your undergraduate computer science courses blindfolded. But the effort spent, and thought techniques gained, by working out some of this stuff by yourself -- that is the reason why you should be attending these courses.

I have been thinking about what you have to do and I have come up with a strange possible solution. What if you instead of thinking of them as an array of 5 chars with 2 possible sets of 21, you instead thing of it as a number. A base 42 number with 5 orders of magnitude. So you create a class that converts them to decimal and back again. In the end you will have a bunch of numbers, the lowest numbers would be first in your sort, the highest numbers would be last. If two numbers are equal to each other then all the characters are equal.

Not sure you are allowed to use this solution but I think it would be much more effiecent then a character sort of 5 characters.

So what do you all think? It is late and I might be just nuts here.

theTroll

Quote:

Original post by TheTroll I have been thinking about what you have to do and I have come up with a strange possible solution. What if you instead of thinking of them as an array of 5 chars with 2 possible sets of 21, you instead thing of it as a number. A base 42 number with 5 orders of magnitude. So you create a class that converts them to decimal and back again. In the end you will have a bunch of numbers, the lowest numbers would be first in your sort, the highest numbers would be last. If two numbers are equal to each other then all the characters are equal. Not sure you are allowed to use this solution but I think it would be much more effiecent then a character sort of 5 characters. So what do you all think? It is late and I might be just nuts here. theTroll

Sure, but the only thing you gain from that is compression, and you have the added tasks of the initial compression, and the final decompression.

As I mentioned earlier, it is important to find out if this assignment is specifically supposed to be about external sorting. If so, then by performing the entire sort in memory, you could miss the whole point of the assignment and lose marks.