Associative Arrays max length? 32bit/64bit

monarch_dodra via Digitalmars-d digitalmars-d at puremagic.com
Sat May 17 23:57:26 PDT 2014


On Saturday, 17 May 2014 at 22:05:03 UTC, bearophile wrote:
> monarch_dodra:
>
>> for a sorted linked list (or forward iterators in general), 
>> you can find the result with O(N) *walk* iterations, but still 
>> only O(log(N)) *comparison* iterations.
>
> I think I have never implement such algorithm, but you are 
> right, and it's nice. Is Phobos using this idea somewhere? Are 
> D AAs using it?
>
> Bye,
> bearophile

It's not used in phobos (as far as I know of anyways). It *could* 
be implemented in SortedRange's BinaryFind though.

As for using it in AA's, you'd have to keep in mind you'd that (I 
think) you probably need a minimum size for the algorithm's lower 
complexity to kick in and actually give you better times.


More information about the Digitalmars-d mailing list