[fetchmail-devel] Some PATRICIA numbers

[Rainer W. <rwe...@ms...>]

The trie implementation is meanwhile complete and I have done some
preliminary benchmarks. I fear that the 'insert' cost will turn out to
be somewhat higher, but the results for searches are promising. The
largest .fetchids file I have here contains 7275 UIDs. Assuming the
trie has already been created, iterating over the input file a
thousand times and searching for every UID needs 3.93s on average,
meaning the average time for a single search is about 5.4E-7 seconds
(3Ghz P4). Doing a plain linear search for every UID needs about 16.6
seconds on average[*] or about 2.3E-4 seconds per search.

	[*] For ten searches. I didn't have the patience to wait for
	1000 :->