About built-in AAs

[Andrew Wiley]

On Tue, Aug 16, 2011 at 7:29 PM, bearophile <bearophileHUGS at lycos.com>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.


The problem here is that algorithmic complexity doesn't really tell the
whole story. We can talk about what "should" be faster all day, but unless
we can prove that there's really a problem here, this doesn't seem like it's
worth worrying about.
And if it was changed in the past because the linked lists turned out to be
faster, I'd guess that actual benchmarking was probably used back then to
determine which was better.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20110816/27213dc8/attachment.html>