Sprawdź, czy dwa skróty mają ten sam zestaw kluczy.

Question

Jaki jest najbardziej skuteczny sposób sprawdzenia, czy dwa hashe h1 i h2 mają ten sam zestaw kluczy, nie biorąc pod uwagę zamówienia? Czy można to uczynić szybszym lub bardziej zwięzłym z większą skutecznością niż odpowiedź, którą publikuję?

Answer 1

Spróbuj:

# 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 

Enumerable#all?

gorszy scenariusz, byłbyś iteracji tylko poprzez klawisze raz.

Answer 2

To moja próba:

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

Answer 3

Łączenie freemasonjson's i sawa's pomysłów:

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

Answer 4

To zależy od Twoich danych.

Nie ma tak naprawdę ogólnego przypadku . Na przykład generalne pobieranie całego zestawu kluczy naraz jest szybsze niż sprawdzanie osobnego włączenia każdego klucza. Jeśli jednak w zestawie danych zestawy kluczy różnią się często, wówczas wolniejsze rozwiązanie, które nie działa szybciej, może być szybsze. Na przykład:

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

Kolejnym czynnikiem, który należy wziąć pod uwagę, jest wielkość haszy. Jeśli są duże rozwiązanie z wyższym kosztem instalacji, jak dzwoni Set.new może się opłacać, jeśli jednak są one małe, że nie będzie:

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

A jeśli zdarzy się porównać te same niezmienne mieszań w kółko ponownie, zdecydowanie zapłaci za buforowanie wyników.

Ostatecznie tylko benchmark powie, ale, aby napisać benchmark, musielibyśmy wiedzieć więcej o twoim przypadku użycia. Na pewno testowanie rozwiązania za pomocą danych syntetycznych (jak na przykład klucze generowane losowo) nie będzie reprezentatywne.

Answer 5

dla samego posiadania przynajmniej odniesienia na to pytanie ...

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 

Wyniki są następujące:

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) 

muszę zgodzić się z @akuhn że byłoby to lepsze wzorzec porównawczy, gdybyśmy mieli więcej informacji na temat używanego zestawu danych. Ale biorąc to pod uwagę, uważam, że to pytanie naprawdę wymagało ciężkiego faktu.

Answer 6

Dobrze, łammy wszystkie zasady savoir vivre i przenośność. Interfejs API MRI wchodzi w grę.

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

Oto plik 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 $@ 

Sztuczny, syntetyczny i uproszczony benchmark pokazuje, co następuje.

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)