Verificare se due hash hanno lo stesso set di chiavi

Question

Qual è il modo più efficace per verificare se due hash h1 e h2 hanno lo stesso set di chiavi che ignorano l'ordine? Potrebbe essere reso più veloce o più conciso con un'efficienza vicina alla risposta che pubblico?

Answer 1

Prova:

# 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?

peggiore delle ipotesi, si sarebbe iterazione solo attraverso i tasti una volta.

Answer 2

Questo è il mio tentativo:

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

Answer 3

Combinando freemasonjson's e sawa's idee:

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

Answer 4

Dipende sui dati.

Non esiste il caso generale. Ad esempio, in genere il recupero dell'intero set di chiavi in ​​una sola volta è più veloce di controllare l'inclusione di ciascuna chiave separatamente. Tuttavia, se nel set di dati, i keysets differiscono il più delle volte, allora una soluzione più lenta che fallisce più velocemente potrebbe essere più veloce. Ad esempio:

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

Un altro fattore da considerare è la dimensione dei propri hash. Se sono grandi una soluzione con costi di installazione più alto, come chiamare Set.new, potrebbe pagare, se invece sono piccoli, non lo farà:

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

E se vi capita di confrontare più e più volte le stesse immutabili hash ancora una volta, pagherebbe sicuramente per memorizzare i risultati.

Alla fine solo un benchmark dirà, ma, per scrivere un punto di riferimento, avremmo bisogno di saperne di più sul tuo caso d'uso. Sicuramente, testare una soluzione con dati sintetici (come ad esempio le chiavi generate casualmente) non sarà rappresentativa.

Answer 5

Solo per il gusto di avere almeno un punto di riferimento in questa domanda ...

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 

risultati sono:

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) 

Sono d'accordo con @akuhn che questo sarebbe una migliore benchmark se avessimo ulteriori informazioni sul set di dati che state utilizzando. Ma detto questo, credo che questa domanda necessitasse davvero di un fatto difficile.

Answer 6

OK, rompiamo tutte le regole di savoir vivre e portabilità. L'API C della MRI entra in gioco.

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

Ecco un 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 $@ 

Un benchmark artificiale, sintetico e semplicistico mostra quanto segue.

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)