Thread overview | |||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
November 18, 2005 Complexity in docs | ||||
---|---|---|---|---|
| ||||
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 |
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tomás Rossi | 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 |
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tomás Rossi | 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
|
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Oskar Linde | 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 |
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Chris | 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 |
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tomás Rossi | 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 |
November 18, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tomás Rossi | 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
|
November 19, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sean Kelly | 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 |
November 19, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Tomás Rossi | 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 |
November 19, 2005 Re: Complexity in docs | ||||
---|---|---|---|---|
| ||||
Posted in reply to Chris | 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 |
Copyright © 1999-2021 by the D Language Foundation