www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - best idiom for insert if not present; else use value in assoc array

reply "Dan" <dbdavidson yahoo.com> writes:
For an associative array, what is the best idiom that allows for 
checking if a key exists in the AA. If it does do something with 
the value, if not initialize the value and then do something with 
it.

In this code: http://dpaste.dzfl.pl/daab318f

How would this piece be improved? It looks like it would have to 
perform the hash and do a find 3 times:

     auto exists = (k in _dataMap);
     if(!exists) {
       _dataMap[k] = init;
       exists = (k in _dataMap);
     }
     ... use *exists

At a higher level and assuming the general goal of this basic 
struct is clear, any other suggestions welcome.

Also, an FYI to dpaste maintainer that the compiler service has 
been unavailable for a while.

Thanks
Dan
Feb 07 2013
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, February 07, 2013 21:20:46 Dan wrote:

 For an associative array, what is the best idiom that allows for
 checking if a key exists in the AA. If it does do something with
 the value, if not initialize the value and then do something with
 it.
 
 In this code: http://dpaste.dzfl.pl/daab318f
 
 How would this piece be improved? It looks like it would have to
 perform the hash and do a find 3 times:
 
 auto exists = (k in _dataMap);
 if(!exists) {
 _dataMap[k] = init;
 exists = (k in _dataMap);
 }
 ... use *exists
 
 At a higher level and assuming the general goal of this basic
 struct is clear, any other suggestions welcome.
 
 Also, an FYI to dpaste maintainer that the compiler service has
 been unavailable for a while.


Remove the useless parens around the in expression. :)

Seriously though, I believe that you're pretty much doing it exactly as its 
supposed to be done, except that you can avoid some of the extra overhead if 
don't need to refer to the actual element in the AA. If that's the case, you 
can do

T var;

if(auto found = k in _dataMap)
 var = *found;
else
{
 var = init;
 _dataMap[k] = var;
}

//...use var

Of course, if assigning T is expensive enough, that could actually be more 
expensive than your example, since an extra assignment is required.

Or, if you didn't care about actually putting it in the AA, you could use the 
get function.

auto var = _dataMap.get(k, init);

But I certainly agree that it would be nice if there were a function that 
inserted the element if it wasn't already there and then returns it regardless 
of whether it was there or not. I don't think that such a function exists 
though.

- Jonathan M Davis
Feb 07 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Jonathan M Davis:


 But I certainly agree that it would be nice if there were a 
 function that
 inserted the element if it wasn't already there and then 
 returns it regardless
 of whether it was there or not. I don't think that such a 
 function exists
 though.


Python dicts have a method that I don't use often that seems 
related to what you say:

setdefault(key[, default])

     If key is in the dictionary, return its value. If not, insert 
key with a value of default and return default. default defaults 
to None.


Adding some other AA function to object module is possible.

Bye,
bearophile
Feb 07 2013
prev sibling next sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/7/13, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 I don't think that such a function exists
 though.


UFCS would do it:

import std.traits;

auto ref set(Hash, Key, Val)(Hash hash, Key key, Val val)
    if (isAssociativeArray!Hash &&
        is(Key : KeyType!Hash) &&
        is(Val : ValueType!Hash))
{
    if (auto res = key in hash)
    {
        return res;
    }
    else
    {
        hash[key] = val;
        return key in hash;
    }
}
...

auto exists = _dataMap.set(k, init);

Note the use of "is(Val : ValueType!Hash)" which checks if Val can be
implicitly converted to the value type, it's to allow e.g. assigning
integrals to double.
Feb 07 2013
parent reply "Dan" <dbdavidson yahoo.com> writes:
On Thursday, 7 February 2013 at 20:46:31 UTC, Andrej Mitrovic 
wrote:


 auto ref set(Hash, Key, Val)(Hash hash, Key key, Val val)
     if (isAssociativeArray!Hash &&
         is(Key : KeyType!Hash) &&
         is(Val : ValueType!Hash))
 {
     if (auto res = key in hash)
     {
         return res;
     }
     else
     {
         hash[key] = val;
         return key in hash;
     }
 }


Definitely a convenient function, but I think what Jonathan and 
bearophile suggested was something more like:

auto ptrToValue = hash.insertDefaultOrFind(key, init)
*ptrToValue += additional;

and then on the first insert for a given key the hash is computed 
just once. I believe this would have to be done at the level of 
AssociativeArray and can not be done as a helper function, since 
this set helper is still doing 3 hashes/lookups.

Thanks
Dan
Feb 07 2013
parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 2/7/13, Dan <dbdavidson yahoo.com> wrote:

 I believe this would have to be done at the level of
 AssociativeArray and can not be done as a helper function, since
 this set helper is still doing 3 hashes/lookups.


Feel free to file an enhancement request.
Feb 08 2013
parent "Dan" <dbdavidson yahoo.com> writes:
On Saturday, 9 February 2013 at 00:54:58 UTC, Andrej Mitrovic 
wrote:

 Feel free to file an enhancement request.


http://d.puremagic.com/issues/show_bug.cgi?id=9491

Hopefully that is clear.
Feb 09 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, February 07, 2013 21:46:20 Andrej Mitrovic wrote:

 On 2/7/13, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 I don't think that such a function exists
 though.


 
 UFCS would do it:
 
 import std.traits;
 
 auto ref set(Hash, Key, Val)(Hash hash, Key key, Val val)
 if (isAssociativeArray!Hash &&
 is(Key : KeyType!Hash) &&
 is(Val : ValueType!Hash))
 {
 if (auto res = key in hash)
 {
 return res;
 }
 else
 {
 hash[key] = val;
 return key in hash;
 }
 }
 ...
 
 auto exists = _dataMap.set(k, init);
 
 Note the use of "is(Val : ValueType!Hash)" which checks if Val can be
 implicitly converted to the value type, it's to allow e.g. assigning
 integrals to double.


I'd probably just make it return Val*. I don't know what you gain by making it 
return auto ref.

But regardless, your function is just doing the same thing that the OP's code 
is doing except that it's encapsulating it nicely. So, it improves upon the 
OP's code but doesn't solve the primary complaint about efficiency. It should
be 
possible for the AA to implement set so that it doesn't require more than one 
lookup, whereas this does up to three.

- Jonathan M Davis
Feb 07 2013
prev sibling parent Ary Borenszweig <ary esperanto.org.ar> writes:
On 2/7/13 5:20 PM, Dan wrote:

 For an associative array, what is the best idiom that allows for
 checking if a key exists in the AA. If it does do something with the
 value, if not initialize the value and then do something with it.

 In this code: http://dpaste.dzfl.pl/daab318f

 How would this piece be improved? It looks like it would have to perform
 the hash and do a find 3 times:

      auto exists = (k in _dataMap);
      if(!exists) {
        _dataMap[k] = init;
        exists = (k in _dataMap);
      }
      ... use *exists

 At a higher level and assuming the general goal of this basic struct is
 clear, any other suggestions welcome.

 Also, an FYI to dpaste maintainer that the compiler service has been
 unavailable for a while.

 Thanks
 Dan


In Ruby you can do this:



Now you can do:




You can even initialize a hash with a lambda that computes the initial 
value based on a key:

h = Hash.new { |hash, key| hash[key] = key * 2 }



I guess in D you would create a struct that wraps an associative array 
and adds that logic.
Feb 08 2013