6

什么是检查两个哈希是否具有相同的键集而不管顺序h1的最有效方法是什么？h2它可以比我发布的答案更快或更简洁吗？

4

7 回答 7

8

好吧，让我们打破所有关于生活品味和便携性的规则。MRI 的 C API 开始发挥作用。

/* Name this file superhash.c. An appropriate Makefile is attached below. */
#include <ruby/ruby.h>

static int key_is_in_other(VALUE key, VALUE val, VALUE data) {
  struct st_table *other = ((struct st_table**) data)[0];
  if (st_lookup(other, key, 0)) {
    return ST_CONTINUE;
  } else {
    int *failed = ((int**) data)[1];
    *failed = 1;
    return ST_STOP;
  }
}

static VALUE hash_size(VALUE hash) {
  if (!RHASH(hash)->ntbl)
    return INT2FIX(0);
  return INT2FIX(RHASH(hash)->ntbl->num_entries);
}

static VALUE same_keys(VALUE self, VALUE other) {
  if (CLASS_OF(other) != rb_cHash)
    rb_raise(rb_eArgError, "argument needs to be a hash");
  if (hash_size(self) != hash_size(other))
    return Qfalse;
  if (!RHASH(other)->ntbl && !RHASH(other)->ntbl)
    return Qtrue;
  int failed = 0;
  void *data[2] = { RHASH(other)->ntbl, &failed };
  rb_hash_foreach(self, key_is_in_other, (VALUE) data);
  return failed ? Qfalse : Qtrue;
}

void Init_superhash(void) {
  rb_define_method(rb_cHash, "same_keys?", same_keys, 1);
}

这是一个Makefile。

CFLAGS=-std=c99 -O2 -Wall -fPIC $(shell pkg-config ruby-1.9 --cflags)
LDFLAGS=-Wl,-O1,--as-needed $(shell pkg-config ruby-1.9 --libs)
superhash.so: superhash.o
    $(LINK.c) -shared $^ -o $@

一个人工的、合成的和简单的基准显示了以下内容。

require 'superhash'
require 'benchmark'
n = 100_000
h1 = h2 = {a:5, b:8, c:1, d:9}
Benchmark.bm do |b|
  # freemasonjson's state of the art.
  b.report { n.times { h1.size == h2.size and h1.keys.all? { |key| !!h2[key] }}}
  # This solution
  b.report { n.times { h1.same_keys? h2} }
end
#       user     system      total        real
#   0.310000   0.000000   0.310000 (  0.312249)
#   0.050000   0.000000   0.050000 (  0.051807)
于 2012-12-09T12:48:40.353 回答
7

结合freemasonjson和sawa的想法：

h1.size == h2.size and (h1.keys - h2.keys).empty?
于 2012-12-09T11:39:03.233 回答
5

尝试：

# Check that both hash have the same number of entries first before anything
if h1.size == h2.size
    # breaks from iteration and returns 'false' as soon as there is a mismatched key
    # otherwise returns true
    h1.keys.all?{ |key| !!h2[key] }
end

可枚举#all?

更糟糕的情况是，您只会遍历键一次。

于 2012-12-09T11:29:15.497 回答
4

只是为了在这个问题上至少有一个基准......

require 'securerandom'
require 'benchmark'

a = {}
b = {}

# Use uuid to get a unique random key
(0..1_000).each do |i|
  key = SecureRandom.uuid
  a[key] = i
  b[key] = i
end

Benchmark.bmbm do |x|
  x.report("#-") do
    1_000.times do
      (a.keys - b.keys).empty? and (a.keys - b.keys).empty?
    end
  end

  x.report("#&") do
    1_000.times do
      computed = a.keys & b.keys
      computed.size == a.size
    end
  end

  x.report("#all?") do
    1_000.times do
      a.keys.all?{ |key| !!b[key] }
    end
  end

  x.report("#sort") do
    1_000.times do
      a_sorted = a.keys.sort
      b_sorted = b.keys.sort
      a == b
    end
  end
end

结果是：

Rehearsal -----------------------------------------
#-      1.000000   0.000000   1.000000 (  1.001348)
#&      0.560000   0.000000   0.560000 (  0.563523)
#all?   0.240000   0.000000   0.240000 (  0.239058)
#sort   0.850000   0.010000   0.860000 (  0.854839)
-------------------------------- total: 2.660000sec

            user     system      total        real
#-      0.980000   0.000000   0.980000 (  0.976698)
#&      0.560000   0.000000   0.560000 (  0.559592)
#all?   0.250000   0.000000   0.250000 (  0.251128)
#sort   0.860000   0.000000   0.860000 (  0.862857)

我必须同意@akuhn 的观点，如果我们有更多关于您正在使用的数据集的信息，这将是一个更好的基准。但话虽如此，我相信这个问题确实需要一些确凿的事实。

于 2012-12-09T12:26:59.463 回答
3

这取决于您的数据。

真的没有一般情况。例如，通常一次检索整个密钥集比单独检查每个密钥的包含要快。但是，如果在您的数据集中，键集经常不同，那么失败速度较慢的解决方案可能会更快。例如：

h1.size == h2.size and h1.keys.all?{|k|h2.include?(k)}

另一个需要考虑的因素是哈希的大小。如果它们是具有较高设置成本的大型解决方案，例如调用Set.new，可能会得到回报，但如果它们很小，则不会：

h1.size == h2.size and Set.new(h1.keys) == Set.new(h2.keys)

而且，如果您碰巧一次又一次地比较相同的不可变哈希，那么缓存结果肯定会有所回报。

最终，只有基准测试才能说明问题，但是，要编写基准测试，我们需要更多地了解您的用例。当然，使用合成数据（例如，随机生成的密钥）测试解决方案不会具有代表性。

于 2012-12-09T12:03:58.547 回答
1

这是我的尝试：

(h1.keys - h2.keys).empty? and (h2.keys - h1.keys).empty?
于 2012-12-09T10:15:36.233 回答
0

这是我的解决方案：

class Hash
    # doesn't check recursively
    def same_keys?(compare)
        if compare.class == Hash
            if self.size == compare.size
               self.keys.all? {|s| compare.key?(s)}
            else
                return false
            end
        else
            nil
        end
    end
end

a = c = {  a: nil,    b: "whatever1",  c: 1.14,     d: true   }
b     = {  a: "foo",  b: "whatever2",  c: 2.14,   "d": false  }
d     = {  a: "bar",  b: "whatever3",  c: 3.14,               }

puts a.same_keys?(b)                    # => true
puts a.same_keys?(c)                    # => true
puts a.same_keys?(d)                    # => false   
puts a.same_keys?(false).inspect        # => nil
puts a.same_keys?("jack").inspect       # => nil
puts a.same_keys?({}).inspect           # => false
于 2018-07-18T19:23:48.230 回答