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

117

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
zidarsk8
źródło
1
Jakiego rodzaju reprezentacji używasz, jeśli twoje „liczby całkowite” są dłuższe niż w standardowym Pythonie int? Czy to nie ma własnej metody obliczania tego?
Marcin
1
możliwy duplikat Count bitów liczby całkowitej w Pythonie
endolith
3
Aby odróżnić pytanie od tego na stackoverflow.com/a/2654211/1959808 (jeśli ma być inne - przynajmniej tak to wygląda), rozważ przeformułowanie tytułu na „... licząc liczbę nie- zero bitów ... ”lub podobne. W przeciwnym razie int.bit_lengthpowinna być odpowiedź, a nie ta zaakceptowana poniżej.
Ioannis Filippidis

Odpowiedzi:

121

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.

kindall
źródło
7
+1! Odwrotność tego nie jest dokładna, jednak należy stwierdzić: bin(n).count("0")nie jest dokładna z powodu przedrostka „0b”. bin(n)[2:].count('0')Musiałby być dla tych, którzy nic nie liczą…
wilk
11
Nie możesz jednak liczyć bitów zerowych, nie wiedząc, ile bajtów zapełniasz, co jest problematyczne w przypadku długich liczb całkowitych Pythona, ponieważ może to być wszystko.
kindall
2
Chociaż są to szybkie opcje dla pojedynczych liczb całkowitych, zwróć uwagę, że algorytmy przedstawione w innych odpowiedziach mogą być potencjalnie wektoryzowane, a zatem znacznie szybsze, jeśli działają na wielu elementach dużej numpytablicy.
gerrit
W przypadku tablic numpy spojrzałbym na coś takiego: gist.github.com/aldro61/f604a3fa79b3dec5436a
kindall
1
Użyłem bin(n).count("1"). Jednak tylko 60% odpowiedzi na pytania Pythona. @ leetcode
northtree
30

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.

Adam Zalcman
źródło
Naprawdę nie mam pojęcia, jak by to działało z liczbami 10 000 bitowymi, ale podoba mi się to rozwiązanie. czy możesz mi podpowiedzieć, czy i jak mogę to przypisać do większych liczb?
zidarsk8
Nie widziałem liczby bitów, z którymi masz do czynienia. Czy rozważałeś napisanie kodu obsługi danych w języku niskiego poziomu, takim jak C? Może jako rozszerzenie twojego kodu w Pythonie? Z pewnością możesz poprawić wydajność, używając dużych tablic w C w porównaniu do dużych liczb w Pythonie. To powiedziawszy, możesz przepisać CountBits()kod tak, aby obsługiwał 10k-bitowe liczby, dodając zaledwie 8 linii kodu. Ale stanie się nieporęczny z powodu ogromnych stałych.
Adam Zalcman
2
Możesz napisać kod, aby wygenerować sekwencję stałych i skonfigurować pętlę do przetwarzania.
Karl Knechtel
Ta odpowiedź ma tę wielką zaletę, że można ją wektoryzować w przypadkach zajmujących się dużymi numpytablicami.
gerrit
17

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.

Óscar López
źródło
To sprytne. Poszukiwanie tego zamiast strzelania z biodra jest całkowicie właściwe!
MrGomez
1
Czy sprawdziłeś to? Na moim komputerze używającym Pythona 2.7 okazało się, że jest to nieco wolniejsze niż bin(n).count("1").
David Weldon,
@DavidWeldon Nie, nie zrobiłem, czy mógłbyś opublikować swoje testy porównawcze?
Ó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
Jednak numberOfSetBitsprzetwarza moje 864 × 64 numpy.ndarrayw 841 µs. Z bitCountStrmuszę jawnie zapętlić i zajmuje to 40,7 ms, czyli prawie 50 razy dłużej.
gerrit
8

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
Paolo Moretti
źródło
Zredagowałem moje pytanie, aby było jasne, że potrzebuję tego do dużych liczb (10 000 bitów i więcej). optymalizacja czegoś dla 32-bitowych liczb całkowitych prawdopodobnie nie zrobiłaby tak dużej różnicy, ponieważ liczba zliczeń musiałaby być naprawdę duża, w takim przypadku spowodowałoby to długi czas wykonywania.
zidarsk8
Ale GMP jest dokładnie dla bardzo dużych liczb, w tym liczb o wielkościach, o których wspominasz, i daleko poza nimi.
James Youngman
1
Wykorzystanie pamięci będzie lepsze, jeśli użyjesz array.arrayfor POPCOUNT_TABLE16, ponieważ wtedy będzie przechowywana jako tablica liczb całkowitych, a nie jako lista intobiektów Pythona o dynamicznym rozmiarze .
gsnedders
6

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
Roboty
źródło
wygląda świetnie, ale nadaje się tylko do bardzo „rzadkich” liczb całkowitych. średnio jest dość powolny. Mimo to wygląda naprawdę przydatne w niektórych przypadkach użycia.
zidarsk8
Nie jestem do końca pewien, co masz na myśli, mówiąc „średnio jest dość wolno”. Dość wolno w porównaniu z czym? Czy masz na myśli powolny w porównaniu z innym kodem Pythona, którego nie cytujesz? Jest dwa razy szybsze niż liczenie bit po bicie dla średniej liczby. W rzeczywistości na moim macbooku liczy 12,6 miliona bitów na sekundę, czyli o wiele szybciej, niż mogę je policzyć. Jeśli masz inny ogólny algorytm Pythona, który działa dla dowolnej długości liczb całkowitych i jest szybszy niż ten, chciałbym o tym usłyszeć.
Robotbugs
1
Zgadzam się, że jest to w rzeczywistości wolniejsze niż odpowiedź Manuela powyżej.
Robotbugs
Średnio dość powolne zliczanie bitów na 10000 liczb z 10000 cyframi zajmuje 0,15 s, bin(n).count("1")ale twoja funkcja zajęła 3,8 sekundy. Gdyby liczby miały bardzo mało ustawionych bitów, działałoby to szybko, ale jeśli weźmiesz jakąkolwiek liczbę losową, średnio powyższa funkcja będzie wolniejsza o rząd wielkości.
zidarsk8
OK, zaakceptuję to. Myślę, że byłem tylko kutasem, bo jesteś trochę nieprecyzyjny, ale masz całkowitą rację. Po prostu nie przetestowałem metody przy użyciu metody Manuela powyżej przed moim komentarzem. Wygląda bardzo niezgrabnie, ale w rzeczywistości jest bardzo szybki. Teraz używam takiej wersji, ale z 16 wartościami w słowniku, a to nawet znacznie szybciej niż ta, którą zacytował. Ale dla przypomnienia, użyłem mojego w aplikacji z tylko kilkoma bitami ustawionymi na 1. Ale dla całkowicie losowych bitów, tak, będzie to około 50:50 z niewielką wariancją zmniejszającą się wraz z długością.
Robotbugs
3

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

Manuel
źródło
To działa szybko. Wystąpił błąd, przynajmniej na p3, [1:] powinno być [2:], ponieważ oct () zwraca „0o” przed łańcuchem. Kod działa jednak znacznie szybciej, jeśli użyjesz hex () zamiast oct () i
utworzysz
2

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.

leewz
źródło
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
źródło
-2

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

Marcin
źródło
@StevenRumbalski Jak to jest nieprzydatne?
Marcin
Kiedy przeczytałem twoją odpowiedź, zawierało tylko twoje pierwsze zdanie: „Liczba bitów w liczbie całkowitej jest stała w Pythonie”.
Steven Rumbalski
Mam już tabelę wyszukiwania liczby bitów dla wszystkich liczników, które można przechowywać, ale mając dużą listę liczb i operując na nich za pomocą [i] i a [j], twoje rozwiązanie jest bezużyteczne, chyba że mam 10+ GB pamięci RAM. tablica dla & ^ | dla potrójnych liczb 10000 byłby rozmiar tabeli przeglądowej 3 * 10000 ^ 3. ponieważ nie wiem, czego będę potrzebować, bardziej sensowne jest po prostu policzyć kilka tysięcy, kiedy ich potrzebuję
zidarsk8
@ zidarsk8 Lub możesz użyć jakiejś bazy danych lub trwałego magazynu kluczy i wartości.
Marcin
@ zidarsk8 10+ GB pamięci RAM nie jest szokująco duży. Jeśli chcesz wykonać szybkie obliczenia numeryczne, nie jest nierozsądne użycie żelaza o średniej wielkości.
Marcin