On 8/17/11 9:04 AM, Steven Schveighoffer wrote:
On Wed, 17 Aug 2011 00:15:38 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> wrote:
On 8/16/11 9:29 PM, bearophile wrote:
Walter Bright:
I think there are search trees like the Red-Black ones that
guarantee a O(n ln n) worst case. I am wrong?
Just feed it more data.
If you feed it more data, even if all items pruce collision because
they all hash to the same bucket, if you use Red-Black trees to
handle the items in the same bucket you keep having a O(n ln n)
behaviour, that's usually fast enough. With Python and the new D AAs
you instead get a quadratic one. This quadratic behaviour gives
troubles way before the physical RAM is exhausted.
Bye,
bearophile
Let's please stop this. Many of us, including yourself, noticed the
relatively poor performance of D's previous hashtables compared to
other languages. Switching to singly-list collision handling marked an
improvement. Now a lot of data structure designs have a worst-case
that makes them perform worse than others. If you worry about attacks,
please implement your own hashtable. If we switch back to the old
implementation, you'll complain again about D's hashtables being
slower than Python's, thus closing a years-long cycle.
Yes, but let's not forget the one valid request out of all of this -- if
trees are no longer being used, opEquals should be used insted of opCmp.
This allows more possible key types (which don't define an ordering). I
think this would be a simple druntime change.
-Steve
Yah, we should put that on the list of things to do on the Wiki. Wait,
where the heck is that? :o)
Andrei
