I ran the above described example applications for dictionary and sorted sequence with key type STR and information type INT and used single or combinations of Sather files in the same directory as input. Measuring the whole application with a time command was the easiest way to get the results. (I tried importing an external C function, which caused problems in the compiler.) If a text contains n words, m of which are unique, then the dictionary application performs n lookups and m inserts. The sorted sequence application performs n inserts, and 2q lookups, where q is the number of queries. (I have used q=10 in all test examples.)
Not surprisingly, the simple list had the worst performance among the three data structures. However, the red-black tree outperformed the skiplist with a tangible edge of 35experimental results delivered by the LEDA implementations. (The test programs are in the /prog section of the LEDA directory, e.g. in cschwarz/lib/LEDA-3.0. In those tests, other randomized data structures also have advantages over the deterministic ones.
The timings for the dictionary application in ms: data str. \ n | 109 471 1422 2845 ----------------------------------------------- red-black | 0.4 1.4 3.4 8.2 skiplist | 0.5 2.1 4.8 11.7 list l | 0.5 2.4 13.9 51.4 The timings for the sorted sequence application in ms, 10 queries: data str. \ n | 109 471 1422 2845 ----------------------------------------------- red-black | 0.3 0.8 1.8 4.4 skiplist | 0.4 1.1 2.9 6.7 list l | 0.7 3.7 31.9 152.6