Szybki sposób zliczania niezerowych bitów w dodatniej liczbie całkowitej

Potrzebuję szybkiego sposobu, aby policzyć liczbę bitów w liczbie całkowitej w Pythonie. Moje obecne rozwiązanie to

bin(n).count("1")

ale zastanawiam się, czy można to zrobić szybciej?

PS: (Reprezentuję dużą tablicę binarną 2D jako pojedynczą listę liczb i wykonuję operacje bitowe, a to skraca czas z godzin do minut. Teraz chciałbym pozbyć się tych dodatkowych minut.

Edycja: 1. musi być w Pythonie 2.7 lub 2.6

a optymalizacja pod kątem małych liczb nie ma większego znaczenia, ponieważ nie byłoby to wyraźnym wąskim gardłem, ale mam liczby z 10 000 + bitami w niektórych miejscach

na przykład jest to przypadek 2000-bitowy:

12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L

W przypadku liczb całkowitych o dowolnej długości bin(n).count("1")jest najszybszym, jaki udało mi się znaleźć w czystym Pythonie.

Próbowałem dostosować rozwiązania Óscara i Adama do przetwarzania liczb całkowitych odpowiednio w 64-bitowych i 32-bitowych fragmentach. Oba były co najmniej dziesięciokrotnie wolniejsze niż bin(n).count("1")(wersja 32-bitowa zajęła o połowę mniej czasu).

Z drugiej strony gmpy popcount() zajęło około 1/20 czasu bin(n).count("1"). Więc jeśli możesz zainstalować gmpy, użyj tego.

Aby odpowiedzieć na pytanie w komentarzach, dla bajtów użyłbym tabeli przeglądowej. Możesz go wygenerować w czasie wykonywania:

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

Lub po prostu zdefiniuj to dosłownie:

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

Następnie counts[x]uzyskuje się liczbę 1 bitów, xgdzie 0 ≤ x ≤ 255.

Możesz dostosować następujący algorytm:

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

Działa to dla 64-bitowych liczb dodatnich, ale jest łatwo rozszerzalne, a liczba operacji rośnie wraz z logarytmem argumentu (tj. Liniowo z rozmiarem bitu argumentu).

Aby zrozumieć, jak to działa, wyobraź sobie, że dzielisz cały 64-bitowy ciąg na 64 1-bitowe segmenty. Wartość każdego zasobnika jest równa liczbie bitów ustawionych w zasobniku (0, jeśli nie ustawiono żadnych bitów i 1, jeśli ustawiono jeden). Pierwsza transformacja skutkuje analogicznym stanem, ale z 32 zasobnikami, każdy o długości 2 bitów. Osiąga się to poprzez odpowiednie przesuwanie koszy i dodawanie ich wartości (jeden dodatek zajmuje się wszystkimi zasobnikami, ponieważ nie może wystąpić żadne przeniesienie między zasobnikami - liczba n-bitowa jest zawsze wystarczająco długa, aby zakodować liczbę n). Dalsze przekształcenia prowadzą do stanów z wykładniczo malejącą liczbą zasobników o wykładniczo rosnącym rozmiarze, aż do momentu, gdy dojdziemy do jednego zasobnika o długości 64 bitów. Daje to liczbę bitów ustawioną w oryginalnym argumencie.

Oto implementacja algorytmu liczenia populacji w języku Python, jak wyjaśniono w tym poście :

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

To zadziała 0 <= i < 0x100000000.

Zgodnie z tym postem wydaje się, że jest to jedna z najszybszych implementacji wagi Hamminga (jeśli nie masz nic przeciwko użyciu około 64 KB pamięci).

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

Na Pythonie 2.x należy wymienić rangez xrange.

Edytować

Jeśli potrzebujesz lepszej wydajności (a twoje liczby są dużymi liczbami całkowitymi), zajrzyj do GMPbiblioteki. Zawiera odręczne implementacje asemblerów dla wielu różnych architektur.

gmpy to kodowany w C moduł rozszerzający Pythona, który otacza bibliotekę GMP.

>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024

Bardzo podoba mi się ta metoda. Jest prosty i dość szybki, ale nie jest również ograniczony pod względem długości bitowej, ponieważ Python ma nieskończone liczby całkowite.

W rzeczywistości jest bardziej przebiegły, niż się wydaje, ponieważ pozwala uniknąć marnowania czasu na skanowanie zer. Na przykład policzenie ustawionych bitów w 1000000000000000000000010100000001 jak w 1111 zajmie tyle samo czasu.

def get_bit_count(value):
   n = 0
   while value:
      n += 1
      value &= value-1
   return n

Możesz użyć algorytmu, aby uzyskać ciąg binarny [1] liczby całkowitej, ale zamiast łączyć łańcuch, zliczając liczbę jedynek:

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

Mówiłeś, że Numpy jest zbyt wolny. Czy używałeś go do przechowywania pojedynczych bitów? Dlaczego nie rozszerzyć idei używania int jako tablic bitowych, ale użyć Numpy do ich przechowywania?

Przechowuj n bitów jako tablicę ceil(n/32.)32-bitowych liczb całkowitych. Możesz wtedy pracować z tablicą numpy w ten sam (no cóż, wystarczająco podobny) sposób, w jaki używasz ints, włączając w to używanie ich do indeksowania innej tablicy.

Algorytm polega w zasadzie na obliczeniu równolegle liczby bitów ustawionych w każdej komórce i zsumowaniu liczby bitów każdej komórki.

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

Chociaż jestem zaskoczony, nikt nie zaproponował Ci napisania modułu C.

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

Okazuje się, że twoją początkową reprezentacją jest lista list liczb całkowitych, które mają wartość 1 lub 0. Po prostu policz je w tej reprezentacji.

Liczba bitów w liczbie całkowitej jest stała w Pythonie.

Jeśli jednak chcesz policzyć liczbę ustawionych bitów, najszybszym sposobem jest utworzenie listy zgodnej z następującym pseudokodem: [numberofsetbits(n) for n in range(MAXINT)]

Zapewni to ciągłe wyszukiwanie w czasie po wygenerowaniu listy. Zobacz odpowiedź @ PaoloMoretti, aby uzyskać dobrą implementację tego. Oczywiście nie musisz trzymać tego wszystkiego w pamięci - możesz użyć jakiegoś trwałego magazynu kluczy i wartości, a nawet MySql. (Inną opcją byłoby zaimplementowanie własnego prostego magazynu dyskowego).