www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Associative array key order

reply "Daniel Kozak" <kozzi11 gmail.com> writes:
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?
Jul 31 2013
next sibling parent reply "Daniel Kozak" <kozzi11 gmail.com> writes:
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?
Jul 31 2013
next sibling parent reply "Dicebot" <public dicebot.lv> writes:
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.
Jul 31 2013
next sibling parent reply "Daniel Kozak" <kozzi11 gmail.com> writes:
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 :)
Jul 31 2013
parent "Andrej Mitrovic" <andrej.mitrovich gmail.com> writes:
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.
Jul 31 2013
prev sibling next sibling parent reply "Daniel Kozak" <kozzi11 gmail.com> writes:
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.


I implemented my own OrderedAA type, which is able to preserve 
insert order and is a little faster and take less memory(30%) 
then the builtin one :-).

But definitly there will be some cases where my own 
implementation doesn't beat the builtin one.
Aug 22 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 22 August 2013 at 07:59:05 UTC, Daniel Kozak wrote:

 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.


 I implemented my own OrderedAA type, which is able to preserve 
 insert order and is a little faster and take less memory(30%) 
 then the builtin one :-).

 But definitly there will be some cases where my own 
 implementation doesn't beat the builtin one.


Nice to hear. Perhaps you could share the implementation with us? 
Even if its not perfect, I'm curious to know how you went at it.
Aug 22 2013
next sibling parent "Daniel Kozak" <kozzi11 gmail.com> writes:
On Thursday, 22 August 2013 at 08:41:13 UTC, monarch_dodra wrote:

 On Thursday, 22 August 2013 at 07:59:05 UTC, Daniel Kozak wrote:

 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.


 I implemented my own OrderedAA type, which is able to preserve 
 insert order and is a little faster and take less memory(30%) 
 then the builtin one :-).

 But definitly there will be some cases where my own 
 implementation doesn't beat the builtin one.


 Nice to hear. Perhaps you could share the implementation with 
 us? Even if its not perfect, I'm curious to know how you went 
 at it.


Yes, it should not be a problem. This evening I should have some 
more spare time. So I do some cleanups and push it somewhere.
Aug 22 2013
prev sibling parent reply "Daniel Kozak" <kozzi11 gmail.com> writes:
https://github.com/Kozzi11/Trash/blob/master/util/orderedaa.d

On Thursday, 22 August 2013 at 08:41:13 UTC, monarch_dodra wrote:

 On Thursday, 22 August 2013 at 07:59:05 UTC, Daniel Kozak wrote:

 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.


 I implemented my own OrderedAA type, which is able to preserve 
 insert order and is a little faster and take less memory(30%) 
 then the builtin one :-).

 But definitly there will be some cases where my own 
 implementation doesn't beat the builtin one.


 Nice to hear. Perhaps you could share the implementation with 
 us? Even if its not perfect, I'm curious to know how you went 
 at it.
Aug 23 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Aug 23, 2013 at 01:54:27PM +0200, Daniel Kozak wrote:

 https://github.com/Kozzi11/Trash/blob/master/util/orderedaa.d


[...]

Neat!

Is a doubly-linked list really necessary for the hash buckets? You could
save on some memory & improve performance slightly if you use a
singly-linked list for the buckets, but still keep the left/right
pointers for retaining insertion order. It will also simplify your code
a bit.


T

-- 
If Java had true garbage collection, most programs would delete themselves upon
execution. -- Robert Sewell
Aug 23 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 ...


On this subject, I added this request to Bugzilla:
http://d.puremagic.com/issues/show_bug.cgi?id=10733

Bye,
bearophile
Aug 23 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
 H. S. Teoh:

 ...




Your answer was really too much short, so I have asked you  a 
question in that enhancement request :-)

Bye,
bearophile
Aug 23 2013
prev sibling parent "Daniel Kozak" <kozzi11 gmail.com> writes:
When I do some cleanups, I find some bugs and after fixing them, 
my own OrderedAA implementation does not beat builtin hash 
anymore :(. But speed is still really near to builtin AA's.

On Thursday, 22 August 2013 at 07:59:05 UTC, Daniel Kozak wrote:

 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.


 I implemented my own OrderedAA type, which is able to preserve 
 insert order and is a little faster and take less memory(30%) 
 then the builtin one :-).

 But definitly there will be some cases where my own 
 implementation doesn't beat the builtin one.
Aug 23 2013
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
On Jul 31, 2013, at 7:55 AM, Dicebot <public dicebot.lv> 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?


=20
 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.

This seems more likely to be a library type.  I have something like this =
that I use very frequently at work where the behavior is pluggable, so =
it can be used as a cache that automatically does LIFO/FIFO eviction =
according to an age window, number of entries, etc.  Or none of those if =
all you want is a plain old hashtable.  It's not a tremendous amount of =
work to adapt an existing implementation to work this way.  The only =
annoying bit I ran into (at least with C++) is that the symbol lookup =
rules pretty much prevent overrides of existing functions to be mixed in =
via the policies.  Does alias this work around this problem in D?  I've =
never tried.=
Aug 23 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Aug 23, 2013 at 11:22:47AM -0700, Sean Kelly wrote:

 On Jul 31, 2013, at 7:55 AM, Dicebot <public dicebot.lv> 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.


 
 This seems more likely to be a library type.  I have something like
 this that I use very frequently at work where the behavior is
 pluggable, so it can be used as a cache that automatically does
 LIFO/FIFO eviction according to an age window, number of entries, etc.
 Or none of those if all you want is a plain old hashtable.  It's not a
 tremendous amount of work to adapt an existing implementation to work
 this way.  The only annoying bit I ran into (at least with C++) is
 that the symbol lookup rules pretty much prevent overrides of existing
 functions to be mixed in via the policies.  Does alias this work
 around this problem in D?  I've never tried.


In http://d.puremagic.com/issues/show_bug.cgi?id=10733 bearophile and I
discussed code reuse between the current AA and an ordered AA
implementation. It appears that a more fundamental structure is the Set,
where the key is the value. An AA can be implemented in terms of a Set,
by making the set element a struct containing a key and value field,
with a custom toHash() and opCmp() that only hashes/compares the key
part.

By adding a pair of pointers to this customized set element, we can make
an ordered AA in terms of Set.

Plus, a Set is something that's very useful on its own as well.


T

-- 
Береги платье снову, а здоровье смолоду.
Aug 23 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jul 31 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 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
Jul 31 2013
prev sibling parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
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
Jul 31 2013
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.
Jul 31 2013
parent Ary Borenszweig <ary esperanto.org.ar> writes:
On 7/31/13 12:56 PM, H. S. Teoh wrote:

 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


Sorry, I meant doubly-linked list. But yeah, two pointers seem now too 
much overhead.
Jul 31 2013
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Ary Borenszweig:


 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).


If it's a singly linked list how do you remove a key from the 
associative array keeping the list coherent? How do you know 
where is the precedent to remove an item from the linked list?
Using the 'deleted' tag on AA items is enough to skip the deleted 
items when you scan the singly linked list, but when you re-use 
that space I think you mess things up. One way to solve it is to 
never re-use locations, but this is bad if you want to add and 
remove many items.



 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).


Python has such data structure in the standard library, and 
thanks to dynamic typing it's transparently compatible with 
associative arrays, so when you need it you have it.
I have often needed such data structure, but it's not always 
needed, I need it probably less than 5% of the times.
Python uses associative arrays all the time, they must be as fast 
as possible, so it's a good idea to not add that feature to the 
standard associative arrays. This is true for the built-in 
associative arrays too, despite they should be designed for 
flexibility first and despite D doesn't use associative arrays 
for basic language purposes, as Python does (symbol lookup for 
variables!).

I have added a small enhancement request to Bugzilla:
http://d.puremagic.com/issues/show_bug.cgi?id=10733

Bye,
bearophile
Jul 31 2013
prev sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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.
Jul 31 2013