रूबी: एक द्विआधारी संख्या

Question

मैं एक द्विआधारी संख्या (52 बिट) है में 1 की की संख्या की गणना एक स्ट्रिंग के रूप में प्रतिनिधित्व "01,100,011 ...."

क्या 1 के की संख्या की गणना करने के लिए तेज तरीका हो सकता है ?

"01100011....".count("1") 

स्पष्ट रूप से काम करता है लेकिन काफी समय लगता है इस आपरेशन हज़ारों बार किया जाना चाहिए है।

ठीक है, कुछ और जानकारी। मैं

def bit_vec(str) 
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' 
    bv = "" 
    alphabet.each_char do |a| 
     if str.include?(a) 
      bv += "1" 
     else 
      bv += "0" 
     end 
    end 
     bv 
end 

बिट_वीसी विधि को लगभग 170 के बार बुलाया जाता है, तो शब्दों के लिए बिट वैक्टर बनाने की कोशिश कर रहा हूं। मैं एक हैश में बिट वैक्टर स्टोर करता हूं और बिट वेक्टरों को XOR'ing द्वारा दिए गए शब्द के लिए समान शब्दों को ढूंढने और 1 की संख्या (अधिक 1 की == कम समानता) की गणना करने के लिए उनका उपयोग करता हूं। यदि गिनती विधि स्ट्रिंग # का उपयोग नहीं करती है तो स्कैन करें कि इसका क्या उपयोग हो सकता है?

मुझे पता है रूबी सी या जावा कहने से धीमी है। मैं बस एल्गोरिदम को बेहतर बनाने के लिए देख रहा हूं। मैं कच्ची गति की तलाश नहीं कर रहा हूं।

शायद इसमें शामिल हैं? विधि बाधा है?

Answer 1

ध्यान दें कि 1-बिट गिनती की समस्या एक "जनसंख्या गिनती" के रूप में जाना जाता है।

कम से कम रूबी में, count विधि के माध्यम से इन्हें स्ट्रिंग के रूप में संभालने के साथ चिपके रहें जब तक कि आपके पास पूर्णांक का उपयोग करने के लिए एक अनिवार्य कारण न हो।

count:

बेंचमार्क: 10000000 पुनरावृत्तियों प्रति सेकंड (127,225.63 पुनरावृत्तियों)

पूर्णांक गणित के लिए,

आप 2**32 ऊपर मूल्यों के बारे में परवाह नहीं करते हैं,

def popcount(x) 
    m1 = 0x55555555 
    m2 = 0x33333333 
    m4 = 0x0f0f0f0f 
    x -= (x >> 1) & m1 
    x = (x & m2) + ((x >> 2) & m2) 
    x = (x + (x >> 4)) & m4 
    x += x >> 8 
    return (x + (x >> 16)) & 0x3f 
end 

के लिए 78.60s

बेंचमार्क: 10,000,000 पुनरावृत्तियों के लिए 105.73 एस (प्रति सेकंड 94,579.03 पुनरावृत्तियों)

आप 2**32 ऊपर मूल्यों के बारे में परवाह है, तो

def popcount(x) 
    b = 0 
    while x > 0 
    x &= x - 1 
    b += 1 
    end 
    return b 
end 

बेंचमार्क: 10000000 पुनरावृत्तियों प्रति सेकंड (27,353.27 पुनरावृत्तियों)

अनुशेष के लिए 365.59s:

आपका कोड:

बेंचमार्क: 1,000,000 पुनरावृत्तियों के लिए 78.25s (प्रति सेकंड 12,77 9.56 पुनरावृत्तियों)

इस कोड:

def bit_vec(str) 
    # alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
    bv = "0" * 52 
    str.each_char do |c| 
    ord = c.ord 
    next unless (ord >= 65 && ord <= 90) || (ord >= 97 && ord <= 122) 
    index = ord - 65 
    index -= 6 if index > 25 
    bv[index] = "1" 
    break if bv == "1111111111111111111111111111111111111111111111111111" 
    end 
    bv 
end 

नोट: आपने कहा कि आप एक 52-बिट संख्या के साथ काम कर रहे थे, तो मैं मान लिया है कि आप दोनों ऊपरी और छोटे अक्षरों (26 + 26 = 52 के बारे में परवाह)। मैंने पहले अपरकेस की जांच करने का विकल्प चुना क्योंकि इस तरह वे गणनाओं को थोड़ा आसान बनाते हुए, हर चरित्र सेट में बहुत अधिक दिखाई देते हैं।

बेंचमार्क: 1000000 पुनरावृत्तियों प्रति सेकंड (40,231.60 पुनरावृत्तियों)

3.14x गति-अप के लिए 24.86s। https://gist.github.com/knugie/3865903

, बस आपकी मशीन पर इसे चलाने अगर तुम संदेह में कर रहे हैं:

Answer 2

आपके पास O(n) प्रदर्शन होगा, इससे कोई फर्क नहीं पड़ता। इस सरल रूबी कमांड का प्रयास करें। अगर यह वास्तव में एक समस्या है तो उपाय करें।

time ruby test.rb के साथ मापा गया यह सरल स्क्रिप्ट 0.058 CPU सेकंड ले गई। यह पुराने 1.25 गीगा प्रोसेसर पर है। क्या आप वाकई सुनिश्चित हैं कि यह ऑपरेशन बहुत धीमा है?

10000.times do 
    "0100010000100001111101101000111110000001101001010".count("1") 
end 

हैं कि तेजी से नहीं है पर्याप्त एक सी विस्तार लिखें। सशर्त उपयोग से बचने की कोशिश करें। इसे इस तरह लिखें:

count = 0; 
for (i = stringLength; i; i++) { 
    count += string[i] - '0';  // no conditional used. 
} 

लेकिन ईमानदारी से, अगर आपको उस तरह की गति रूबी की आवश्यकता है तो यह आपके लिए गलत भाषा है। रूबी में इतनी सारी चीज़ें हैं जो एक साधारण .count("1") से अधिक समय लेती हैं।

Answer 3

http://www.bergek.com/2009/03/11/count-number-of-bits-in-a-ruby-integer/

yourString.scan(/1/).size 

---

से http://snippets.dzone.com/posts/show/4233

count = 0 
count += byte & 1 and byte >>= 1 until byte == 0 

---

यहाँ से 1 के 0 के बनाम के घनत्व के आधार पर गिनती के लिए अलग अलग छोरों के साथ एक पोस्ट (ग) में है

http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Answer 4

8 में स्ट्रिंग को विभाजित करें, 128 प्रविष्टि लुकअप तालिका में प्रत्येक प्रविष्टि को देखें और उन्हें जोड़ दें?

मुझे पता है .. यह हास्यास्पद है ... बस साझा करने में कुछ सुझाव ;-)

Answer 5

यहाँ एक और बेंचमार्क है।

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

नमूना उत्पादन:

 
$ ruby bit_count_benchmark.rb 
CPU  : Intel(R) Core(TM)2 Duo CPU P8400 @ 2.26GHz 
MEM  : 3083288 kB 
RUBY  : ruby-1.9.2-p320 

"NORM": 
    TEST... OK 
    BENCHMARK (2000000): 
    PREPARE... OK 
    RUN... 
          user  system  total  real 
scan_string   227.770000 0.250000 228.020000 (227.912435) 
scan_regex    214.500000 0.220000 214.720000 (214.635405) 
progressive_right_shift 43.420000 0.030000 43.450000 (43.412643) 
continuous_right_shift 39.340000 0.010000 39.350000 (39.345163) 
count_string   19.910000 0.030000 19.940000 (19.932677) 
access_bit_fast   18.310000 0.040000 18.350000 (18.345740) 
bit_elimination_for  16.400000 0.010000 16.410000 (16.388461) 
bit_elimination_until 14.650000 0.000000 14.650000 (14.650187) 
bit_elimination_while 14.610000 0.000000 14.610000 (14.604845) 
pre_compute_16   4.370000 0.000000 4.370000 ( 4.371228) 

"NORM" FINISHED 


"LOTTO": 
    TEST... OK 
    BENCHMARK (2000000): 
    PREPARE... OK 
    RUN... 
          user  system  total  real 
scan_string    92.900000 0.100000 93.000000 (92.947647) 
scan_regex    79.500000 0.230000 79.730000 (79.671581) 
progressive_right_shift 43.430000 0.010000 43.440000 (43.424880) 
continuous_right_shift 35.360000 0.020000 35.380000 (35.360854) 
count_string   19.210000 0.020000 19.230000 (19.215173) 
access_bit_fast   17.890000 0.000000 17.890000 (17.890401) 
bit_elimination_for  5.680000 0.010000 5.690000 ( 5.680348) 
bit_elimination_until 5.040000 0.010000 5.050000 ( 5.054189) 
bit_elimination_while 5.080000 0.020000 5.100000 ( 5.093165) 
pre_compute_16   4.360000 0.010000 4.370000 ( 4.364988) 

"LOTTO" FINISHED 


DONE 

बिट वैक्टर के बजाय