Alex Gaynor <alex.gay...@gmail.com> added the comment: On Thu, Jan 26, 2012 at 4:00 PM, Martin v. Löwis <rep...@bugs.python.org>wrote:
> > Martin v. Löwis <mar...@v.loewis.de> added the comment: > > I'd like to propose an entirely different approach: use AVL trees for > colliding strings, for dictionaries containing only unicode or byte strings. > > A prototype for this is in > http://hg.python.org/sandbox/loewis/branches#avl > It is not fully working yet, but I'm now confident that this is a feasible > approach. > > It has the following advantages over the alternatives: > - performance in case of collisions is O(log(N)), where N is the number of > colliding keys > - no new exceptions are raised, except for MemoryError if it runs out of > memory for allocating nodes in the tree > - the hash values do not change > - the dictionary order does not change as long as no keys collide on hash > values (which for all practical purposes should mean that the dictionary > order does not change in all places where it matters) > > ---------- > nosy: +loewis > > _______________________________________ > Python tracker <rep...@bugs.python.org> > <http://bugs.python.org/issue13703> > _______________________________________ > Martin, What happens if, instead of putting strings in a dictionary directly, I have them wrapped in something. For example, the classes Antoine and I pasted early. These define hash and equal as being strings, but don't have an ordering. Alex ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue13703> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
