Is there somewhere in the docs something about the complexity of operations?

For example:
What is the complexity for associative array operations? (I could guess it's
implemented as a map (upon a tree) so it has map complexities but thas's a
guess).

IMO (as Stroustrup did with stl) it's a MUST to specify complexity of
non-trivial operations and since D has complex (non-constant-time) features
inside the language (e.g. associative arrays), it should stipulate time
complexity of operations (and space complexity as well if relevant).

Regards

Tom

In article <dll6iq$1n1u$1@digitaldaemon.com>, Tomás Rossi says...
>
>Is there somewhere in the docs something about the complexity of operations?

Not as far as I know.

>For example:
>What is the complexity for associative array operations? (I could guess it's
>implemented as a map (upon a tree) so it has map complexities but thas's a
>guess).

Associative arrays are implemented as hash-tables, i.e. O(1).
(IIRC, the hash table nodes are sorted for each bucket, so even if all indices
hash to the same value, you get O(log n). But doing binary search is probably
reducing the performance when you have a good hash function.)

/Oskar

On Fri, 18 Nov 2005 18:29:46 +0000 (UTC), Tomás Rossi
<Tomás_member@pathlink.com> wrote:

>Is there somewhere in the docs something about the complexity of operations?
>
>For example:
>What is the complexity for associative array operations? (I could guess it's
>implemented as a map (upon a tree) so it has map complexities but thas's a
>guess).
the implimentation for them can be found in dmd/src/phobos/internal. Like Oskar said, it's a hashtable.


Chris

In article <dll7fq$1nn2$1@digitaldaemon.com>, Oskar Linde says...
>
>In article <dll6iq$1n1u$1@digitaldaemon.com>, Tomás Rossi says...
>>
>>Is there somewhere in the docs something about the complexity of operations?
>
>Not as far as I know.
>
>>For example:
>>What is the complexity for associative array operations? (I could guess it's
>>implemented as a map (upon a tree) so it has map complexities but thas's a
>>guess).
>
>Associative arrays are implemented as hash-tables, i.e. O(1).
>(IIRC, the hash table nodes are sorted for each bucket, so even if all indices
>hash to the same value, you get O(log n). But doing binary search is probably
>reducing the performance when you have a good hash function.)

Ok a hash table, don't know why didn't think about it before. Certainly I write without thinking first :). But still my concern could be other peoples concern so it should be documented as well as other non-trivial features/operations (if there is more).

Tom

In article <8a9sn1553k8psuebi8ff1msi0inb4i4dcu@4ax.com>, Chris says...
>
>On Fri, 18 Nov 2005 18:29:46 +0000 (UTC), Tomás Rossi
><Tomás_member@pathlink.com> wrote:
>
>>Is there somewhere in the docs something about the complexity of operations?
>>
>>For example:
>>What is the complexity for associative array operations? (I could guess it's
>>implemented as a map (upon a tree) so it has map complexities but thas's a
>>guess).
>the implimentation for them can be found in dmd/src/phobos/internal. Like Oskar said, it's a hashtable.

Ok, but why should I be looking at the implementation when searching for complexities? Should be documented (aren't them or am I getting all wrong?)

Tom

Tomás Rossi wrote:
> Is there somewhere in the docs something about the complexity of operations?
> 
> For example: What is the complexity for associative array operations? (I could guess it's
> implemented as a map (upon a tree) so it has map complexities but thas's a
> guess). 

AA's are implemented as a chaining hash table with binary trees replacing the slists (thus the need for opCmp instead of opEquals for stored objects).  So AA operations should be O(1).  Personally, I don't understand the choice of btrees over slists as it seems to expect that the hashing algorithm won't provide a good distribution.  I'd rather lose the need for an extra pointer or two per node if possible.  Though I suppose the tree could be implemented in an array to save memory as well.

> IMO (as Stroustrup did with stl) it's a MUST to specify complexity of
> non-trivial operations and since D has complex (non-constant-time) features
> inside the language (e.g. associative arrays), it should stipulate time
> complexity of operations (and space complexity as well if relevant).

Agreed.  Complexity constraints should be present in documentation whenever possile.  This is just another thing that has been ignored in favor of more substantial updates.


Sean

On Fri, 18 Nov 2005 19:19:38 +0000 (UTC), Tomás Rossi
<Tomás_member@pathlink.com> wrote:
>Ok, but why should I be looking at the implementation when searching for complexities? Should be documented (aren't them or am I getting all wrong?)

I  just mentioned it as an fyi. I do agree with you that complexity should be documented. It would give you a general idea of what to stay away from when writing high performance code.

Chris

Sean Kelly wrote:

[...]
> So AA operations should be O(1).

A clear maybe.

> Personally, I don't understand the choice of btrees over slists as it seems to expect that the hashing algorithm won't provide a good distribution.

The hash function walter uses is the adress of the element inserted, that is as fast as can be---and bad in terms of distribution over the table. But although the distribution is bad the probability is close to zero, that any bin contains more than 16 elements. Although the unbalanced binary tree Walter has choosen for the resolution of collisions is bad as hell in theory it performs very well under the constraints given.

Let a be the number of accesses to the n element in the AA and let r be the number of rehashes of the AA, then the runtime in total is O (a+r*n), the runtime for a single access is O(n) because an automatic rehash might occur, and the amortized runtime for a single access is O(1+r/ae), where ae is the minimal number of accesses to an element in the AA, of course ae>=1.

Therefore the time bound for an access to an element in the AA is amortized O(1) if and only if the number of rehashes to the AA can be bound by a constant.

-manfred

In article <dll9ga$1pmq$1@digitaldaemon.com>, Tomás Rossi says...
>
>In article <8a9sn1553k8psuebi8ff1msi0inb4i4dcu@4ax.com>, Chris says...
>>
>>On Fri, 18 Nov 2005 18:29:46 +0000 (UTC), Tomás Rossi
>><Tomás_member@pathlink.com> wrote:
>>
>>>Is there somewhere in the docs something about the complexity of operations?
>>>
>>>For example:
>>>What is the complexity for associative array operations? (I could guess it's
>>>implemented as a map (upon a tree) so it has map complexities but thas's a
>>>guess).
>>the implimentation for them can be found in dmd/src/phobos/internal. Like Oskar said, it's a hashtable.
>
>Ok, but why should I be looking at the implementation when searching for complexities? Should be documented (aren't them or am I getting all wrong?)
>
>Tom

If you're reading the docs and it occurs to you that some important informatin is lacking you can click on the "Comments" link at the top of the page. In the wiki, you can add a comment about what you think needs to be added (whether it's something you know or something you'd like to know). Walter knows these wiki comment pages are there and he integrates new material from them from time to time.

Home  | Search  | D  | Comments <---

Or you can ask here and maybe has already figured out where the answer is by studying the code of Phobos or the front end.

jcc7

In article <uhfsn1p10c1jan97n6lv7f8kd8eqp1t9k0@4ax.com>, Chris says...
>
>On Fri, 18 Nov 2005 19:19:38 +0000 (UTC), Tomás Rossi
><Tomás_member@pathlink.com> wrote:
>>Ok, but why should I be looking at the implementation when searching for complexities? Should be documented (aren't them or am I getting all wrong?)
>
>I  just mentioned it as an fyi.

Unfortunately, that wasn't the first time someone got yelled at for trying to help. ;)

>I do agree with you that complexity
>should be documented. It would give you a general idea of what to stay
>away from when writing high performance code.
>
>Chris

It's not in the official docs yet (and it'll probably quite a while before it
is), but it's already in the un-official docs (due to the generous contributions
from this newsgroup):
http://www.prowiki.org/wiki4d/wiki.cgi?DocComments/Arrays#ComplexityofAssociativeArrayOperations

jcc7