Re: test for equality of the content of two AA

[Paolo Invernizzi via Digitalmars-d-learn]

On Wednesday, 26 October 2016 at 19:03:45 UTC, Ali Çehreli wrote:

On 10/26/2016 08:03 AM, Paolo Invernizzi wrote:

[...]


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);
}

[...]


Thank you Ali, very exhaustive!

Re: test for equality of the content of two AA

[Ali Çehreli via Digitalmars-d-learn]

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

test for equality of the content of two AA

[Paolo Invernizzi via Digitalmars-d-learn]

As the subject states, what is the best idiomatic way for doing 
that?


Thanks in advance
/Paolo