Rubino: contare il numero di 1 di in un numero binario

Question

Ho un numero binario (52 bit), rappresentato come una stringa "01.100.011 ...."

Quale sarebbe il modo più rapido per contare il numero di 1 di ?

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

ovviamente funziona ma richiede molto tempo se questa operazione deve essere eseguita migliaia di volte.

ok, qualche informazione in più. Sto cercando di creare i bit vettori per le parole come segue

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 

Il metodo bit_vec viene chiamato circa 170 volte K. Conservo i vettori bit in un hash e li uso per trovare parole simili per una determinata parola XORando i bit-vettori e contando il numero di 1 (più 1 = = meno similarità). Se il metodo count non usa la scansione # di stringa, cos'altro potrebbe usarlo?

So che Ruby è più lento di dire C o Java. Sto solo cercando di migliorare l'algoritmo il meglio che posso. Non sto cercando la velocità grezza.

Forse l'inclusione? il metodo è il collo di bottiglia?

Answer 1

Si noti che il problema di contare 1-bit viene indicato come un "conteggio della popolazione".

Almeno in Ruby, il bastone con la gestione di questi come una stringa mediante il metodo count meno che non abbiate un motivo valido per usare numeri interi.

count:

Benchmark: 78.60s per 10.000.000 iterazioni (127,225.63 iterazioni al secondo)

Per matematica intero,

Se non si cura di valori di cui sopra, 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 

Riferimento: 105,73s per 10.000.000 di iterazioni (94.579.03 iterazioni al secondo)

Se si preoccupano valori sopra 2**32,

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

Benchmark: 365.59s per 10.000.000 iterazioni (27,353.27 iterazioni al secondo)

Addenda:

tuo codice:

Benchmark: 78.25 per 1.000.000 di iterazioni (12.779.56 iterazioni al secondo)

Questo codice:

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 

Nota: Lei ha detto che si aveva a che fare con un numero di 52 bit, così ho pensato che si cura su entrambe le lettere maiuscole e minuscole (26 + 26 = 52). Ho optato per il controllo delle maiuscole perché è così che appaiono in quasi tutti i set di caratteri di sempre, rendendo i calcoli un po 'più semplici.

riferimento: 24.86s per 1.000.000 iterazioni (40,231.60 iterazioni al secondo)

3.14x accelerazione.

Answer 2

Avrete prestazioni O(n), non importa cosa. Prova questo semplice comando rubino. Misura se è davvero un problema.

Questo semplice script, misurato con time ruby test.rb, ha impiegato 0,058 secondi CPU. Questo è su un vecchio processore 1,25 Ghz. Sei proprio sicuro che questa operazione sia troppo lenta?

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

Se non è abbastanza veloce scrivere un'estensione C. Cerca di evitare l'uso di condizionali. Scrivere in questo modo:

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

Ma onestamente, se avete bisogno di questo tipo di rubino velocità è la lingua sbagliata per voi. Ci sono così tante cose diverse nel rubino che prendono molto più più di un semplice .count("1").

Answer 3

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

yourString.scan(/1/).size 

---

da http://snippets.dzone.com/posts/show/4233

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

---

Ecco un post con diversi loop (in c) per il conteggio in base alla densità di 0 vs 1 di

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

Answer 4

Dividere la stringa in 8, cercare ogni voce in una tabella di ricerca di 128 voci e sommarle?

lo so .. questo è ridicolo ... solo la condivisione di alcune idee ;-)

Answer 5

Ecco un altro punto di riferimento: https://gist.github.com/knugie/3865903

eseguire semplicemente sulla vostra macchina se siete in dubbio.

Ruby non deve essere utilizzato per l'ottimizzazione massima, ma il controllo dei colli di bottiglia nel codice è sempre ragionevole. Un Algoritmo che funziona bene in un dominio non funziona necessariamente bene in un altro. Cerca di utilizzare i dati reali dalla tua applicazione per l'ottimizzazione.

Esempio di output:

 
$ 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