रूबी में हथौड़ा दूरी की गणना करने का सबसे प्रभावी तरीका?

Question

रूबी में, दो हस्ताक्षरित पूर्णांक (जैसे हथौड़ा दूरी) के बीच थोड़ा अंतर की गणना करने का सबसे प्रभावी तरीका क्या है?

a = 10001010011111000110101110110101 
b = 01101010010000010000100101101000 

एक & ख 17 है के बीच थोड़ा अंतर ..

मैं:

जैसे, मैं पूर्णांक एक = +२३२३४०९८४५ और b = 1782647144.

उनके बाइनरी अभ्यावेदन हैं उन पर एक तार्किक एक्सओआर कर सकते हैं, लेकिन यह मुझे एक अलग पूर्णांक देगा! = 17, मुझे परिणाम के द्विआधारी प्रतिनिधित्व के माध्यम से फिर से शुरू करना होगा और # 1 के # के बारे में बताएं।

थोड़ा अंतर की गणना करने का सबसे प्रभावी तरीका क्या है?

अब, क्या कई चींटियों के अनुक्रमों के थोड़ा अंतर की गणना के लिए उत्तर परिवर्तन होता है? जैसे

x = {2323409845,641760420,509499086....} 
y = {uint,uint,uint...} 

दो दृश्यों के बीच थोड़ा अंतर की गणना करने के लिए सबसे कारगर तरीका क्या है: अहस्ताक्षरित पूर्णांकों का 2 दृश्यों दिया?

क्या आप अनुक्रम के माध्यम से फिर से शुरू करेंगे, या एक ही समय में पूरे अनुक्रम में अंतर की गणना करने का एक तेज़ तरीका है?

Answer 1

आप रूबी में अनुकूलित स्ट्रिंग कार्यों के उपयोग बिट गिनती करने के लिए, शुद्ध गणित के बजाय कर सकते हैं। यह कुछ त्वरित बेंचमार्किंग के साथ लगभग 6 गुना तेज हो जाता है। जबकि h2 एक स्ट्रिंग में XOR धर्मान्तरित

def h2(a, b) 
    (a^b).to_s(2).count("1") 
end 

h1, गणना करने के लिए सामान्य तरीका है, और की संख्या की गणना "1" रों

बेंचमार्क:

ruby-1.9.2-p180:001:0>> def h1(a, b) 
ruby-1.9.2-p180:002:1*> ret = 0 
ruby-1.9.2-p180:003:1*> xor = a^b 
ruby-1.9.2-p180:004:1*> until xor == 0 
ruby-1.9.2-p180:005:2*> ret += 1 
ruby-1.9.2-p180:006:2*> xor &= xor - 1 
ruby-1.9.2-p180:007:2*> end 
ruby-1.9.2-p180:008:1*> ret 
ruby-1.9.2-p180:009:1*> end 
# => nil 
ruby-1.9.2-p180:010:0>> def h2(a, b) 
ruby-1.9.2-p180:011:1*> (a^b).to_s(2).count("1") 
ruby-1.9.2-p180:012:1*> end 
# => nil 
ruby-1.9.2-p180:013:0>> h1(2323409845, 1782647144) 
# => 17 
ruby-1.9.2-p180:014:0>> h2(2323409845, 1782647144) 
# => 17 
ruby-1.9.2-p180:015:0>> quickbench(10**5) { h1(2323409845, 1782647144) } 
Rehearsal ------------------------------------ 
    2.060000 0.000000 2.060000 ( 1.944690) 
--------------------------- total: 2.060000sec 

     user  system  total  real 
    1.990000 0.000000 1.990000 ( 1.958056) 
# => nil 
ruby-1.9.2-p180:016:0>> quickbench(10**5) { h2(2323409845, 1782647144) } 
Rehearsal ------------------------------------ 
    0.340000 0.000000 0.340000 ( 0.333673) 
--------------------------- total: 0.340000sec 

     user  system  total  real 
    0.320000 0.000000 0.320000 ( 0.326854) 
# => nil 
ruby-1.9.2-p180:017:0>> 

Answer 2

वेग्नर का एक एल्गोरिथ्म:

def hamm_dist(a, b) 
    dist = 0 
    val = a^b 

    while not val.zero? 
    dist += 1 
    val &= val - 1 
    end 
    dist 
end 

p hamm_dist(2323409845, 1782647144) # => 17 

Answer 3

के सुझाव के अनुसार

एमयू बहुत छोटा है, मैंने __builtin_popcount का उपयोग करने के लिए एक सरल सी एक्सटेंशन लिखा है, और बेंचमार्क का उपयोग करके सत्यापित किया है कि यह रूबी के अनुकूलित स्ट्रिंग फ़ंक्शंस की तुलना में कम से कम 3 एक्स तेज है ..

मैंने देखा निम्नलिखित दो ट्यूटोरियल:

• Extending Ruby With C
• Ruby Extension in C in 5 min

मेरे कार्यक्रम में:

require './FastPopcount/fastpopcount.so' 
include FastPopcount 

def hamming(a,b) 
    popcount(a^b) 
end 

फिर dir में

मेरा कार्यक्रम युक्त, मैं एक फ़ोल्डर "PopCount" निम्नलिखित के साथ बनाने के फ़ाइलें।

extconf.rb:

# Loads mkmf which is used to make makefiles for Ruby extensions 
require 'mkmf' 

# Give it a name 
extension_name = 'fastpopcount' 

# The destination 
dir_config(extension_name) 

# Do the work 
create_makefile(extension_name) 

popcount।c:

// Include the Ruby headers and goodies 
#include "ruby.h" 

// Defining a space for information and references about the module to be stored internally 
VALUE FastPopcount = Qnil; 

// Prototype for the initialization method - Ruby calls this, not you 
void Init_fastpopcount(); 

// Prototype for our method 'popcount' - methods are prefixed by 'method_' here 
VALUE method_popcount(int argc, VALUE *argv, VALUE self); 

// The initialization method for this module 
void Init_fastpopcount() { 
    FastPopcount = rb_define_module("FastPopcount"); 
    rb_define_method(FastPopcount, "popcount", method_popcount, 1); 
} 

// Our 'popcount' method.. it uses the builtin popcount 
VALUE method_popcount(int argc, VALUE *argv, VALUE self) { 
    return INT2NUM(__builtin_popcount(NUM2UINT(argv))); 
} 

फिर popcount निर्देशिका समय में:

माणिक extconf.rb

फिर कार्यक्रम चलाने आप इसे आलोचनात्मक दूरी करने के लिए .... सबसे तेज़ तरीका है, और वहाँ रूबी में

Answer 4

यदि कोई व्यक्ति सी-आधारित पथ का पालन करना चाहता है, तो अपने मेकफ़ाइल में कंपाइलर ध्वज -msse4.2 जोड़ने का अच्छा विचार है। यह संकलक को पॉपकाउंट उत्पन्न करने के लिए तालिका का उपयोग करने के बजाय हार्डवेयर आधारित popcnt निर्देश उत्पन्न करने की अनुमति देता है। मेरे सिस्टम पर यह लगभग 2.5x तेज था।