CODEWITHSUNDEEP
rubyhashkeyreverse-lookup
MarioDS
MarioDS

Reputation: 13073

How expensive is the "key" function of a Ruby hash?

I'm using a couple of Hashes where the values of some hashes are the key of others.

I need to use key a couple of times to get the key for a value so that I can use it to access something in another hash.

I was wondering what kind of a performance impact this could possibly have. In my situation, these hashes are few in number and the contents are small, but I want to know theoretically.

Should I avoid using this too much? How does it perform compared to getting the value for a key?

Upvotes: 4

Views: 392

Answers (2)

the Tin Man
the Tin Man

Reputation: 160631

Think of it this way: you're occasionally doing an extra step to get the value. That's what happens any time you use a conditional test and add a couple steps to a computation.

It's obvious there's a little overhead associated with it, but worrying about it at this point is premature optimization. You CAN get a feel for the difference, by using the Benchmark class to test your alternate way of getting the hash key, vs. the normal way.

I suspect you'll have to do several million loops to see an appreciable difference.

Here is how I create the reverse mapping mentioned by @fontanus:

hash = {a:1, b:2}
hash.merge!(Hash[hash.values.zip(hash.keys)])

Which results in:

{
    :a => 1,
    :b => 2,
     1 => :a,
     2 => :b
}

It can also be done by coercing the hash into an array, flattening it and reversing it and then turning it back into a hash, but I find this less intuitive than the above. YMMV.

hash.merge!(Hash[*hash.to_a.flatten.reverse])

@steenslag reminded me of Hash.invert. I knew there was something but couldn't remember the method name:

>> hash.merge!(hash.invert)
{
    :a => 1,
    :b => 2,
     1 => :a,
     2 => :b
}

Give him an upvote for that!

Upvotes: 2

fotanus
fotanus

Reputation: 20116

Searching in ruby 1.9.3 and 2.0.0 are O(n) operations. 

static VALUE
rb_hash_key(VALUE hash, VALUE value)
{
    VALUE args[2];

    args[0] = value;
    args[1] = Qnil;

    rb_hash_foreach(hash, key_i, (VALUE)args);

    return args[1];
}

Implementation of rb_hash_foreach:

void
rb_hash_foreach(VALUE hash, int (*func)(ANYARGS), VALUE farg)
{
    struct hash_foreach_arg arg; 

    if (!RHASH(hash)->ntbl)
        return;
    RHASH_ITER_LEV(hash)++;
    arg.hash = hash;
    arg.func = (rb_foreach_func *)func;
    arg.arg  = farg;
    rb_ensure(hash_foreach_call, (VALUE)&arg, hash_foreach_ensure, hash);
}

Yet, your hashes are small. @theTinMan is correct about being premature optimization, and you should not worry about it.

Upvotes: 1

Related Questions