<br><br><div class="gmail_quote">On Tue, Aug 16, 2011 at 7:29 PM, bearophile <span dir="ltr"><<a href="mailto:bearophileHUGS@lycos.com">bearophileHUGS@lycos.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Walter Bright:<br>
<div class="im"><br>
> > I think there are search trees like the Red-Black ones that guarantee a O(n ln n) worst case. I am wrong?<br>
><br>
> Just feed it more data.<br>
<br>
</div>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.</blockquote>

<div><br></div><div>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.</div>

<div>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.</div></div><br>