ruby - 2つのハッシュに同じキーのセットがあるかどうかを確認します

Question

h12つのハッシュがありh2、順序を無視して同じキーのセットがあるかどうかを確認する最も効率的な方法は何ですか？私が投稿した回答よりも速く、またはより簡潔に、効率よく作成できますか？

Answer 1

よし、サヴォア・バイブルとポータビリティのすべてのルールを破りましょう。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)

Answer 2

freemasonjsonとsawa のアイデアを組み合わせると、次のようになります。

h1.size == h2.size and (h1.keys - h2.keys).empty?

Answer 3

Answer 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 に同意する必要があります。しかし、そうは言っても、この質問には確かな事実が必要だったと思います。

Answer 5

それはあなたのデータに依存します。

一般的なケースは実際にはありません。たとえば、通常、キーセット全体を一度に取得する方が、各キーが個別に含まれていることを確認するよりも高速です。ただし、データセット内でキーセットが頻繁に異なる場合は、より速く失敗するより遅いソリューションの方が速い可能性があります。例えば：

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

考慮すべきもう1つの要素は、ハッシュのサイズです。それらが大きい場合、呼び出しのようにセットアップコストが高いソリューションは効果があるSet.newかもしれませんが、それらが小さい場合、それは効果がありません。

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

そして、同じ不変のハッシュを何度も何度も比較した場合、結果をキャッシュすることは間違いなく報われるでしょう。

最終的にはベンチマークだけがわかりますが、ベンチマークを作成するには、ユースケースについて詳しく知る必要があります。確かに、合成データ（たとえば、ランダムに生成されたキー）を使用してソリューションをテストすることは代表的なことではありません。

Answer 6

これは私の試みです：

(h1.keys - h2.keys).empty? and (h2.keys - h1.keys).empty?