| |
| Posted by Ali Çehreli in reply to Paolo Invernizzi | PermalinkReply |
|
Ali Çehreli
Posted in reply to Paolo Invernizzi
| On 10/26/2016 08:03 AM, Paolo Invernizzi wrote:
> As the subject states, what is the best idiomatic way for doing that?
>
> Thanks in advance
> /Paolo
If you mean D's AAs, then that is already implemented:
void main() {
auto a = [ "hello" : 1, "world" : 2 ];
auto b = [ "world" : 2, "hello" : 1 ];
assert(a == b);
}
The source makes sense:
https://github.com/dlang/druntime/blob/master/src/rt/aaA.d#L615
* First check that the lengths are equal
* Then check each element
The last step is already fast without needing any other data structure (e.g. one may imagine a sorted array) because hash table lookup is O(1) and there are N elements that needs to be processed (i.e. compared), so the whole operation must be O(N).
If the equality comparison is very frequent, then a hash table that maintains a hash of all keys and values can be used, which would be O(1). (As far as I know D's AAs don't have such a feature.) This would make the comparison of non-equal tables O(1) but if this overall hash were equal between two tables, one would still have to compare every element to be sure, which would be O(N).
Ali
|