On 9/1/05, Raymond Hettinger <[EMAIL PROTECTED]> wrote: > The goal is to determine whether the setobject.c implementation would be > improved by recoding the set_lookkey() function to optimize key > insertion order using Brent's variation of Algorithm D (See Knuth vol. > III, section 6.4, page 525).
Brent's variation depends on the next probe position for a key being derivable just from the key and its current position. The use of perturbation in set_lookkey() prevents that, as we cannot say, given a key at a certain position, where the next probe location for that key would have been, without doing a complete lookup of that key (obviously too expensive). It would be interesting to see whether Brent's variation or perturbation give better expected overall performance -- the latter may well prove better in most cases, as it should reduce the number of probes needed for both successful and unsuccessful lookups, while Brent's variation only speeds up successful lookups. Well, this sort of question is what the experiment is meant to resolve, no? _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
