Message152033
On Thu, Jan 26, 2012 at 4:00 PM, Martin v. Löwis <report@bugs.python.org>wrote:
>
> Martin v. Löwis <martin@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 <report@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 |
|
Date |
User |
Action |
Args |
2012-01-26 21:04:28 | alex | set | recipients:
+ alex, lemburg, gvanrossum, tim.peters, loewis, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, vstinner, christian.heimes, benjamin.peterson, eric.araujo, grahamd, Arfrever, v+python, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5 |
2012-01-26 21:04:28 | alex | link | issue13703 messages |
2012-01-26 21:04:27 | alex | create | |
|