Programming Challenge 9 - Manage a Data Structure

This programming Challenge is now finished and was about storing a large number of English words in memory and then retrieving them as fast as possible.

Entrants could use whatever data structures they wished, except that only their own code and not make use of any provided containers, 3rd party libraries etc. In C++ use Boost and STL containers or any others are not permitted.

For example write a hash function. Each word has a numeric value associated with it and you must retrieve that value as fast as possible and add all 10,000 values up.

Formal Statement of Problem

Write two functions in C, C++ or C#. These are AddWord() and GetWord(). The definitions are shown below:

• int AddWord(char * text,int value) c/c++
• int AddWord(string text,int value), c#
• int GetValue( char * text) c/c++
• int GetValue( string text) c#

AddWord() should store the value associated with the word in a data structure of your own making. If there is a duplicate it should return 0, or 1 for successfully storing the word. GetWord() should return the value associated with the word or -1 if the word was not found.

A file of 50,000 words will be supplied (one word per line) and your program should read these in and call AddWord() for each word. A second file of 10,000 words will be supplied and your program should read the words then fetch the value by calling GetWord(). Your program this as fast as possible.

Note: No 3rd party libraries, .NET container library or C++ STL/Boost class are allowed. It should be your own code that implements AddWord() and GetWord().

• Download Data Files. This has two zipped up text files holding 50,000 words, one to a line with a number and 10,000 words.

Each line in the 50,000 Data Word File has a word then a comma and an int numeric value. E.g.

Fred,89

Each line in the 10,000 word file has just one word.

Output

Output the total of the 10,000 values and the time it took to retrieve and sum them. The timing code below should be used to time the run. You may start the timing after you have read the 50,000 words into memory. If you load the 10,000 words immediately after then you can defer the timing start until after that has loaded. If you defer loading of the 10,000 words and then start the timing, you will get knocked out!

• How To Time C Code.
• How To Time C++ Code.
• How To Time C# Code.

Results

Congratulations to Robert C Cartaino for the fastest time with his homebrewed C# hash algorithm which was nearly twice as fast as the next entry. But a big thank you to everyone who entered.

1. Robert C. Cartaino (USA) in C# Time = 0.0026552
2. Yanjiang QIAN (P.R.CHINA) in C Time = 0.00439
3. st0le (India) in C++ Time = 0.00627368
4. Lucas Pimentel (29, Dominican Republic) in C# Time = 0.0076883
5. Peter Jannson (36, Sweden) in C++ Time = 0.0126922
6. Sameerkumar Namdeo (India) in C++ Time = 0.0134799
7. st0le (India) in C++ Time = 0.0261473
8. N.Navaneetha Krishnan (25, India) in C# Time = 0.53693
9. Sattar Sattari (Iran) in C# Time = 0.9689304

More Programming Challenges

• Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
• Link to Programming Challenge 2 - Count the Islands. (Finished)
• Link to Programming Challenge 3 - Manage Elevators. (Finished)
• Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
• Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
• Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
• Link to Programming Challenge 8 - Score Poker Hands - (Finished)
• Link to Programming Challenge 10 - Hide text in the text of a book - (Deadline March 31 2008)