STL: map with string as key — access speedup

Author:	Wojciech Muła
Added on:	2010-04-03

The idea is quite simple: we do not have a single stl::map<string, something>, but a vector of maps, indexed with O(1) time — each map stores keys sharing certain properties. Drawback: additional memory.

I've tested following grouping schemes:

1. the length of string,
2. the first letter of string (one level trie),
3. both length and the first letter.

Third is the fastest — around 60% faster then plain std::map from GCC (red-black tree).

Tests: my program read plain text (I've used The Illiad from http://gutenberg.org), text is split into words (~190000) and then each words is inserted into a dictionary (~28000 distinct words); then the same words are searched in dictionaries. Table below summarizes results on my computer (gcc 4.3.4 from Cygwin).

data struct	running time [ms]			speedup [%]
	min	avg	max	min	avg	max
inserting
std::map	269	287	355	100	100	100
first char	218	241	395	81	84	111
length	218	240	345	81	84	97
len./char	165	172	207	61	60	58
searching
std::map	295	322	483	100	100	100
first char	243	263	460	82	82	95
length	238	248	292	80	77	60
len./char	184	190	241	62	60	50

Download test program.