digitalmars.D.learn - test for equality of the content of two AA
- Paolo Invernizzi (4/4) Oct 26 2016 As the subject states, what is the best idiomatic way for doing
- =?UTF-8?Q?Ali_=c3=87ehreli?= (22/25) Oct 26 2016 If you mean D's AAs, then that is already implemented:
- Paolo Invernizzi (2/11) Oct 30 2016 Thank you Ali, very exhaustive!
As the subject states, what is the best idiomatic way for doing that? Thanks in advance /Paolo
Oct 26 2016
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 /PaoloIf 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
Oct 26 2016
On Wednesday, 26 October 2016 at 19:03:45 UTC, Ali Çehreli wrote:On 10/26/2016 08:03 AM, Paolo Invernizzi wrote:Thank you Ali, very exhaustive![...]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); } [...]
Oct 30 2016