파이썬에서 정수의 비트 수를 계산하는 빠른 방법이 필요합니다. 내 현재 솔루션은
bin(n).count("1")하지만 더 빠른 방법이 있는지 궁금합니다.
추신 : (나는 큰 2D 이진 배열을 단일 숫자 목록으로 나타내고 비트 연산을 수행하고 있으며, 그로 인해 시간이 몇 시간에서 몇 분으로 단축됩니다. 이제 그 여분의 분을 제거하고 싶습니다.
편집 : 1. 파이썬 2.7 또는 2.6에 있어야합니다.
그리고 작은 숫자에 대한 최적화는 명확한 병목 현상이 아니기 때문에 그다지 중요하지 않지만 일부 장소에는 10,000 + 비트의 숫자가 있습니다.
예를 들어 이것은 2000 비트 케이스입니다.
12448057941136394342297748548545082997815840357634948550739612798732309975923280685245876950055614362283769710705811182976142803324242407017104841062064840113262840137625582646683068904149296501029754654149991842951570880471230098259905004533869130509989042199261339990315125973721454059973605358766253998615919997174542922163484086066438120268185904663422979603026066685824578356173882166747093246377302371176167843247359636030248569148734824287739046916641832890744168385253915508446422276378715722482359321205673933317512861336054835392844676749610712462818600179225635467147870208L답변
임의 길이 정수의 경우 bin(n).count("1")순수한 Python에서 찾을 수있는 가장 빠른 것입니다.
저는 Óscar와 Adam의 솔루션을 적용하여 정수를 각각 64 비트와 32 비트 청크로 처리했습니다. 둘 다 적어도 10 배 더 느 렸습니다 bin(n).count("1")(32 비트 버전은 시간이 절반 정도 걸렸습니다).
반면에 gmpy popcount() 는 bin(n).count("1"). 따라서 gmpy를 설치할 수 있다면 그것을 사용하십시오.
주석의 질문에 답하기 위해 바이트에 대해 조회 테이블을 사용합니다. 런타임에 생성 할 수 있습니다.
counts = bytes(bin(x).count("1") for x in range(256)) # py2: use bytearray또는 문자 그대로 정의하십시오.
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')그런 다음 0 ≤ x ≤ 255 counts[x]인 1 비트 수를 가져옵니다 x.
답변
다음 알고리즘을 적용 할 수 있습니다.
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이는 64 비트 양수에 대해 작동하지만 쉽게 확장 할 수 있으며 인수의 로그에 따라 연산 수가 증가합니다 (즉, 인수의 비트 크기에 따라 선형 적으로).
이것이 어떻게 작동하는지 이해하기 위해 전체 64 비트 문자열을 64 개의 1 비트 버킷으로 나눈다 고 상상해보십시오. 각 버킷의 값은 버킷에 설정된 비트 수와 같습니다 (비트가 설정되지 않은 경우 0, 1 비트가 설정된 경우 1). 첫 번째 변환은 유사한 상태가되지만 각 2 비트 길이의 버킷이 32 개 있습니다. 이는 버킷을 적절하게 이동하고 값을 추가하여 수행됩니다 (버킷간에 캐리가 발생하지 않기 때문에 한 번만 추가하면 모든 버킷이 처리됩니다. n 비트 숫자는 항상 숫자 n을 인코딩하기에 충분합니다). 추가 변환은 하나의 64 비트 길이 버킷에 도달 할 때까지 기하 급수적으로 증가하는 크기의 버킷 수를 기하 급수적으로 감소시키는 상태로 이어집니다. 이것은 원래 인수에 설정된 비트 수를 제공합니다.
답변
다음은이 게시물 에서 설명한대로 인구 수 알고리즘의 Python 구현입니다 .
def numberOfSetBits(i):
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24에서 작동합니다 0 <= i < 0x100000000.
답변
이 게시물 에 따르면 이것은 Hamming 가중치를 가장 빠르게 구현 한 것 같습니다 (약 64KB의 메모리를 사용하는 것이 괜찮다면).
#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])Python 2.x range에서는 xrange.
편집하다
더 나은 성능이 필요하고 숫자가 큰 정수인 경우 GMP라이브러리를 살펴보십시오 . 여기에는 다양한 아키텍처에 대해 손으로 작성한 어셈블리 구현이 포함되어 있습니다.
gmpy GMP 라이브러리를 래핑하는 C 코딩 된 Python 확장 모듈입니다.
>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024답변
이 방법이 정말 마음에 듭니다. 간단하고 매우 빠르지 만 파이썬에는 무한한 정수가 있기 때문에 비트 길이에 제한이 없습니다.
0을 스캔하는 데 시간을 낭비하지 않기 때문에 실제로 보이는 것보다 더 교활합니다. 예를 들어 1111에서와 같이 1000000000000000000000010100000001에서 설정된 비트를 계산하는 데 같은 시간이 걸립니다.
def get_bit_count(value):
n = 0
while value:
n += 1
value &= value-1
return n답변
알고리즘을 사용하여 정수의 이진 문자열 [1]을 가져올 수 있지만 문자열을 연결하는 대신 1의 수를 계산합니다.
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답변
Numpy가 너무 느리다고 했잖아요. 개별 비트를 저장하는 데 사용 했습니까? int를 비트 배열로 사용하는 아이디어를 확장하지 않고 Numpy를 사용하여 저장하는 이유는 무엇입니까?
n 비트를 ceil(n/32.)32 비트 정수 배열로 저장 합니다. 그런 다음 다른 배열을 인덱싱하는 데 사용하는 것을 포함하여 int를 사용하는 것과 동일한 방식으로 (잘, 비슷하게) numpy 배열을 사용할 수 있습니다.
알고리즘은 기본적으로 각 셀에 설정된 비트 수를 병렬로 계산하고 각 셀의 비트 수를 합산하는 것입니다.
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놀랍지 만 아무도 C 모듈 작성을 제안하지 않았습니다.
