J'ai un nombre binaire (52 bits) représenté comme une chaîne "01100011 ..."
Quel serait le moyen le plus rapide de compter le nombre de 1? p>
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
5 Réponses :
Vous allez avoir Ce script simple, mesuré avec si cela n'est pas assez rapide, écrivez une extension C. Essayez d'éviter d'utiliser des conditionnels. Ecrivez-le comme ceci: mais honnêtement, si vous avez besoin de ce type de vitesse, Ruby est la mauvaise langue pour vous. Il y a tellement de choses différentes dans Ruby qui prennent beaucoup plus de temps qu'un simple O (n) performance, quoi qu'il arrive. Essayez cette simple commande de rubis. Mesurer si c'est vraiment un problème. Time Ruby Test.rb a pris 0,058 secondes de CPU. Ceci est sur un ancien processeur de 1,25 GHz. Êtes-vous vraiment sûr que cette opération est trop lente? .Count ("1") .
J'ai couru mon programme avec RProfile et il a montré que 38% du temps est consacré à l'aide de la chaîne # Scan (appels 170K). Je pensais que s'il y avait un moyen intelligent de compter les 1, je pourrais peut-être accélérer un peu de choses.
Je ne pense pas .Count () utilise scannez # scanner interne. Peut-être que votre goulot d'étranglement est ailleurs.
Comment puis-je découvrir quelles méthodes utilisent la chaîne # Scannez en interne?
Utilisez un profileur qui vous indique ou regarde la source. ruby-lang.org/fr/downloads
Pour les non-initiés, la raison de ne pas utiliser de conditionnels est une crise de la succursale de la CPU, qui tendent à perdre du temps de processeur dans ce qu'on appelle une "pipeline stalle": la CPU doit arrêter d'accepter de nouvelles instructions dans un pipeline / une voie de réservation jusqu'au pipeline est clair pour calculer le résultat correct (non prévu). Dans l'ensemble, utilisez un profileur décent pour être sûr que l'optimisation mature fournit une amélioration mesurable.
de HTTP : //www.bergek.com/2009/03/11/count-number-of-bits-in-a-ruby-integer/ de http://snippets.dzone.com/posts/show/4233 P >
count = 0
count += byte & 1 and byte >>= 1 until byte == 0
Scan (/ 1 /). La taille est supérieure à 10 fois plus lente que Nombre ("1") .
Split la chaîne en 8, recherchez chaque entrée dans une table de recherche de 128 entrées et résumez-les?
Je sais .. c'est ridicule ... juste partager des idées; -)
+1 - Cela peut être l'approche la plus rapide, aussi ridicule que cela sonne. Même s'ils ont été regroupés en groupes de 4, il peut être un peu plus lent, mais la table de recherche serait tellement plus petite.
Hachage Les 8 octets vont prendre plus de temps que de compter les occurrences de 1s.
Si vous vous séparez par 8, vous n'avez pas besoin de 256 entrées dans votre table de recherche?
Cela sera plus lent que compter dans ruby, presque garanti.
Notez que le problème de compter 1-bits est appelé «nombre de population».
au moins en rubis, collez-vous avec la manipulation de ceux-ci comme une chaîne via la méthode code> à moins que vous avoir une raison impérieuse d'utiliser des entiers. p>
référence de référence: 78.60 pour 10 000 000 itérations (127.225,63 itérations par seconde) p> Pour les mathématiques entier, p> Si vous ne vous souciez pas des valeurs ci-dessus comptage code>: p> 2 ** 32 CODE>, P> 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
Merci pour la réponse détaillée. Cela a aidé!
Voici un autre point de repère: https://gist.github.com/knugie/3865903
Il suffit de l'exécuter sur votre ordinateur si vous êtes en doute. P>
Ruby ne doit pas être utilisé pour une optimisation maximale, mais la vérification des goulots d'étranglement dans votre code est toujours raisonnable. Un algorithme qui fonctionne bien dans un domaine ne fonctionne pas nécessairement bien dans un autre. Essayez d'utiliser des données réelles à partir de votre application d'optimisation. P>
Sortie d'échantillon: P>
$ 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
Au lieu des vecteurs de bits, je pourrais essayer de stocker les cordes comme une éventail de lettres et faire quelque chose comme ça (["A", "B", "C"] & ["x", "x"] ).Taille