On 2/16/15 1:23 AM, Daniel Murphy wrote:
"bearophile" wrote in message news:[email protected]...
D associative arrays used to be O(1) amortized and O(n ln n) in worst
case.
No, they were still O(n) worst case, for a single bucket with a
degenerate binary tree.
IIRC, the AA code tried to make balanced trees, at least on rehash, but
I thought it did so proactively on insertion too.
But in any case, the reason AA's are so slow is because the load factor
is 4. As in, the AA will have 4x as many elements as buckets before it
increases buckets. I've brought it up before. Typically you want to keep
the number of elements per bucket near 1 for O(1) lookup.
-Steve
