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: h = Hash.new(0) # 0 is the default value if the key is not present Now you can do: h[0] += 3 #=> {0 => 3} h[1] = 4 #=> {0 => 3, 1 => 4} 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 } h[10] #=> 20 I guess in D you would create a struct that wraps an associative array and adds that logic.
Feb 08 2013