Moyen rapide de compter les bits non nuls en entier positif

117

J'ai besoin d'un moyen rapide de compter le nombre de bits dans un entier en python. Ma solution actuelle est

bin(n).count("1")

mais je me demande s'il existe un moyen plus rapide de faire cela?

PS: (je représente un grand tableau binaire 2D comme une liste unique de nombres et j'effectue des opérations au niveau du bit, ce qui réduit le temps d'heures en minutes. Et maintenant, je voudrais me débarrasser de ces minutes supplémentaires.

Edit: 1. il doit être en python 2.7 ou 2.6

et l'optimisation pour les petits nombres n'a pas beaucoup d'importance car ce ne serait pas un goulot d'étranglement clair, mais j'ai des nombres avec plus de 10000 bits à certains endroits

par exemple c'est un cas de 2000 bits:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
zidarsk8
la source
1
Quel genre de représentation utilisez-vous si vos "entiers" sont plus longs qu'un python standard int? Cela n'a-t-il pas sa propre méthode de calcul?
Marcin
1
duplication possible de Count bits d'un entier en Python
endolith
3
Pour distinguer la question de celle de stackoverflow.com/a/2654211/1959808 (si elle est censée être différente - du moins en a-t-elle l'air), veuillez reformuler le titre en «... en comptant le nombre de non- zéro bit ... »ou similaire. Sinon, int.bit_lengthdevrait être la réponse, et non celle acceptée ci-dessous.
Ioannis Filippidis

Réponses:

121

Pour les entiers de longueur arbitraire, bin(n).count("1")c'est le plus rapide que j'ai pu trouver en Python pur.

J'ai essayé d'adapter les solutions d'Óscar et d'Adam pour traiter l'entier en blocs 64 bits et 32 ​​bits, respectivement. Les deux étaient au moins dix fois plus lents que bin(n).count("1")(la version 32 bits a encore pris environ la moitié du temps).

D'un autre côté, gmpy a popcount() pris environ 1 / 20e du temps de bin(n).count("1"). Donc, si vous pouvez installer gmpy, utilisez-le.

Pour répondre à une question dans les commentaires, pour les octets, j'utiliserais une table de recherche. Vous pouvez le générer au moment de l'exécution:

counts = bytes(bin(x).count("1") for x in range(256))  # py2: use bytearray

Ou définissez-le littéralement:

counts = (b'\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07'
          b'\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08')

Ensuite, il counts[x]faut obtenir le nombre de 1 bits xoù 0 ≤ x ≤ 255.

kindall
la source
7
+1! L'inverse de ceci n'est pas exact, cependant, il faut le dire: bin(n).count("0")n'est pas exact à cause du préfixe «0b». Aurait besoin d'être bin(n)[2:].count('0')pour ceux qui comptent les vilaines ....
le loup
11
Cependant, vous ne pouvez pas vraiment compter zéro bit sans savoir combien d'octets vous remplissez, ce qui est problématique avec un entier long Python car cela pourrait être n'importe quoi.
kindall
2
Bien que ce soient des options rapides pour des entiers simples, notez que les algorithmes présentés dans d'autres réponses peuvent être potentiellement vectorisés, donc beaucoup plus rapides s'ils sont exécutés sur de nombreux éléments d'un grand numpytableau.
gerrit
Pour les tableaux numpy, j'examinerais quelque chose comme ceci: gist.github.com/aldro61/f604a3fa79b3dec5436a
kindall
1
J'ai utilisé bin(n).count("1"). Cependant, ne bat que 60% de la soumission python. @ leetcode
northtree
29

Vous pouvez adapter l'algorithme suivant:

def CountBits(n):
  n = (n & 0x5555555555555555) + ((n & 0xAAAAAAAAAAAAAAAA) >> 1)
  n = (n & 0x3333333333333333) + ((n & 0xCCCCCCCCCCCCCCCC) >> 2)
  n = (n & 0x0F0F0F0F0F0F0F0F) + ((n & 0xF0F0F0F0F0F0F0F0) >> 4)
  n = (n & 0x00FF00FF00FF00FF) + ((n & 0xFF00FF00FF00FF00) >> 8)
  n = (n & 0x0000FFFF0000FFFF) + ((n & 0xFFFF0000FFFF0000) >> 16)
  n = (n & 0x00000000FFFFFFFF) + ((n & 0xFFFFFFFF00000000) >> 32) # This last & isn't strictly necessary.
  return n

Cela fonctionne pour les nombres positifs de 64 bits, mais il est facilement extensible et le nombre d'opérations augmente avec le logarithme de l'argument (c'est-à-dire linéairement avec la taille en bits de l'argument).

Afin de comprendre comment cela fonctionne, imaginez que vous divisez la chaîne 64 bits entière en 64 compartiments 1 bit. La valeur de chaque compartiment est égale au nombre de bits définis dans le compartiment (0 si aucun bit n'est défini et 1 si un bit est défini). La première transformation aboutit à un état analogue, mais avec 32 compartiments de 2 bits chacun. Ceci est réalisé en décalant de manière appropriée les compartiments et en ajoutant leurs valeurs (une addition prend en charge tous les compartiments car aucun report ne peut se produire entre les compartiments - un nombre de n bits est toujours assez long pour coder le nombre n). D'autres transformations conduisent à des états avec un nombre exponentiellement décroissant de seaux de taille exponentiellement croissante jusqu'à ce que nous arrivions à un seau de 64 bits de long. Cela donne le nombre de bits définis dans l'argument d'origine.

Adam Zalcman
la source
Je ne sais sérieusement pas comment cela fonctionnerait avec des nombres de 10 000 bits, mais j'aime la solution. pouvez-vous me donner un indice si et comment je peux l'appliquer à de plus grands nombres?
zidarsk8
Je n'ai pas vu le nombre de bits dont vous avez affaire ici. Avez-vous envisagé d'écrire votre code de traitement des données dans un langage de bas niveau comme C? Peut-être comme une extension de votre code python? Vous pouvez certainement améliorer les performances en utilisant de grands tableaux en C par rapport aux grands chiffres en python. Cela dit, vous pouvez réécrire le CountBits()pour gérer les nombres de 10 000 bits en ajoutant seulement 8 lignes de code. Mais cela deviendra difficile à manier en raison d'énormes constantes.
Adam Zalcman
2
Vous pouvez écrire du code pour générer la séquence de constantes et configurer une boucle pour le traitement.
Karl Knechtel
Cette réponse a le grand avantage de pouvoir être vectorisée pour les cas traitant de grands numpytableaux.
gerrit
17

Voici une implémentation Python de l'algorithme de comptage de population, comme expliqué dans cet article :

def numberOfSetBits(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

Cela fonctionnera pour 0 <= i < 0x100000000.

Óscar López
la source
C'est malin. Rechercher cela au lieu de tirer une réponse de la hanche est tout à fait approprié!
MrGomez
1
Avez-vous évalué cela? Sur ma machine utilisant python 2.7, j'ai trouvé que c'était en fait un peu plus lent que bin(n).count("1").
David Weldon
@DavidWeldon Non je ne l'ai pas fait, pourriez-vous s'il vous plaît poster vos benchmarks?
Óscar López
%timeit numberOfSetBits(23544235423): 1000000 loops, best of 3: 818 ns per loop; %timeit bitCountStr(23544235423): 1000000 loops, best of 3: 577 ns per loop.
gerrit
7
Cependant, numberOfSetBitstraite mes 864 × 64 numpy.ndarrayen 841 µs. Avec bitCountStrje dois boucler explicitement, et cela prend 40,7 ms, soit presque 50 fois plus longtemps.
gerrit
8

Selon cet article , cela semble être l'une des implémentations les plus rapides du poids de Hamming (si cela ne vous dérange pas d'utiliser environ 64 Ko de mémoire).

#http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable
POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

Sur Python 2.x, vous devez remplacer rangepar xrange.

Éditer

Si vous avez besoin de meilleures performances (et que vos nombres sont de gros entiers), jetez un œil à la GMPbibliothèque. Il contient des implémentations d'assemblage manuscrites pour de nombreuses architectures différentes.

gmpy est un module d'extension Python codé C qui encapsule la bibliothèque GMP.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
Paolo Moretti
la source
J'ai édité ma question pour préciser que j'en ai besoin pour les grands nombres (10k bits et plus). l'optimisation de quelque chose pour des entiers 32 bits ne ferait probablement pas une grande différence puisque le nombre de comptages devrait être vraiment grand, auquel cas cela entraînerait un temps d'exécution lent.
zidarsk8
Mais GMP est exactement pour les très grands nombres, y compris les nombres égaux et bien au-delà des tailles que vous mentionnez.
James Youngman
1
L'utilisation de la mémoire sera meilleure si vous utilisez array.arrayfor POPCOUNT_TABLE16, car elle sera stockée sous la forme d'un tableau d'entiers, au lieu d'une liste d' intobjets Python de taille dynamique .
gsnedders
6

J'aime vraiment cette méthode. C'est simple et assez rapide mais pas non plus limité dans la longueur en bits puisque python a des entiers infinis.

C'est en fait plus rusé qu'il n'y paraît, car cela évite de perdre du temps à scanner les zéros. Par exemple, il faudra le même temps pour compter les bits définis dans 1000000000000000000000010100000001 que dans 1111.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
Robotbugs
la source
semble super, mais ce n'est bon que pour les entiers très "épars". en moyenne, c'est assez lent. Pourtant, cela semble vraiment utile dans certains cas d'utilisation.
zidarsk8
Je ne sais pas trop ce que vous entendez par «en moyenne, c'est assez lent». Assez lent par rapport à quoi? Voulez-vous dire lent par rapport à un autre code python que vous ne citez pas? C'est deux fois plus rapide que de compter petit à petit le nombre moyen. En fait, sur mon macbook, il compte 12,6 millions de bits par seconde, ce qui est beaucoup plus rapide que je ne peux les compter. Si vous avez un autre algorithme python générique qui fonctionne pour n'importe quelle longueur d'entier et est plus rapide que cela, j'aimerais en entendre parler.
Robotbugs
1
J'admets qu'il est en fait plus lent que la réponse de Manuel ci-dessus.
Robotbugs
Assez lent en moyenne, le comptage des bits pour 10000 nombres avec 10000 chiffres prend 0,15 s avec bin(n).count("1")mais cela prend 3,8 s pour votre fonction. Si les nombres avaient très peu de bits, cela fonctionnerait rapidement, mais si vous prenez un nombre aléatoire, la fonction ci-dessus sera en moyenne plus lente.
zidarsk8
OK, je vais accepter cela. Je suppose que j'étais juste un con parce que tu es un peu imprécis mais tu as tout à fait raison. Je n'avais tout simplement pas testé la méthode en utilisant la méthode de Manuel ci-dessus avant mon commentaire. Cela a l'air très maladroit mais c'est en fait très rapide. J'utilise maintenant une version comme celle-là mais avec 16 valeurs dans le dictionnaire et c'est encore beaucoup plus rapide que celle qu'il a citée. Mais pour mémoire, j'utilisais le mien dans une application avec seulement quelques bits mis à 1. Mais pour les bits totalement aléatoires, oui, ça va à environ 50:50 avec une petite variance décroissant avec la longueur.
Robotbugs
3

Vous pouvez utiliser l'algorithme pour obtenir la chaîne binaire [1] d'un entier mais au lieu de concaténer la chaîne, en comptant le nombre d'unités:

def count_ones(a):
    s = 0
    t = {'0':0, '1':1, '2':1, '3':2, '4':1, '5':2, '6':2, '7':3}
    for c in oct(a)[1:]:
        s += t[c]
    return s

[1] https://wiki.python.org/moin/BitManipulation

Manuel
la source
Cela fonctionne vite. Il y a une erreur, au moins sur p3, le [1:] devrait être [2:] car oct () renvoie «0o» avant la chaîne. Le code s'exécute beaucoup plus rapidement si vous utilisez hex () au lieu d'oct () et créez un dictionnaire de 16 entrées,
Robotbugs
2

Vous avez dit que Numpy était trop lent. L'utilisiez-vous pour stocker des bits individuels? Pourquoi ne pas étendre l'idée d'utiliser des ints comme tableaux de bits, mais utiliser Numpy pour les stocker?

Stocke n bits sous la forme d'un tableau de ceil(n/32.) 32 bits. Vous pouvez ensuite travailler avec le tableau numpy de la même manière (enfin assez similaire) que vous utilisez ints, y compris en les utilisant pour indexer un autre tableau.

L'algorithme consiste essentiellement à calculer, en parallèle, le nombre de bits définis dans chaque cellule et à additionner le nombre de bits de chaque cellule.

setup = """
import numpy as np
#Using Paolo Moretti's answer http://stackoverflow.com/a/9829855/2963903
POPCOUNT_TABLE16 = np.zeros(2**16, dtype=int) #has to be an array

for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff])

def count1s(v):
    return popcount32_table16(v).sum()

v1 = np.arange(1000)*1234567                       #numpy array
v2 = sum(int(x)<<(32*i) for i, x in enumerate(v1)) #single int
"""
from timeit import timeit

timeit("count1s(v1)", setup=setup)        #49.55184188873349
timeit("bin(v2).count('1')", setup=setup) #225.1857464598633

Bien que je sois surpris, personne ne vous a suggéré d'écrire un module C.

leewz
la source
0
#Python prg to count set bits
#Function to count set bits
def bin(n):
    count=0
    while(n>=1):
        if(n%2==0):
            n=n//2
        else:
            count+=1
            n=n//2
    print("Count of set bits:",count)
#Fetch the input from user
num=int(input("Enter number: "))
#Output
bin(num)
Praveen Narala
la source
-2

Il s'avère que votre représentation de départ est une liste de listes d'entiers qui valent 1 ou 0. Il suffit de les compter dans cette représentation.


Le nombre de bits dans un entier est constant en python.

Cependant, si vous souhaitez compter le nombre de bits définis, le moyen le plus rapide est de créer une liste conforme au pseudocode suivant: [numberofsetbits(n) for n in range(MAXINT)]

Cela vous fournira une recherche en temps constant après avoir généré la liste. Voir la réponse de @ PaoloMoretti pour une bonne implémentation de ceci. Bien sûr, vous n'êtes pas obligé de garder tout cela en mémoire - vous pouvez utiliser une sorte de magasin clé-valeur persistant, ou même MySql. (Une autre option serait d'implémenter votre propre stockage sur disque simple).

Marcin
la source
@StevenRumbalski En quoi est-ce inutile?
Marcin
Quand j'ai lu votre réponse, elle ne contenait que votre première phrase: "Le nombre de bits dans un entier est constant en python."
Steven Rumbalski
J'ai déjà une table de recherche pour tous les nombres qu'il est possible de stocker, mais avoir une grande liste de nombres et les utiliser avec un [i] et un [j] rend votre solution inutile à moins que j'en ai 10+ Go de RAM. tableau pour & ^ | pour les tripples de 10000 nombres, la taille de la table de recherche serait de 3 * 10000 ^ 3. puisque je ne sais pas ce dont j'aurai besoin, il est plus logique de compter les quelques milliers quand
j'en
@ zidarsk8 Ou, vous pouvez utiliser une sorte de base de données ou de stockage de clé-valeur persistant.
Marcin
@ zidarsk8 10 + Go de RAM n'est pas terriblement grand. Si vous souhaitez effectuer un calcul numérique rapide, il n'est pas déraisonnable d'utiliser un fer de taille moyenne à grande.
Marcin