रूबी

Question

में बाइट की समानता की गणना करें यदि बाइट में बाइट में अजीब या समानता है तो गणना करने का सबसे अच्छा तरीका क्या है? मैं एक संस्करण काम कर रहे है:

result = "AB".to_i(16).to_s(2).count('1').odd? 
=> true 

एक स्ट्रिंग के लिए एक नंबर परिवर्तित और गिनती "1" रों समता की गणना हालांकि की एक गरीब तरीका लगता है। कोई बेहतर तरीका?

मैं 3 डीईएस कुंजी की समानता की गणना करने में सक्षम होना चाहता हूं। आखिरकार, मैं बाइट्स को अजीब में परिवर्तित करना चाहता हूं।

धन्यवाद, दान

Answer 1

जब तक आपके पास पर्याप्त तेज़ नहीं है, तो इसे रखें। यह स्पष्ट और संक्षेप में है, और इसका प्रदर्शन आपके विचार से बेहतर है।

हम सरणी देखने के खिलाफ बेंचमार्क सब कुछ, सबसे तेजी से विधि मैं परीक्षण किया जाएगा:

ODD_PARITY = [ 
    false, 
    true, 
    true, 
    ... 
    true, 
    false, 
] 

def odd_parity?(hex_string) 
    ODD_PARITY[hex_string.to_i(16)] 
end 

• सरणी देखने प्रति सेकंड 640,000 बाइट्स की दर से समता गणना करता है।
• बोवेर्सिनेर का सी कोड प्रति सेकंड 640,000 बाइट्स की दर से समानता की गणना करता है।
• आपका कोड प्रति सेकंड 284,000 बाइट्स की दर से समानता की गणना करता है।
• बोवेर्सिनेर का मूल कोड प्रति सेकंड 171,000 बाइट्स की दर से समानता की गणना करता है।
• थियो का छोटा कोड प्रति सेकंड 128,000 बाइट्स की दर से समानता की गणना करता है।

Answer 2

शायद 255 प्रविष्टियों के साथ किसी सरणी के एक लुकअप तालिका में सबसे तेजी से होगा समाधान "रूबी में"।

सी में मैं मुखौटा और शिफ्ट करूंगा। या अगर मेरे पास एसएसई 4 है तो मैं इनलाइन असेंबलर के साथ पीओपीसीएनटी निर्देश का उपयोग करूंगा। यदि आपको उच्च प्रदर्शन होने की आवश्यकता है तो सी में मूल एक्सटेंशन लिखें जो ऊपर से कोई भी करता है।

http://en.wikipedia.org/wiki/SSE4

Answer 3

आप RubyDES library पर एक नज़र उठाया है? यह आपके स्वयं के कार्यान्वयन को लिखने की आवश्यकता को हटा सकता है।

require 'rubygems' 
require 'inline' # RubyInline (install with `gem install RubyInline`) 

class Fixnum 
    # native ruby version: simpler but slow 
    # algorithm from: 
    # http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel  
    def parity_native 
    (((self * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1 
    end 

    class << self 
    # inline c version using RubyInline to create c extension 
    # 4-5 times faster than native version 
    # use as class method: 
    # Fixnum.parity(0xAB) 
    inline :C do |builder| 
     builder.c <<-EOC 
     int parity_c(int num) { 
     return (
      ((num * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF 
     ) & 1; 
     } 
     EOC 
    end 
    end 

    def parity 
    self.class.parity_c(self) 
    end 

    def parity_odd? 
    1 == parity 
    end 
    def parity_even? 
    0 == parity 
    end 
end 

0xAB.parity  # => 1 
0xAB.parity_odd? # => true 
0xAB.parity_even? # => false 
(0xAB + 1).parity # => 0 

सरल मानक के अनुसार, इनलाइन ग संस्करण है 3-4 गुना तेजी से देशी रूबी संस्करण

require 'benchmark' 
n = 10000 
Benchmark.bm do |x| 
    x.report("inline c") do 
    n.times do 
     (0..255).map{|num| num.parity} 
    end 
    end 

    x.report("native ruby") do 
    n.times do 
     (0..255).map{|num| num.parity_native} 
    end 
    end 
end 
# inline c  1.982326s 
# native ruby 7.044330s 

Answer 4

x = 'AB'.to_i(16) 
p = 0 
until x == 0 
    p += x & 1 
    x = x >> 1 
end 
puts p # => 5 

से:

समता गणना करने के लिए, आप कुछ इस तरह का उपयोग कर सकते हैं

जो

x = 'AB'.to_i(16) 
p = x & 1 
p += x & 1 until (x >>= 1) == 0 

012 को छोटा किया जा सकता

यदि आप कुछ ऐसा चाहते हैं जो अपठनीय है ☺

Answer 5

कैसे Memoization के साथ अपने मूल समाधान का उपयोग कर के बारे में? यह केवल प्रत्येक पूर्णांक मान के लिए एक बार गणना करेगा।

class Fixnum 
    # Using a class variable for simplicity, and because subclasses of 
    # Fixnum—while very uncommon—would likely want to share it. 
    @@parity = ::Hash.new{ |h,i| h[i] = i.to_s(2).count('1').odd? } 
    def odd_parity? 
    @@parity[self] 
    end 
    def even_parity? 
    !@@parity[self] 
    end 
end 

"AB".to_i(16).odd_parity? 
#=> true 

Answer 6

मैं 16 प्रविष्टियों (16 वर्ण तालिका के रूप में) की एक तालिका का निर्माण करूंगा, जो बाइट्स के प्रत्येक निबल (आधा) के अनुरूप होता है। प्रविष्टियां, 0,1,1,2,1,2 कर रहे हैं .... 4

अपने बाइट की जांच के लिए

बाईं निबल बाहर मास्क और एक देखने करते हैं, संख्या को याद। करो। 4 तक दाईं ओर एक शिफ्ट करें और दूसरा लुकअप करें, एक योग प्रदान करने के लिए पिछले नंबर पर परिणाम संख्या जोड़ना।

फिर योग से कम ऑर्डर बिट का परीक्षण करें। यदि यह 1 है, तो बाइट अजीब है, अगर यह 0 है, तो बाइट भी है। यदि परिणाम भी है, तो आप xor निर्देश का उपयोग करके उच्च ऑर्डर बिट फ़्लिप करते हैं। यह लुकअप विधि एकल बदलावों द्वारा बाइट में बिट्स जोड़ने से कहीं अधिक तेज है।

मुझे 8 बाइट्स के लिए समानता करने के लिए एक साधारण फ़ंक्शन के लिए ईमेल करें। 3 डीईएस 8 बाइट्स के 3 समूहों का उपयोग करता है।