On Sunday, 29 March 2015 at 22:32:34 UTC, Martin Nowak wrote:
On 03/29/2015 05:19 PM, w0rp wrote:
4. I ended up writing my own library hashmap, which when I
tested ages
ago competed with the standard associative array in terms of
performance. This allows me to mark many things @safe pure
nothrow.
Destroy!
Nice docs.
Always use open addressing when implementing a hash table.
https://github.com/D-Programming-Language/dmd/pull/4088
https://github.com/higgsjs/Higgs/pull/170
You probably beat my implementation in terms of speed now. I
think the only thing
I did quite differently from the standard implementation was use
& 2 for computing the hash index instead of a divide, as that was
the method OpenJDK used for its hashmap.
Also, I was able to implement setDefault in a hopefully
efficient
manner. I have tried to push setDefault as an awesome thing a
few times,
but I've never been able to explain why it's good eloquently.
I guess that's the counterpart to `get(key, default)` that also
inserts
the default value. That's a very much needed primitive for our
AA,
because currently you end up doing at least 1 unnecessary
lookup.
Often I even write this.
auto p = key in aa;
if (p is null)
{
aa[key] = default;
p = key in aa;
}
It's called getOrElseUpdate in Scala, but I'd prefer getOrSet.
http://www.scala-lang.org/api/2.10.1-RC1/scala/collection/mutable/HashMap.html#getOrElseUpdate(A,⇒B):B
Yeah, that's the one. I personally don't really care what the
name is. 'setdefault' is the Python name for it. Only we can do
better than Python, because we have the lazy keyword. For which
I'll say, "One magical day, the compiler can generate special
code for this." As you say, it's special in that it has the
ability to only compute the hash once when implemented with
direct access to the hashtable.