0이 아닌 비트를 양의 정수로 빠르게 카운트하는 방법
파이썬에서 정수의 비트 수를 빠르게 셀 수 있는 방법이 필요합니다.나의 현재 해결책은
bin(n).count("1")
더 빠른 방법이 없을까요?
정수의 경우 임의 길이 의수 경우 bin(n).count("1")순수 파이썬에서 찾을 수 있는 것 중 가장 빠릅니다.
Oscar와 Adam의 솔루션을 각각 64비트와 32비트 청크로 정수를 처리하도록 조정해 보았습니다. 다 .bin(n).count("1")(32비트 버전은 약 절반의 시간이 소요되었습니다.)
반면에, gmpy. popcount()의 시간의 약 1/20을 차지했습니다.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')
그럼입니다.counts[x]를 1비트로 x여기서 0 ≤ x ≤ 255.
Python 3.10은 다음을 도입했습니다.
>>> n = 19
>>> bin(n)
'0b10011'
>>> n.bit_count()
3
>>> (-n).bit_count()
3
이는 기능적으로 다음과 같습니다.bin(n).count("1")하지만 최대 6배 더 빨라야 합니다.29882호를 참조하십시오.
다음 알고리즘을 조정할 수 있습니다.
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비트 버킷으로 나눈다고 가정합니다.각 버킷의 값은 버킷에 설정된 비트 수와 동일합니다(비트가 설정되지 않은 경우 0, 비트가 설정된 경우 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.
저는 이 방법이 정말 마음에 듭니다.파이썬은 단순하고 꽤 빠르지만, 파이썬은 무한 정수를 가지고 있기 때문에 비트 길이에 제한이 없습니다.
이것은 실제로 보기보다 더 교활합니다. 왜냐하면 0을 스캔하는 데 시간을 낭비하지 않기 때문입니다.예를 들어, 설정 비트를 1000000000000000000000010100000001에서 카운트하는 데 1111에서와 동일한 시간이 소요됩니다.
def get_bit_count(value):
n = 0
while value:
n += 1
value &= value-1
return n
이 게시물에 따르면, 이것은 해밍 무게를 가장 빠르게 구현한 것으로 보입니다(약 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])
2에서는 Python 2.x를 .range와 함께xrange.
편집
더 나은 성능이 필요한 경우(숫자가 큰 정수인 경우) 라이브러리를 확인하십시오.다양한 아키텍처를 위한 손으로 작성된 어셈블리 구현이 포함되어 있습니다.
gmpy 는 GMP 라이브러리를 감싸는 C 코드 Python 확장 모듈입니다.
>>> import gmpy
>>> gmpy.popcount(2**1024-1)
1024
알고리즘을 사용하여 정수의 이진 문자열 [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
[1] https://wiki.python.org/moin/BitManipulation
룩업테다결수있습다 니 합 할 음 과 int.to_bytes(파이썬 3에만 해당):
popcount8bit = bytes([popcount(x) for x in range(1<<8)]) # use any method to initialize this lookup table
popcount = lambda x: sum(map(popcount8bit.__getitem__,
x.to_bytes((x.bit_length()+7)//8, "little")))
도 이 은 안깝게도이솔다은루약다음보다션타느니립%▁unfortun▁than▁about 20▁20니보다 약 20% 느립니다.bin(x).count('1')Python 3에서는 두 배 더 빠르지만 PyPy3에서는 두 배 더 빠릅니다.
다음은 벤치마크 스크립트로, 여기에 제시된 여러 솔루션을 비트 수에 따라 비교한 것입니다.
from __future__ import print_function #for Python 2
import sys
from timeit import timeit
import random
def popcount(x): return bin(x).count("1")
version3=sys.version.startswith("3")
for numBit in (2, 4, 8, 16, 31, 32, 63, 64, 1000, 10000):
maximum=int((1<<numBit)-1) #int cast just in case it overflows to long in Python 2
functions=[
(popcount, "bin count"),
(lambda x: "{:b}".format(x).count("1"), "format string count"),
]
try:
import gmpy
functions.append((gmpy.popcount, "gmpy"))
except ImportError:
pass
if sys.version.startswith("3"):
exec('''functions.append((lambda x: f"{x:b}".count("1"), "f-string count"))''')
if numBit<=16:
table1=[popcount(x) for x in range(maximum+1)]
functions.append((lambda x: table1[x], "lookup list"))
functions.append((table1.__getitem__, "lookup list without lambda"))
table2="".join(map(chr, table1))
functions.append((lambda x: ord(table2[x]), "lookup str"))
if version3:
table3=bytes(table1)
functions.append((lambda x: table3[x], "lookup bytes"))
if numBit==8:
functions.append((
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'
.__getitem__, "lookup bytes hard coded 8 bit"))
table_hardcoded=(
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')
functions.append((
table_hardcoded.__getitem__, "lookup bytes hard coded 8 bit local variable"))
functions.append((table3.__getitem__, "lookup bytes without lambda"))
if version3:
popcount8bit=bytes([popcount(x) for x in range(1<<8)]) #bytes because benchmark says that it's fastest
functions.append((
lambda x: sum(popcount8bit[x] for x in x.to_bytes((x.bit_length()+7)//8, "big")),
"to_bytes"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "big"))),
"to_bytes without list comprehension"
))
functions.append((
lambda x: sum(map(popcount8bit.__getitem__, x.to_bytes((x.bit_length()+7)//8, "little"))),
"to_bytes little endian, without list comprehension"
))
#for x in (2, 4, 8, 16, 32, 64):
# table1=[popcount(x) for x in range(1<<8)]
print("====== numBit=", numBit)
data=[]
numRepeat=10**7//(numBit+100)
for popcountFunction, description in functions:
random.seed(10) #make randint returns the same value
data.append((
timeit(lambda: popcountFunction(random.randint(0, maximum)), number=numRepeat),
description
))
time1, name1=data[0]
assert name1=="bin count"
data.sort()
maxLength=0
for time, description in data:
maxLength=max(maxLength, len(description))
for time, description in data:
print("{:{}} -> {:2f} = {} * {:2f}".format(description, maxLength+2, time, name1, time/time1))
Python 2와 3 모두에서 작동하지만 Python 2에 대한 솔루션을 사용할 수 없는 경우에는 측정되지 않습니다.
일부 솔루션은 여기에 나열되지 않습니다.
결과:
- 파이썬 2: <= 16비트의 경우 "빈 카운트"보다 25% 빠르며, "빈 카운트"보다 6% 빠르며, "빈 카운트"가 가장 빠릅니다. (파이썬 2의 경우 gmpy를 설치하지 않았습니다.)
- 파이썬 3: 대략 같은 결과입니다.
- "람다를 사용하지 않는 조회 바이트"는 "람다를 사용하지 않는 조회 목록"과 비교하여 (+/-2%) 비교할 수 있습니다.
- gmpy는 모든 경우에서 "bin count"보다 빠르지만, numBit <= 16으로 "람다가 없는 list"보다 약 5% 느립니다.
- "to_bytes"는 유사합니다.
- f-string을 사용하는 것은 "bin count"보다 약 10% 느립니다.
- 는 더 비용을 , PyPy3: 람다는더이많상비발않으며지,
to_bytes버전이 훨씬 빨라집니다("bin count"보다 두 배 빠름). 하지만 gmpy를 설치할 수 없었습니다.
Numpy가 너무 느리다고 했잖아요.개별 비트를 저장하는 데 사용했습니까?int를 비트 배열로 사용하는 아이디어를 확장하고 Numpy를 사용하여 저장하는 것은 어떻습니까?
n비트를 배열로 저장ceil(n/32.)32비트 int.그런 다음 numpy 배열을 사용하여 다른 배열을 인덱싱하는 것을 포함하여 int를 사용하는 것과 동일한 방식(충분히 유사함)으로 작업할 수 있습니다.
알고리즘은 기본적으로 각 셀에 설정된 비트 수를 병렬로 계산하고 각 셀의 비트 수를 합산하는 것입니다.
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 모듈을 쓰라고 제안하지 않은 것이 놀랍습니다.
class popcount_lk:
""" Creates an instance for calculating the population count of
bitstring, based on a lookup table of 8 bits. """
def __init__(self):
""" Creates a large lookup table of the Hamming weight of every 8 bit integer. """
self.lookup_table = bytes.maketrans(bytes(range(1<<8)),bytes((bin(i).count('1') for i in range(1<<8))))
self.byteorder = sys.byteorder
def __call__(self,x):
""" Breaks x, which is a python integer type, into chuncks of 8 bits.
Calls the lookup table to get the population count of each chunck and returns
the aggregated population count. """
return sum(x.to_bytes((x.bit_length()>>3)+1,self.byteorder).translate(self.lookup_table))
popcount = popcount_lk
print(popcount(56437865483765))
이 속도는 다음보다 3배 빨라야 합니다.bin(56437865483765).count('1')Cython 및 PyPy3에서.
@로봇벌레의 대답, 하지만 numba의 njit 장식기에 싸여 있는 것이 제 경우 gmpy보다 빨랐습니다.
@njit(int64(uint64))
def get_bit_count(bitboard):
n = 0
bitboard = int64(bitboard)
while bitboard:
n += 1
bitboard &= bitboard - 1
return n
OverlowError를 피하기 위해 unt64를 인수 유형으로 설정해야 했습니다.
#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)
시작 표현이 1 또는 0인 int 목록인 것으로 나타났습니다.그 표현에서 그것들을 간단히 세어보세요.
정수의 비트 수는 파이썬에서 일정합니다.
그러나 설정된 비트 수를 계산하려면 다음 의사 코드를 준수하는 목록을 만드는 것이 가장 빠른 방법입니다.[numberofsetbits(n) for n in range(MAXINT)]
이렇게 하면 목록을 생성한 후에도 지속적인 시간 조회가 제공됩니다.이를 제대로 구현하려면 @PaoloMoretti의 답변을 참조하십시오.물론 이 모든 것을 메모리에 저장할 필요는 없습니다. 영구 키 값 저장소나 MySql을 사용할 수도 있습니다. (또 다른 옵션은 간단한 디스크 기반 스토리지를 구현하는 것입니다.)
언급URL : https://stackoverflow.com/questions/9829578/fast-way-of-counting-non-zero-bits-in-positive-integer
'source' 카테고리의 다른 글
| ORA-01658: 테이블스페이스 TS_DATA에서 세그먼트에 대한 INITIAL 익스텐트를 생성할 수 없습니다. (0) | 2023.06.15 |
|---|---|
| 요인 수준과 요인 레이블 간의 혼동 (0) | 2023.06.15 |
| R에 로드된 패키지 버전을 확인하는 방법은 무엇입니까? (0) | 2023.06.15 |
| 10.4.24-MariaDB - 외부 키 구속조건이 잘못 형성됨 (0) | 2023.06.15 |
| SQL을 사용하여 테이블의 열 수를 계산하는 방법은 무엇입니까? (0) | 2023.06.15 |