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

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

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.

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

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

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

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.

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.

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.