“key”方法在Ruby哈希表中的消耗有多大？

Question

“key”方法在Ruby哈希表中的消耗有多大？

rubyhashkeyreverse-lookup

4

我正在使用几个哈希表，其中一些哈希表的值是其他哈希表的键。

我需要使用key 函数多次来获取一个值的键，以便我可以使用它来访问另一个哈希表中的内容。

我想知道这可能会对性能产生什么影响。在我的情况下，这些哈希表数量较少，内容很小，但我想从理论上知道。

我应该避免过多地使用它吗？与获取键的值相比，它的性能如何？

- MarioDS

2个回答

1

在 Ruby 1.9.3 和 2.0.0 中，搜索操作的时间复杂度为 O(n)。

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];
}

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);
}

然而，你的哈希值很小。@theTinMan关于过早优化的观点是正确的，你不应该担心这个问题。

- fotanus

1

(1) 这不是真的。在 Ruby 1.9 中，也就是 Ruby 2.0 之前，哈希表是有序的。 (2) 哈希表是否有序对“key”有什么影响？我没有看到任何理由。 - sawa

@sawa (1) 谢谢，你是正确的，它不是Ruby 2，而是1.9.2。- 错误的数字2。(2) 在无序列表中，您无法比线性搜索更快地查找元素，但如果您知道列表已排序，可以使用其他搜索算法 - fotanus

2

在什么意义上是“有序的”？在Ruby哈希被称为有序的上下文中，它并不意味着键是“排序”的。它意味着插入键的顺序被保留。 - sawa

我认为这段话很有道理，虽然我们很少看到性能提升，但是OP没有透露他的哈希表大小，所以我相信他正在遇到性能问题。无论如何，问题是“Ruby哈希表的“key”函数有多昂贵？”，我的回答只是在需要时提供一些指导。 - fotanus

1

@fotanus “每次迭代时都是排序的吗？” - 不是的。它不会自动排序。有序意味着每次遍历都以相同的顺序返回元素（在1.9之前不是这种情况），即元素插入的顺序。 - Patrick Oscity

显示剩余8条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- the Tin Man · Accepted Answer

这样想吧：有时你需要做额外的步骤来获取值。每当你使用条件测试并在计算中添加几个步骤时，就会发生这种情况。

显然，这会带来一些开销，但现在担心这个问题是过早进行优化。你可以使用Benchmark类来测试获取哈希键的替代方法与正常方法之间的差异。

我猜你需要循环几百万次才能看到明显的差异。

这是我创建@fontanus提到的反向映射的方法：

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

这导致：

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

它也可以通过将哈希强制转换为数组，将其展平并反转，然后将其转换回哈希来完成，但我发现这比上面的方法不太直观。你的体验可能会有所不同。

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

@steenslag提醒我Hash.invert方法。我知道有这样的方法，但是想不起来方法名：

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

请给他点赞！