Programming Challenge: Letter frequency

(Results at the end of the post - Updated 2009-06-20 21:52 UTC.)

I have devised a small programming challenge for the world to work on. It has been suggested as a programming challenge for About.Com's C/C++ but it is given here as well in case they reject it. It goes as follows.

Write a program that calculate the frequency of characters in a given large text file as fast as possible. Write the frequency results and how long time it took on standard output in the format given below. Submit your code in a comment to this post.

This challenge goes on forever! I post new results in the end of this post as soon as there are any.

Rules:

1. Your program should be case insensitive when it counts letters.
2. The program should not read the text file from standard input. (Addendum 2009-06-20.)
3. The program should be written using Standard C or C++ so that it can easily be compiled and run on various platforms.
4. The 1.1 GB text file to use for counting, containing 1 byte characters, can be downloaded in a 339 MB compressed zip archive using one of the following ways.
• Via bittorrent using this torrent file.
• Via bittorent using an online torrent relay with the same torrent as above (works with just a web browser).
• Via GNUnet.
5. You must begin timing your code just before the text file is opened and you must end the timing after the results have been written to standard output. For timing, you can use the code given below (it works on POSIX and Windows systems).

Output format:

a 8.167%
b 1.492%
c 2.782%
d 4.253%
e 12.702%
f 2.228%
g 2.015%
h 6.094%
i 6.966%
j 0.153%
k 0.772%
l 4.025%
m 2.406%
n 6.749%
o 7.507%
p 1.929%
q 0.095%
r 5.987%
s 6.327%
t 9.056%
u 2.758%
v 0.978%
w 2.360%
x 0.150%
y 1.974%
z 0.074%
Time [microseconds]: 310

The frequency distribution given above is incidentally the relative frequencies of letters in the English language.

Timing code:

Use as follows in C++ (the code can be modified to be useful in C):

/*
 CStopWatch s;
 s.startTimer();
 The_Stuff_You_Want_To_Time_Executes_Here();
 s.stopTimer();
You may then get the elapsed time in seconds
via the method getElapsedTime.
*/
#ifdef WIN32
#include <windows.h>
class CStopWatch
{
private:
   typedef struct {
      LARGE_INTEGER start;
      LARGE_INTEGER stop;
   } stopWatch;
   stopWatch timer;
   LARGE_INTEGER frequency;
   double LIToSecs( LARGE_INTEGER & L)
   {
      return ((double)L.QuadPart/(double)frequency.QuadPart);
   }
public:
   CStopWatch()
   {
      timer.start.QuadPart=0;
      timer.stop.QuadPart=0;
      QueryPerformanceFrequency( &frequency );
   }
   void startTimer() { QueryPerformanceCounter(&timer.start); }
   void stopTimer() { QueryPerformanceCounter(&timer.stop); }
   double getElapsedTime()
   {
      LARGE_INTEGER time;
      time.QuadPart=timer.stop.QuadPart-timer.start.QuadPart;
      return LIToSecs( time );
   }
};
#else
#include <sys/time.h>
class CStopWatch
{
private:
   typedef struct {
      timeval start;
      timeval stop;
   } stopWatch;
   stopWatch timer;
public:
   void startTimer( ) { gettimeofday(&(timer.start),0); }
   void stopTimer( ) { gettimeofday(&(timer.stop),0); }
   double getElapsedTime()
   {
      timeval res;
      timersub(&(timer.stop),&(timer.start),&res);
      return res.tv_sec + res.tv_usec/1000000.0;
   }
};
#endif

Results

All programs was compiled using GNU g++/gcc on an Ubuntu i386 machine with 500 MB RAM using the -O3 optimization flag. NDEBUG was defined as well. All programs was run using the text file in the challenge description. Some of the programs did not use the (wall clock) timing code provided so I have used the UNIX time command to get their execution real time, marked with (*) below. (I used GNU make for building and executing the code using this Makefile.)

Each program was run 10 times and the average time was calculated using the spreadsheet available here. The list below shows relative times, compared to the fastest.

Standard C or C++ (As per the rules.)

1. Chris M Thomasson 3 (C): 100,00 % (*)
2. Jonathan Lee (C++): 100,02 %
3. Pavel (C++): 100,09 % (*)
4. Chris M Thomasson 4 (C): 100,12 % (*)
5. Alf P Steinbach's modification of Chris' 2:nd code (C): 100,31 % (*)
6. Meathe (C): 100,33 % (*)
7. Nils (C++): 100,45 %
8. Giannis T (C++): 100,71 %
9. Chris M Thomasson 1 (C): 100,91 % (*)
10. Chris M Thomasson 2 (C): 100,95 % (*)
11. Agelos Anaptixi (C++): 101,05 % (*)
12. Peter Jansson (C++): 101,10 %
13. Ioannis Vranos (C++): 101,18 % (*)
14. JT (C): 102,10 % (*)
15. Graham Cox (C++): 102,28 % (*)
16. Peter's modification on Blarrg's code (to read from file) (C++): 123,46 % (*)
17. Jerry Coffin (C++): 244,82 % (*)
18. Bart van Ingen Schenau (C++): 378,50 % (*)

Using other libraries (not following the rules)

1. Blarrg (C++, reads from stdin): 76,67 % (*)
2. MrX 2 (C++, Linux pthreads): 98,69 %
3. MrX 1 (C++, Linux pthreads): 100,09 %
4. Fifoforlifo (C++, Boost 1.37): 101,74 % (*)