Thread overview | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
July 31, 2013 Associative array key order | ||||
---|---|---|---|---|
| ||||
D: foreach(key, val; ["query" : 1, "count" : 2]) writeln(key); // print count query foreach(key, val; ["count" : 1, "query" : 2]) writeln(key); // print count query too PHP: foreach(["query" => 1,"count"=>2] as $key => $val) echo $key; // print query count foreach(["count" => 1,"query"=>2] as $key => $val) echo $key; is there a way for AA to change order? |
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel Kozak | D: foreach(key, val; ["query" : 1, "count" : 2]) writeln(key); // print count query foreach(key, val; ["count" : 1, "query" : 2]) writeln(key); // print count query too PHP: foreach(["query" => 1,"count"=>2] as $key => $val) echo $key; // print query count foreach(["count" => 1,"query"=>2] as $key => $val) echo $key; // print count query is there a way for AA to behave same as PHP? |
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel Kozak | On Wednesday, 31 July 2013 at 14:43:21 UTC, Daniel Kozak wrote:
> is there a way for AA to behave same as PHP?
I doubt it. This snippet suggests that AA's in PHP are not simply AA's and do additionally track insertion order (or use some similar trick). Data in associative arrays is organized in a way that allows fast key lookup and iterating in an original order requires tracking extra state. Contrary to PHP, D does care about performance so I see no way this can happen automatically.
There is a good chance that if you rely on key order, you don't really need an AA but plain array of key-value tuples instead.
|
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel Kozak | On Wed, Jul 31, 2013 at 04:41:14PM +0200, Daniel Kozak wrote: > > D: > > foreach(key, val; ["query" : 1, "count" : 2]) writeln(key); // print > count query > foreach(key, val; ["count" : 1, "query" : 2]) writeln(key); // print > count query too > > PHP: > foreach(["query" => 1,"count"=>2] as $key => $val) > echo $key; // print query count > foreach(["count" => 1,"query"=>2] as $key => $val) echo $key; > > > is there a way for AA to change order? AA's in D are unordered. If you want a specific order, you should use an array, or sort the AA keys before looping over them. T -- I see that you JS got Bach. |
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dicebot | On Wednesday, 31 July 2013 at 14:55:55 UTC, Dicebot wrote:
> On Wednesday, 31 July 2013 at 14:43:21 UTC, Daniel Kozak wrote:
>> is there a way for AA to behave same as PHP?
>
> I doubt it. This snippet suggests that AA's in PHP are not simply AA's and do additionally track insertion order (or use some similar trick). Data in associative arrays is organized in a way that allows fast key lookup and iterating in an original order requires tracking extra state. Contrary to PHP, D does care about performance so I see no way this can happen automatically.
>
> There is a good chance that if you rely on key order, you don't really need an AA but plain array of key-value tuples instead.
Thanks I will use plain array, it is not perfect but better than nothing :)
|
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel Kozak | On Wednesday, 31 July 2013 at 15:00:34 UTC, Daniel Kozak wrote:
> Thanks I will use plain array, it is not perfect but better than nothing :)
For some reason this (unordered keys) wasn't documented on the website, but it will be soon.
|
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Daniel Kozak | Daniel Kozak:
> is there a way for AA to behave same as PHP?
D associative arrays are based on hashing, so they do not keep the order of the items. This is true in Python too. The Python standard library has a hash-based ordered dict that keeps the insertion order of the keys. There is no such data structure in Phobos.
You could write one yourself (wrapping an associative array and using a linked list. I remember there is a trick to find the address of a D associative array key given its value address, but I don't remember it and it's not portable).
An alternative solution is to use the Phobos AVL-based tree as an associative array, but it's less convenient and the search complexity is logarithmic instead of constant in the average case.
Bye,
bearophile
|
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | > I remember there is a trick to find the address of a D associative array key given its value address,
Perhaps you need a better explanation for that. Let's say your data structure is:
final class OrderedAA(TK, TV) {
struct MV {
TV item;
MV* pred, succ;
}
private MV[TK] data;
...
}
it's a wrapper to a built-in associative array. Each value is a struct that beside the original value contains a pointer to the precedent and successive MV, in a doubly linked list.
The member functions of OrderedAA that add or remove items from the associative array manage the linked list of values. The iteration is a range that follows the linked list. But this way you only scan the values... To also scan keys or key-val pairs you have to find the pointer to the key.
Maybe it's worth adding in Bugzilla an ehnancement request for a portable way to find that pointer... to implement a hash-based ordered associative array in library code.
Bye,
bearophile
|
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | On 7/31/13 12:05 PM, bearophile wrote: > Daniel Kozak: > >> is there a way for AA to behave same as PHP? > > D associative arrays are based on hashing, so they do not keep the order > of the items. This is true in Python too. The Python standard library > has a hash-based ordered dict that keeps the insertion order of the > keys. There is no such data structure in Phobos. However in Ruby 1.9 they are ordered. You only need to store in each bucket entry a pointer to the next bucket. Then traversing the hash is super fast (just follow the links) while preserving insertion order. Accessing by key still uses the buckets and entries (if that's how AAs are implemented in D). I don't think adding a pointer to each bucket entry hurts performance that much, and having traversal by insertion order is pretty common (in my opinion). To see a sample code for this: https://github.com/manastech/crystal/blob/master/std/hash.cr#L28 |
July 31, 2013 Re: Associative array key order | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ary Borenszweig | On Wed, Jul 31, 2013 at 12:51:25PM -0300, Ary Borenszweig wrote: > On 7/31/13 12:05 PM, bearophile wrote: > >Daniel Kozak: > > > >> is there a way for AA to behave same as PHP? > > > >D associative arrays are based on hashing, so they do not keep the order of the items. This is true in Python too. The Python standard library has a hash-based ordered dict that keeps the insertion order of the keys. There is no such data structure in Phobos. > > However in Ruby 1.9 they are ordered. > > You only need to store in each bucket entry a pointer to the next bucket. Then traversing the hash is super fast (just follow the links) while preserving insertion order. Accessing by key still uses the buckets and entries (if that's how AAs are implemented in D). > > I don't think adding a pointer to each bucket entry hurts performance that much, and having traversal by insertion order is pretty common (in my opinion). [...] It does. What do you do when you delete entries? T -- Windows 95 was a joke, and Windows 98 was the punchline. |
Copyright © 1999-2021 by the D Language Foundation