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
int
? Czy to nie ma własnej metody obliczania tego?int.bit_length
powinna być odpowiedź, a nie ta zaakceptowana poniżej.Odpowiedzi:
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 czasubin(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:
Lub po prostu zdefiniuj to dosłownie:
Następnie
counts[x]
uzyskuje się liczbę 1 bitów,x
gdzie 0 ≤ x ≤ 255.źródło
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ą…numpy
tablicy.bin(n).count("1")
. Jednak tylko 60% odpowiedzi na pytania Pythona. @ leetcodeMożesz dostosować następujący algorytm:
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.
źródło
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.numpy
tablicami.Oto implementacja algorytmu liczenia populacji w języku Python, jak wyjaśniono w tym poście :
To zadziała
0 <= i < 0x100000000
.źródło
bin(n).count("1")
.%timeit numberOfSetBits(23544235423)
:1000000 loops, best of 3: 818 ns per loop
;%timeit bitCountStr(23544235423)
:1000000 loops, best of 3: 577 ns per loop
.numberOfSetBits
przetwarza moje 864 × 64numpy.ndarray
w 841 µs. ZbitCountStr
muszę jawnie zapętlić i zajmuje to 40,7 ms, czyli prawie 50 razy dłużej.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).
Na Pythonie 2.x należy wymienić
range
zxrange
.Edytować
Jeśli potrzebujesz lepszej wydajności (a twoje liczby są dużymi liczbami całkowitymi), zajrzyj do
GMP
biblioteki. 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.źródło
array.array
forPOPCOUNT_TABLE16
, ponieważ wtedy będzie przechowywana jako tablica liczb całkowitych, a nie jako listaint
obiektów Pythona o dynamicznym rozmiarze .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.
źródło
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.Możesz użyć algorytmu, aby uzyskać ciąg binarny [1] liczby całkowitej, ale zamiast łączyć łańcuch, zliczając liczbę jedynek:
[1] https://wiki.python.org/moin/BitManipulation
źródło
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.
Chociaż jestem zaskoczony, nikt nie zaproponował Ci napisania modułu C.
źródło
źródło
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).
źródło