Schnelle Methode zum Zählen von Nicht-Null-Bits in positiven Ganzzahlen

117

Ich brauche einen schnellen Weg, um die Anzahl der Bits in einer Ganzzahl in Python zu zählen. Meine aktuelle Lösung ist

bin(n).count("1")

aber ich frage mich, ob es einen schnelleren Weg gibt, dies zu tun?

PS: (Ich stelle ein großes 2D-Binärarray als einzelne Liste von Zahlen dar und führe bitweise Operationen durch. Dadurch wird die Zeit von Stunden auf Minuten verkürzt. Jetzt möchte ich diese zusätzlichen Minuten loswerden.

Bearbeiten: 1. Es muss in Python 2.7 oder 2.6 sein

und die Optimierung für kleine Zahlen spielt keine große Rolle, da dies kein klarer Engpass wäre, aber ich habe an einigen Stellen Zahlen mit mehr als 10 000 Bits

Dies ist beispielsweise ein 2000-Bit-Fall:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L
zidarsk8
quelle
Siehe auch
dusan
1
Welche Art von Darstellung verwenden Sie, wenn Ihre "Ganzzahlen" länger als eine Standardpython sind int? Hat das nicht eine eigene Methode, um dies zu berechnen?
Marcin
1
Mögliches Duplikat von Count-Bits einer Ganzzahl in Python
Endolith
3
Um die Frage von der in stackoverflow.com/a/2654211/1959808 zu unterscheiden (wenn es anders sein soll - zumindest sieht es so aus), sollten Sie den Titel in „... die Anzahl der Nicht- Null Bits ... ”oder ähnlich. Ansonsten int.bit_lengthsollte die Antwort sein und nicht die unten akzeptierte.
Ioannis Filippidis

Antworten:

121

Für Ganzzahlen beliebiger Länge bin(n).count("1")ist dies die schnellste, die ich in reinem Python finden konnte.

Ich habe versucht, die Lösungen von Óscar und Adam so anzupassen, dass die Ganzzahl in 64-Bit- bzw. 32-Bit-Blöcken verarbeitet wird. Beide waren mindestens zehnmal langsamer als bin(n).count("1")(die 32-Bit-Version brauchte wieder etwa halb so viel Zeit).

Auf der anderen Seite dauerte gmpy popcount() ungefähr 1/20 der Zeit von bin(n).count("1"). Wenn Sie also gmpy installieren können, verwenden Sie das.

Um eine Frage in den Kommentaren zu beantworten, würde ich für Bytes eine Nachschlagetabelle verwenden. Sie können es zur Laufzeit generieren:

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

Oder definieren Sie es einfach wörtlich:

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')

Dann ist es counts[x], die Anzahl von 1 Bits zu erhalten, xwobei 0 ≤ x ≤ 255 ist.

irgendwie
quelle
7
+1! Die Umkehrung davon ist nicht genau, es sollte jedoch angegeben werden: bin(n).count("0")ist aufgrund des Präfixes '0b' nicht genau. Müsste bin(n)[2:].count('0')für diejenigen sein, die Naughts zählen ...
der Wolf
11
Sie können jedoch nicht wirklich null Bits zählen, ohne zu wissen, wie viele Bytes Sie füllen. Dies ist bei einer langen Python-Ganzzahl problematisch, da es sich um alles handeln kann.
Kindall
2
Obwohl dies schnelle Optionen für einzelne Ganzzahlen sind, beachten Sie, dass Algorithmen, die in anderen Antworten dargestellt werden, möglicherweise vektorisiert werden können und daher viel schneller sind, wenn sie über viele Elemente eines großen numpyArrays ausgeführt werden.
Gerrit
Für numpy Arrays würde ich so etwas untersuchen: gist.github.com/aldro61/f604a3fa79b3dec5436a
bitte alle
1
Ich habe benutzt bin(n).count("1"). Schlägt jedoch nur 60% der Python-Einreichung. @ Leetcode
Northtree
29

Sie können den folgenden Algorithmus anpassen:

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

Dies funktioniert für positive 64-Bit-Zahlen, ist jedoch leicht erweiterbar und die Anzahl der Operationen wächst mit dem Logarithmus des Arguments (dh linear mit der Bitgröße des Arguments).

Um zu verstehen, wie dies funktioniert, stellen Sie sich vor, Sie teilen die gesamte 64-Bit-Zeichenfolge in 64 1-Bit-Buckets. Der Wert jedes Buckets entspricht der Anzahl der im Bucket gesetzten Bits (0, wenn keine Bits gesetzt sind, und 1, wenn ein Bit gesetzt ist). Die erste Transformation führt zu einem analogen Zustand, jedoch mit 32 Buckets von jeweils 2 Bit Länge. Dies wird erreicht, indem die Buckets entsprechend verschoben und ihre Werte addiert werden (eine Addition kümmert sich um alle Buckets, da kein Übertrag zwischen Buckets auftreten kann - die n-Bit-Nummer ist immer lang genug, um die Nummer n zu codieren). Weitere Transformationen führen zu Zuständen mit exponentiell abnehmender Anzahl von Buckets exponentiell wachsender Größe, bis wir zu einem 64 Bit langen Bucket gelangen. Dies gibt die Anzahl der im ursprünglichen Argument gesetzten Bits an.

Adam Zalcman
quelle
Ich habe ernsthaft keine Ahnung, wie dies mit 10 000 Bit-Zahlen funktionieren würde, aber ich mag die Lösung. Kannst du mir einen Hinweis geben, ob und wie ich das auf größere Zahlen übertragen kann?
Zidarsk8
Ich habe die Anzahl der Bits, mit denen Sie hier zu tun haben, nicht gesehen. Haben Sie darüber nachgedacht, Ihren Datenverarbeitungscode in einer einfachen Sprache wie C zu schreiben? Vielleicht als Erweiterung Ihres Python-Codes? Sie können die Leistung sicherlich verbessern, indem Sie große Arrays in C im Vergleich zu großen Zahlen in Python verwenden. Das heißt, Sie können die CountBits()10k-Bit-Zahlen neu schreiben , indem Sie nur 8 Codezeilen hinzufügen. Aber es wird aufgrund großer Konstanten unhandlich.
Adam Zalcman
2
Sie können Code schreiben, um die Folge von Konstanten zu generieren, und eine Schleife für die Verarbeitung einrichten.
Karl Knechtel
Diese Antwort hat den großen Vorteil, dass sie für Fälle mit großen Arrays vektorisiert werden kann numpy.
Gerrit
17

Hier ist eine Python-Implementierung des Populationszählalgorithmus, wie in diesem Beitrag erläutert :

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

Es wird funktionieren für 0 <= i < 0x100000000.

Óscar López
quelle
Das ist schlau. Es ist völlig angemessen, dies nachzuschlagen, anstatt eine Antwort aus der Hüfte zu schießen!
MrGomez
1
Haben Sie dies bewertet? Auf meinem Computer mit Python 2.7 war dies tatsächlich etwas langsamer als bin(n).count("1").
David Weldon
@ DavidWeldon Nein, habe ich nicht. Könnten Sie bitte Ihre Benchmarks veröffentlichen?
Ó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
Allerdings numberOfSetBitsverarbeitet meine 864 × 64 numpy.ndarrayin 841 & mgr; s. Mit muss bitCountStrich explizit schleifen, und es dauert 40,7 ms oder fast 50 mal länger.
Gerrit
8

Laut diesem Beitrag scheint dies eine der schnellsten Implementierungen des Hamming-Gewichts zu sein (wenn es Ihnen nichts ausmacht, etwa 64 KB Speicher zu verwenden).

#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])

Auf Python 2.x Sie ersetzen sollten rangemit xrange.

Bearbeiten

Wenn Sie eine bessere Leistung benötigen (und Ihre Zahlen große Zahlen sind), schauen Sie sich die GMPBibliothek an. Es enthält handgeschriebene Assembly-Implementierungen für viele verschiedene Architekturen.

gmpy ist ein C-codiertes Python-Erweiterungsmodul, das die GMP-Bibliothek umschließt.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
Paolo Moretti
quelle
Ich habe meine Frage bearbeitet, um zu verdeutlichen, dass ich diese für große Zahlen (10.000 Bits und mehr) benötige. Eine Optimierung für 32-Bit-Ganzzahlen würde wahrscheinlich keinen großen Unterschied machen, da die Anzahl der Zählungen wirklich groß sein müsste. In diesem Fall würde dies die langsame Ausführungszeit verursachen.
Zidarsk8
GMP ist jedoch genau für sehr große Zahlen geeignet, einschließlich Zahlen, die weit über die von Ihnen genannten Größen hinausgehen.
James Youngman
1
Die Speichernutzung ist besser, wenn Sie array.arrayfür verwenden POPCOUNT_TABLE16, da sie dann als Array von Ganzzahlen und nicht als dynamisch dimensionierte Liste von Python- intObjekten gespeichert wird .
Gsnedders
6

Ich mag diese Methode wirklich. Es ist einfach und ziemlich schnell, aber auch nicht in der Bitlänge begrenzt, da Python unendlich viele ganze Zahlen hat.

Es ist tatsächlich schlauer als es aussieht, weil es keine Zeit damit verschwendet, die Nullen zu scannen. Beispielsweise dauert das Zählen der gesetzten Bits in 1000000000000000000000010100000001 genauso lange wie in 1111.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n
Robotbugs
quelle
sieht gut aus, ist aber nur für sehr "spärliche" ganze Zahlen geeignet. im Durchschnitt ist es ziemlich langsam. Trotzdem sieht es in bestimmten Anwendungsfällen sehr nützlich aus.
Zidarsk8
Ich bin mir nicht ganz sicher, was du mit "im Durchschnitt ist es ziemlich langsam" meinst. Ganz langsam im Vergleich zu was? Meinen Sie langsam im Vergleich zu einem anderen Python-Code, den Sie nicht zitieren? Es ist doppelt so schnell wie Stück für Stück für die durchschnittliche Anzahl zu zählen. Tatsächlich zählt es auf meinem MacBook 12,6 Millionen Bits pro Sekunde, was viel schneller ist, als ich sie zählen kann. Wenn Sie einen anderen generischen Python-Algorithmus haben, der für eine beliebige Länge von Ganzzahlen funktioniert und schneller ist, würde ich gerne davon hören.
Robotbugs
1
Ich akzeptiere, dass es tatsächlich langsamer ist als die Antwort von Manuel oben.
Robotbugs
Im Durchschnitt bedeutet das Zählen von Bits für 10000 Zahlen mit 10000 Ziffern 0,15 bin(n).count("1")Sekunden, für Ihre Funktion jedoch 3,8 Sekunden. Wenn für die Zahlen nur sehr wenige Bits gesetzt wären, würde dies schnell funktionieren. Wenn Sie jedoch eine Zufallszahl verwenden, ist die obige Funktion im Durchschnitt um Größenordnungen langsamer.
Zidarsk8
OK, das werde ich akzeptieren. Ich glaube, ich war nur ein Schwanz, weil du ein bisschen ungenau bist, aber du hast vollkommen recht. Ich hatte die Methode vor meinem Kommentar einfach nicht mit der oben beschriebenen Methode von Manuel getestet. Es sieht sehr klobig aus, ist aber tatsächlich sehr schnell. Ich verwende jetzt eine solche Version, aber mit 16 Werten im Wörterbuch, und das ist sogar viel schneller als die, die er zitiert hat. Aber für die Aufzeichnung habe ich meine in einer Anwendung mit nur wenigen Bits verwendet, die auf 1 gesetzt wurden. Aber für völlig zufällige Bits geht es ungefähr 50:50, wobei eine kleine Varianz mit der Länge abnimmt.
Robotbugs
3

Sie können den Algorithmus verwenden, um die Binärzeichenfolge [1] einer Ganzzahl abzurufen, aber anstatt die Zeichenfolge zu verketten, zählen Sie die Anzahl der Einsen:

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
quelle
Das geht schnell. Zumindest auf p3 ist ein Fehler aufgetreten. [1:] sollte [2:] sein, da oct () vor dem String '0o' zurückgibt. Der Code läuft jedoch viel schneller, wenn Sie hex () anstelle von oct () verwenden und ein Wörterbuch mit 16
Einträgen erstellen.
2

Sie sagten, Numpy sei zu langsam. Haben Sie es verwendet, um einzelne Bits zu speichern? Warum nicht die Idee erweitern, Ints als Bit-Arrays zu verwenden, sondern diese mit Numpy speichern?

Speichern Sie n Bits als Array von ceil(n/32.)32-Bit-Ints. Sie können dann mit dem numpy-Array auf die gleiche (gut genug ähnliche) Weise arbeiten, wie Sie Ints verwenden, einschließlich der Verwendung, um ein anderes Array zu indizieren.

Der Algorithmus besteht im Wesentlichen darin, parallel die Anzahl der in jeder Zelle gesetzten Bits zu berechnen und die Bitanzahl jeder Zelle zusammenzufassen.

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

Obwohl ich überrascht bin, hat niemand vorgeschlagen, ein C-Modul zu schreiben.

leewz
quelle
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
quelle
-2

Es stellt sich heraus, dass Ihre Startdarstellung eine Liste von Ints-Listen ist, die entweder 1 oder 0 sind. Zählen Sie sie einfach in dieser Darstellung.


Die Anzahl der Bits in einer Ganzzahl ist in Python konstant.

Wenn Sie jedoch die Anzahl der gesetzten Bits zählen möchten, erstellen Sie am schnellsten eine Liste, die dem folgenden Pseudocode entspricht: [numberofsetbits(n) for n in range(MAXINT)]

Dadurch erhalten Sie eine konstante Zeitsuche, nachdem Sie die Liste erstellt haben. Eine gute Implementierung finden Sie in der Antwort von @ PaoloMoretti. Natürlich müssen Sie dies nicht alles im Speicher behalten - Sie könnten einen dauerhaften Schlüsselwertspeicher oder sogar MySQL verwenden. (Eine andere Möglichkeit wäre, einen eigenen einfachen festplattenbasierten Speicher zu implementieren.)

Marcin
quelle
@StevenRumbalski Wie ist es nicht hilfreich?
Marcin
Als ich Ihre Antwort las, enthielt sie nur Ihren ersten Satz: "Die Anzahl der Bits in einer Ganzzahl ist in Python konstant."
Steven Rumbalski
Ich habe bereits eine Nachschlagetabelle für die Anzahl der Bitzählungen für alle Zählungen, die gespeichert werden können. Wenn Sie jedoch eine große Liste von Zahlen haben und diese mit einem [i] und einem [j] bearbeiten, wird Ihre Lösung unbrauchbar, es sei denn, ich habe 10+ GB RAM. Array für & ^ | für Tripples von 10000 Zahlen wäre 3 * 10000 ^ 3 Nachschlagetabellengröße. da ich nicht weiß, was ich brauche, ist es sinnvoller, nur die paar tausend zu zählen, wenn ich sie brauche
zidarsk8
@ zidarsk8 Oder Sie könnten eine Art Datenbank oder einen dauerhaften Schlüsselwertspeicher verwenden.
Marcin
@ zidarsk8 10 + GB RAM ist nicht schockierend groß. Wenn Sie eine schnelle numerische Berechnung durchführen möchten, ist es nicht unangemessen, mittelgroßes Eisen zu verwenden.
Marcin