I apologize for not having graded Challenge Two yet. I'll get around to it sometime. Just not soon enough.

However, people have asked when Challenge Three is starting, so I'm giving a very practical problem. I won't give any hints about it, because I want everyone to try to come up with the most efficient solution they can. I am not asking for actual code segments for this, though if you want to write a code segment to explain something or whatnot, I don't mind. I would prefer the actual solution you have be presented clearly and concisely.

Okay, here's the challenge (challenge closes November 30, 2007):

Let's say you have a phone book stored on your hard drive. 100,000,000 entries, 1K each. This means the file is roughly 100GB in size. These entries are not sorted in any fashion though, so it's basically 100GB of data that needs to be properly organized. What's the most efficient way possible to sort all the entries (to a separate file)?

Get the file size, mmap it, create another file of that size, mmap that for writing also, memcpy, in-place MergeSort.

Do I win a prize?

No.

Methinks I know why you gave the date you did. Kek.

I should note that as a grader (probably) I will be grading for search-by-name time as well as a list-in-order time.

I'll give a hint; there's a very specific struct to use with this.

Ten-way tree!

<prophile> Why two when you have have a foursome? Or a tensome?

Anyone else hearing this? Prophile likes orgies?

Just talked with you about this... You're partially right. There's a VERY specific way to solve this. But there's no one data structure to do it.

No common data structure, depending on how you answer the question I left you on Skype.

Thanks for posting this; I see that I never did post my latest solution to challenge #2.

As for this, my solution would be:

• Allocate an array large enough to hold the entire data set
• Run quicksort (or your favorite sorting algorithm) on said array
• Print the array to the new file.

Since the system can handle the original data file, it can potentially allocate that much virtual memory, or manipulate a file as if it were an array in memory. Maybe, because it's 100 gigabytes long, you can't literally keep the entire array in memory, and you end up doing a lot of seeking instead. That makes not one whit of difference to the algorithm itself.

One optimization that might allow you to store the full data set in memory is to index and hash the entries (in linear time) and sort the hashes. You could then print out the entries in the original file in the order they appear in the sorted array.

To clarify what I mean, let's say you have the following entries:

Arnold Palmer (1048 bytes of data)
Eldrick Woods (1020 bytes of data)
Jack Nicklaus (1014 bytes of data)
Greg Norman (1080 bytes of data)

In linear time, we could make a pass through that file, and generate the following index:

PALMER ARNOLD, offset 0, length 1048
WOODS ELDRICK, offset 1048, length 1020
NICKLAUS JACK, offset 2068, length 1014
NORMAN GREG, offset 3082, length 1080

If we allow 14 characters for the name, 8 bytes for the file offset, and 2 bytes for the record length, we need 24 bytes per record, or a total of 2.4 GB of memory, for the array. A modern system will have this. We can now order any two entries with a constant-time lexicographic comparison of both 14-character name fields. (Only if these are identical will we need to look up the full names in the original records, which we can do from the offsets.) We can now quicksort or introsort this array of structures, into:

NICKLAUS JACK, offset 2068, length 1014
NORMAN GREG, offset 3082, length 1080
PALMER ARNOLD, offset 0, length 1048
WOODS ELDRICK, offset 1048, length 1020

From these lengths and offsets, reassembling the original file in sorted order is a linear-time operation.

just dump everything in a mysql database and index it, done, oh wait, this are C++ challenges, heh

EDIT: if you need a more serious entry, I would go for the memory efficient way. built a file with hashes and the location in the file, then if you need a name, hash the name, lookup the hash in the hash table, find the location in the file, and grab the data from that location. You could also organise the hashes a bit, like if the hash is ABCDEF:
/hashes/A/B/C.txt, to make it easier to search trough files, or make a file that says: A entries start at place 0, B entries start at place 2345 (for the hashes, ofcourse)

I only know very basic C++ but, can't you just split the file and index it in pieces?

That's your response? This isn't a query, it's a freaking sort! Let's say you have the RESULT of a query and your job is to sort it.

How do you mean?

Well, lets say there is a file, 1000 mb (1 gb),

1. Split (5 pieces). (Or other size so its possible to fit it in ram)
2. Organize by A,B,C...
3. Combine then split again this time into letter groups.
4. Now you have a file for every letter group that is organized into alphabetical order.

Do this again if you want it organized by area code or something.

I have no clue how hard or how complicated the program would be or if its even possible, thats all I can think of for now.