www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - AA deterministic order ?

reply user-6431 <user-6431 nowhere.kl> writes:
I know that AA items order does not follow the additions but is 
the order deterministic ?

For example for a given set of items, will they always be ordered 
in the same way ? (I mean whatever is the way I append them to 
the AA).
Nov 25 2015
next sibling parent cym13 <cpicard openmailbox.org> writes:
On Wednesday, 25 November 2015 at 20:24:25 UTC, user-6431 wrote:
 I know that AA items order does not follow the additions but is 
 the order deterministic ?

 For example for a given set of items, will they always be 
 ordered in the same way ? (I mean whatever is the way I append 
 them to the AA).
No it's not. The way it works is that a hash of the key is computed and the comparison of hashes gives the position of the new AA element in the structure. Two keys can have the same hash: in case of collision the later is put to another place, so the order is dependant of the order of insertion. Either way you can't and shouldn't rely on any sort of determinism with the order of AA keys, that's just not the way they work and any determinism is subject to change. On another note if the subject proves interesting to you you may want to read the AA implementation ( https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d ) and see this video which describes how it works in python (not exactly the same as in D but the spirit is there and the video is of quality anyway): https://www.youtube.com/watch?v=C4Kc8xzcA68
Nov 25 2015
prev sibling next sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Nov 25, 2015 at 08:24:24PM +0000, user-6431 via Digitalmars-d-learn
wrote:
 I know that AA items order does not follow the additions but is the
 order deterministic ?
 
 For example for a given set of items, will they always be ordered in
 the same way ? (I mean whatever is the way I append them to the AA).
It is deterministic in the current implementation, but this should not be relied on. A future implementation may change the order without any warning (e.g., upgrade druntime, and AA order becomes different from before). A future implementation may also return items in a different order each time you iterate the same AA (unlikely, but in theory possible). Generally, if you want any kind of ordering on your items, AA's are not a good container to use. A better container would be some kind of tree-based structure that has a guaranteed ordering. If you need the O(1) access speed of AA's but still want deterministic ordering, you could perhaps consider using the AA as an "index" into the actual container (say, an array or tree), so that individual lookups are fast, but when you need to iterate the entire set you have full control over the ordering. T -- Turning your clock 15 minutes ahead won't cure lateness---you're just making time go faster!
Nov 25 2015
prev sibling parent cym13 <cpicard openmailbox.org> writes:
On Wednesday, 25 November 2015 at 20:24:25 UTC, user-6431 wrote:
 I know that AA items order does not follow the additions but is 
 the order deterministic ?

 For example for a given set of items, will they always be 
 ordered in the same way ? (I mean whatever is the way I append 
 them to the AA).
Minimal example showing a collision: void main() { import std.array; int[int] aa_1; int[int] aa_2; aa_1[0] = 42; aa_1[8] = 42; aa_2[8] = 42; aa_2[0] = 42; assert(aa_1.byKey.array == [0, 8]); assert(aa_2.byKey.array == [8, 0]); }
Nov 25 2015