जांचें कि क्या दो हैश के पास कुंजी का एक ही सेट है

Question

यह जांचने का सबसे प्रभावी तरीका क्या है कि दो हैश h1 और h2 ऑर्डर को अनदेखा करते हुए कुंजी का एक ही सेट है? क्या मैं पोस्ट किए गए उत्तर की तुलना में निकट दक्षता के साथ तेज़ी से या अधिक संक्षिप्त बना सकता हूं?

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

Answer 1

प्रयास करें:

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

बदतर स्थिति, एक बार आप केवल कुंजी के माध्यम से पुनरावृत्ति होगी

Answer 2

यह मेरी कोशिश है।

Answer 3

का मेल freemasonjson's और sawa's विचार:

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

Answer 4

यह अपने डेटा पर निर्भर करता है।

कोई सामान्य मामला वास्तव में नहीं है। उदाहरण के लिए, आम तौर पर पूरी कुंजीसेट को एक बार में पुनर्प्राप्त करना प्रत्येक कुंजी को अलग-अलग शामिल करने की तुलना में तेज़ होता है। हालांकि, यदि आपके डेटासेट में, चाबियाँ अधिक से अधिक भिन्न नहीं होती हैं, तो एक धीमी समाधान जो तेजी से विफल हो जाता है तेज़ी से हो सकता है। उदाहरण के लिए:

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) 

आप पर एक ही अपरिवर्तनीय हैश तुलना करने के लिए होगा अगर फिर, यह निश्चित रूप से परिणामों को कैश करने के लिए भुगतान करेगा।

आखिरकार केवल एक बेंचमार्क बताएगा, लेकिन, एक बेंचमार्क लिखने के लिए, हमें आपके उपयोग के मामले के बारे में और जानना होगा। निश्चित रूप से, सिंथेटिक डेटा के साथ समाधान का परीक्षण (उदाहरण के लिए, यादृच्छिक रूप से जेनरेट की गई कुंजी) प्रतिनिधि नहीं होंगे।

बस इस प्रश्न पर कम से कम एक बेंचमार्क होने की खातिर

Answer 5

...

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 6

ठीक है, चलिए savoir vivre और पोर्टेबिलिटी के सभी नियमों को तोड़ दें। एमआरआई का सी एपीआई खेल में आता है।

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

यहां एक मेकफ़ाइल है।

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)