Dictionary Tests with Random Numeric Keys

This page describes a set of experiments using a generator of Dictionary operations with random numeric keys. The generator was written by Marc Brooks with modifications by C. McGeoch. Send Cathy a note if you have questions or need help.

• Get the compressed tar file containing the random generator. Type

    uncompress dc_random.tar   (If your browser hasn't done it)
    tar -xf dc_random.tar
    cd dc_random 
    gcc random_dc.c -o rdc
  

• There are two shell scripts that generate the test inputs for the dictionary driver. The keys are real numbers which are to be treated as strings: when running the dictionary driver set the ky_type to str16.

• Typing dimacs_test1 will create 27 dictionary trace files in the subdirectory traces/. These represent 3 random trials at each of 3 problem sizes (N=1k, 10k, and 100k) with 3 kinds of problems. The file names are coded as follows:

       id      N inserts followed by N deletes.
       is      N inserts followed by N successful lookups.  
       iu      N inserts followed by N unsuccessful lookups. 
       

  When the trace files are ready, give them to your dictionary driver to run the dictionary experiments.

• Typing dimacs_test2 will create 27 more dictionary trace files in /traces: again, 3 random trials, 3 problem sizes (1k, 10k, 100k), and 3 kinds of problems. The file names are coded as follows:

    
      iid   N inserts followed by N repetitions of [ins del]  (3N total) 
      iisd  N inserts followed by N repetitions of [ins successful del]  
      iiud  N inserts followed by N repetitions of [in  unsuccessful delete]
      

  When the trace files are ready, give them to your dictionary driver to run the core experiments.

• You are strongly encouraged to create other dictionary tests using this problem generator. You can generate more random trials to improve your estimate of the mean, similar trials at larger problem sizes, or trials using different combinations of parameter settings.

Back to the Challenge.

Back to the Dictionary Tests.