digitalmars.D.learn - Can the order in associative array change when keys are not midified?
- Idan Arye (3/3) Jan 01 2015 If I have an associative array and I only modify it's values,
- Andrej Mitrovic via Digitalmars-d-learn (4/7) Jan 01 2015 Associative arrays are not ordered at all.
- Peter Alexander (9/16) Jan 01 2015 The order is unspecified, but an iteration must iterate in *some*
- Idan Arye (11/30) Jan 01 2015 That's right.
- H. S. Teoh via Digitalmars-d-learn (54/62) Jan 01 2015 It's risky to rely on the order of values returned by an AA. It's
- Andrej Mitrovic via Digitalmars-d-learn (4/6) Jan 01 2015 This one works nicely on D1, I'd imagine the D2 port works just the same...
- Tobias Pankrath (4/12) Jan 01 2015 You could implement an OrderedMap!(Key, Value) via
- Andrej Mitrovic via Digitalmars-d-learn (4/6) Jan 01 2015 We could add this as an alias into Phobos or perhaps as just a
- Laeeth Isharc (18/24) Jan 01 2015 V good point.
- Tobias Pankrath (3/9) Jan 02 2015 Will do. Going to submit some documentation PRs anyway.
- Andrej Mitrovic via Digitalmars-d-learn (6/13) Jan 01 2015 Hmm yeah, that definitely wasn't ever specified. But remember that
- ketmar via Digitalmars-d-learn (10/13) Jan 01 2015 On Thu, 01 Jan 2015 12:32:33 +0000
- Steven Schveighoffer (7/9) Jan 02 2015 I would never make that assumption. An AA is free to rehash at any time,...
If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?
Jan 01 2015
On 1/1/15, Idan Arye via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?Associative arrays are not ordered at all. See the first note here: http://dlang.org/hash-map.html
Jan 01 2015
On Thursday, 1 January 2015 at 13:13:10 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:On 1/1/15, Idan Arye via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed. The spec doesn't say anything about this, although I would expect in practice that the order will not change. I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?Associative arrays are not ordered at all. See the first note here: http://dlang.org/hash-map.html
Jan 01 2015
On Thursday, 1 January 2015 at 13:39:57 UTC, Peter Alexander wrote:On Thursday, 1 January 2015 at 13:13:10 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:That's right. My use case is that I have a large AA where the values are numbers and the keys are strings, and I need to send it over network again and again. The values constantly change but the keys should remain the same(after an initial initialization process), so I don't want to always have to send the keys, which compose the larger part of the AA's size. If the order is fixed as long as the keys are fixed I can cache the keys order and send only the values(without having to sort them each time).On 1/1/15, Idan Arye via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed. The spec doesn't say anything about this, although I would expect in practice that the order will not change. I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?Associative arrays are not ordered at all. See the first note here: http://dlang.org/hash-map.html
Jan 01 2015
On Thu, Jan 01, 2015 at 04:17:39PM +0000, Idan Arye via Digitalmars-d-learn wrote: [...]My use case is that I have a large AA where the values are numbers and the keys are strings, and I need to send it over network again and again. The values constantly change but the keys should remain the same(after an initial initialization process), so I don't want to always have to send the keys, which compose the larger part of the AA's size. If the order is fixed as long as the keys are fixed I can cache the keys order and send only the values(without having to sort them each time).It's risky to rely on the order of values returned by an AA. It's implementation-dependent. Although currently we don't see any reason for ever changing the order, that doesn't guarantee that a future implementation with a new, innovative lookup algorithm, won't change it, since the spec says that AA's are inherently unordered. If you need consistent ordering of values, you probably want a different data structure, like an ordered map, instead of an AA. Alternatively, you can implement your own wrapper around the built-in AA's that keeps track of insertion order, something like this: struct MyAA(K,V) { static struct WrappedValue { WrappedValue* next; V value; alias value this; } private WrappedValue[K] impl; WrappedValue* first; void opIndexAssign(V value, K key) { auto val = WrappedValue(value); val.next = first; impl[key] = val; first = &impl[key]; } ref V opIndex(K key) { return impl[key].value; } property auto byValue() { static struct Range { WrappedValue* current; property bool empty() { return current is null; } property auto front() { return current.value; } void popFront() { current = current.next; } } return Range(first); } ... // other AA methods here } Some care would have to be taken care of if you need to support deleting AA keys (you have to relink stuff, so potentially you want a doubly-linked list instead of a singly-linked list here). But basically, something along these lines should give you an AA-like container that guarantees iteration order no matter what the underlying AA implementation is. T -- "No, John. I want formats that are actually useful, rather than over-featured megaliths that address all questions by piling on ridiculous internal links in forms which are hideously over-complex." -- Simon St. Laurent on xml-dev
Jan 01 2015
On 1/1/15, H. S. Teoh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:If you need consistent ordering of values, you probably want a different data structure, like an ordered mapThis one works nicely on D1, I'd imagine the D2 port works just the same: https://github.com/SiegeLord/Tango-D2/blob/d2port/tango/util/container/SortedMap.d
Jan 01 2015
On Thursday, 1 January 2015 at 18:08:52 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:On 1/1/15, H. S. Teoh via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:You could implement an OrderedMap!(Key, Value) via RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).If you need consistent ordering of values, you probably want a different data structure, like an ordered mapThis one works nicely on D1, I'd imagine the D2 port works just the same: https://github.com/SiegeLord/Tango-D2/blob/d2port/tango/util/container/SortedMap.d
Jan 01 2015
On 1/1/15, Tobias Pankrath via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:You could implement an OrderedMap!(Key, Value) via RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).We could add this as an alias into Phobos or perhaps as just a documentation line on the website.
Jan 01 2015
On Thursday, 1 January 2015 at 18:58:04 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:On 1/1/15, Tobias Pankrath via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:V good point. This is one of those small frictions that cumulatively raises the cost of adoption for newcomers who are not by nature hackers but want to get stuff done, and yet could be valuable members of the D community over time. For whatever reason, there is some resistance for many people to ask for help in a forum and it is easy to be overwhelmed and give up. Modern people don't have much tolerance for pain, even though that's an essential part of learning and being a developer. And compare python where you have OrderedDict and a search will find many examples of how to use it. I agree with comments about readability of library functions, but maybe also worth extending hints and tips for common patterns / code fragments. What is the protocol for contributing to the wiki? Can one just edit it ?You could implement an OrderedMap!(Key, Value) via RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).We could add this as an alias into Phobos or perhaps as just a documentation line on the website.
Jan 01 2015
On Thursday, 1 January 2015 at 18:58:04 UTC, Andrej Mitrovic via Digitalmars-d-learn wrote:On 1/1/15, Tobias Pankrath via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:Will do. Going to submit some documentation PRs anyway.You could implement an OrderedMap!(Key, Value) via RedBlackTree!(Tuple!(Key, Value), (a,b) => a[0] < b[0]).We could add this as an alias into Phobos or perhaps as just a documentation line on the website.
Jan 02 2015
On 1/1/15, Peter Alexander via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:The order is unspecified, but an iteration must iterate in *some* order. The question (if I've understood it correctly), is whether that order of iteration changes when the keys aren't changed.Hmm yeah, that definitely wasn't ever specified. But remember that there is also a .rehash() method. It's a bit tricky to work with AAs for sure..The spec doesn't say anything about this, although I would expect in practice that the order will not change. I've added a bug to track this omission from the spec: https://issues.dlang.org/show_bug.cgi?id=13923Thanks.
Jan 01 2015
On Thu, 01 Jan 2015 12:32:33 +0000 Idan Arye via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:If I have an associative array and I only modify it's values,=20 without changing the keys, can I assume that the order won't=20 change?please, don't: this is implementation-specific. druntime code can change (for example, by tracking access frequency and regrouping frequently accesed keys into clusters for better cache utilising), and your finely crafted code will start to fail mysteriously. it is safe to assume that after ANY change in AA *everything* is changed there. you'd better augment AA with some "change buffer" or use different data structure for your task.
Jan 01 2015
On 1/1/15 7:32 AM, Idan Arye wrote:If I have an associative array and I only modify it's values, without changing the keys, can I assume that the order won't change?I would never make that assumption. An AA is free to rehash at any time, for whatever reason. What I would say is that you can probably safely assume an AA will iterate in the same order as long as it hasn't been changed. If you need guaranteed ordering, use an array or a RedBlackTree. -Steve
Jan 02 2015