On Sat, Dec 10, 2011 at 3:51 AM, Hrvoje Niksic <hnik...@xemacs.org> wrote: > The case of dicts which require frequent access, such as those used to > implement namespaces, is different, and more interesting. Those dicts > are typically quite small, and for them the difference between O(log n) > and O(1) is negligible in both theory (since n is "small", i.e. bounded) > and practice. In fact, depending on the details of the implementation, > the lookup in a small tree could even be marginally faster.
This is something where, I am sure, far greater minds than mine delve... but, would a splay tree be effective for name lookups? In most cases, you'll have a huge puddle of names of which you use the tiniest fraction; and a splay tree would, in effect, automatically optimize itself to handle tight loops. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
